今有a、b、c、d、e、f、g共7个球类运动爱好者,已知下列事实:a喜欢篮球运动;b喜欢篮球运动和足球运动;c喜欢篮球、排球和乒

今有a、b、c、d、e、f、g共7个球类运动爱好者,已知下列事实:a喜欢篮球运动;b喜欢篮球运动和足球运动;c喜欢篮球、排球和乒乓球运动;d喜欢网球和足球运动;e喜欢羽毛球和排球运动;f喜欢棒球、网球和乒乓球运动;g喜欢棒球和羽毛球运动。试问:这7个人应如何围圆桌排座位,才能使每个人和他身边的人有共同球类爱好话题。须写出所有可能方案。
【正确答案】:

如果两个人爱好同一种球类,则用无向边连接它们,得到图34-1为按题意构造的关系图。求该图所有的哈密顿回路,即为所求得的方案。如图34-2所示。


【题目解析】:如果两个人爱好同一种球类,则用无向边连接它们,得到图34-1为按题意构造的关系图;求解方案实际上是寻找图34-1中是否有哈密顿回路,该哈密顿图中每个结点的度数均为2。所以在删边时应考虑删除度数大于2的结点关联的边。由此判断:因为结点c的度数为4,所以必须删掉结点c关联的两条边,边bc、cf删除后所有结点的度数刚好均为2,由此构成一个哈密顿回路。删除其他边均不能满足条件,所以只有一种方案。