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