08年 离散数学 自考试题

来源：百度知道 编辑：UC知道 时间：2024/05/22 06:27:19
今要将6人分成3组（每组2个人）去完成3项任务。已知每个人至少与其余5个人中的3个人能相互合作。
（1）能否使得每组的2个人都能相互合作？ （2）你能给出几种不同的分组方案？

将6个人看成结点,两人能相互合作,其对应的两点之间存在一条边,这样得到一个图,该问题化为图论中的匹配问题,即确定存在不存在一个最大匹配问题,如果存在最大匹配,确定有多少不同的最大匹配.
由每个人至少与其余5个人中的3个人能相互合作,则对任意点v,v的度数大于等于3,这是条件.