计算机科学论坛--离散：关于求完备匹配方案数的方法

贴子主题：离散：关于求完备匹配方案数的方法

本主题类别:

离散大本，关于第十三章支配集、覆盖集、独立集与匹配，P200 习题8
8.现有三个课外小组：物理组，化学组，生物组，今有张，王，李，赵，陈5名同学，已
知
1）张，王为物理组成员，张，李，赵为化学组成员，李，赵，陈为生物组成员
2）张为物理组成员，王，李，赵为化学组成员，王,李，赵，陈为生物组成员
3）张为物理组成员和化学组成员，王,李，赵，陈为生物组成员;
问在(1),(2),(3)三种情况下能否各选出3名不兼职的组长？为什么？若能选出，各有多少
种不同的选择方案?

解：用顶点v1,v2,v3,v4,v5分别表示张，王，李，赵，陈，用u1,u2,u3分别表示物理组，
化学组和生物组，若vi是uj的成员，就连边(vi,uj)，分别做二部图进行讨论，若存在完
备匹配
就能选出三名不兼职的组长，否则就不能
1)在第一种情况下，所做的二部图为图(略)所示，设V1={u1,u2,u3},V2={v1,v2,v3,v4,
v5},V1中每个顶点至少关联2条边，V2中每个顶点至多关联两条边，取 t=2,则满足t=2的
条件由定理可知，存在从V1 到V2的完备匹配，因而可以选出三名不兼职的组长，并且可
以有11中不同的选择方案.
2)在第二种情况下，所做二部图（图略），此二部图不满足t条件，但满足“相异性”条
件，
因而也存在从V1到V2的完备匹配，所以可以选出三名不兼职的组长来，共有9种可选择的
方案。
3）在第三种情况下，所得二部图不满足“相异性条件”，因而不存在从V1到V2的完备匹
配，所以选不出三名不兼职的组长来

有个问题：对于1）、2）两种情况，“各有多少种不同的选择方案?”，即求完备匹配方案
数，这个推理过程能否细化些，是不是用高中代数里的排列组合的计算方法？如果不
是，是用什么方法？不管是什么方法，能否花时间给出你的推理过程？

请多指教，谢谢了！


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	46.875ms