今有a，b，c，d，e，g共7人，已知下列事实： a会讲法语；b会讲法语、意大利语和日语；c会讲法语、汉语；d会讲日语和意大利语

今有a，b，c，d，e，g共7人，已知下列事实： a会讲法语；b会讲法语、意大利语和日语；c会讲法语、汉语；d会讲日语和意大利语；e会讲德语、汉语和法语;f会讲英语、日语和俄语；g会讲英语和德语。试问：这7个人应如何围圆桌排座位，才能使每个人和他两边的人可以交谈?(须写出所有可能方案)
【正确答案】：
【题目解析】：如果两个人会讲同一种语言，则用无向边连接它们，得到图35-1为按题意构造的关系图；求解方案实际上是寻找图35-1中是否有哈密顿回路，该哈密顿图中每个结点的度数均为2。所以在删边时应考虑删除度数大于2的结点关联的边。由此判断：必须删掉边bf。边be必须删除，否则若保留，则结点b和e的度数已经都是2，这样只能删除跟这两个结点关联的其他边，但删除这些边后原图变成非连通图。在删除bf和be所得到的新图中，必须再删除两条边，而且要保证abce四个结点各减去1度，才能使所有结点度数为2.（1）若删除ab，则只能删除ce，才能满足条件；反之亦然。（2）若删除bc，则只能删除ae，才能满足条件；反之亦然。（3）若删除ac，则均不可能满足条件。所以，所有符合条件的方案只有2个。如图35-2为所有符合要求的安排方案。