离散数学——二部图复习

文章作者 100test 发表时间 2007:03:10 18:38:16
来源 100Test.Com百考试题网

定义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一定满足相异性条件，但反之不真。