离散数学——二部图复习

来源：计算机等级考试发布时间：2012-08-27 计算机等级考试视频评论

定义1：   若能将无向图G= 的顶点集V划分成两个子集 V1和V2（V1交V2为空集），使得G中任何一条边的两个端点一个属于V1，另一个属于V2，则称G为二部图（也称偶图），V1、V2称为互补顶点子集，此时可将G记成G= .
         若V1中任一顶点与V2中每一个顶点均有且仅有一条边相关联，则称二部图G为完全二部图（或完全偶图）。

定理1：   一个无向图G=是二部图当且仅当G中无奇数长度的回路。

定义2：   设G=为无向图，E*属于E，若E*中任意两条边均不相邻，则称E*为G中的匹配（或边独立集）。若在E*中再加入任何1条边就都不是匹配了，则称E*为极大匹配。边数最多的极大匹配称最大匹配，最大匹配中的元素（边）的个数称为G的匹配数。
          设M为G中一个匹配。v属于V（G），若存在M中的边与v关联，
则称v为M饱和点，否则称v为M非饱和点。若G中每个顶点都是M饱和点，则称M为G中完美匹配。

定义3：   设G=为一个二部图，M为G中一个最大匹配，若|M|=min{|V1|,|V2|},则M为G中一个完备匹配，此时若|V1|<=|V2|，则称M为V1到V2的一个完备匹配。如果|V1|=|V2|，这时M为G中的完美匹配。

定理2：（Hall定理）设二部图G=〈V1，V2，E〉，|V1|<=|V2|，G中存在从V1到V2的完备匹配当且仅当V1中任意k个顶点（k=1，2....，|V1|）至少邻接V2中的k个顶点。

定理3：
由Hall定理容易证明下面定理：
1，V1中每个顶点至少关联t（t>0）条边；
2，V2中每个顶点至多关联t条边，则G中存在V1到V2的完备匹配。

Hall定理中的条件为“相异性条件”，定理3中的条件为“t条件”。
满足t条件的二部图，一定满足相异性条件，事实上，由条件（1）可知，V1中k个顶点至少关联 kt条边。由条件（2）可知，这 kt条边至少关联V2中的k个顶点，于是若G满足t条件，则G一定满足相异性条件，但反之不真。

视频学习

我考网版权与免责声明

① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件，版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源：我考网"，违者本网将依法追究责任；

② 本网部分稿件来源于网络，任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益，应该及时向我考网书面反馈，并提供身份证明、权属证明及详细侵权情况证明，我考网在收到上述法律文件后，将会尽快移除被控侵权内容。