离散数学——二部图复习

定义:如果一个无向图G=的顶点集V可分为V1和V2两个子集(V1过V2为a 空集)，使得G中任意一条边的两个端点之一属于V1，另一个属于V2，则G称为二部图(也叫偶图)，V1和V2称为补顶点子集。此时G可以记为G =。[/]

定理1:一个无向图G=是二分的当且仅当G中没有奇数环

定义2:设G=是一个无向图，E*属于E .如果E*中任意两条边不相邻，则称E*为G中的一个匹配(或边独立集).如果给E*加任何边都不是匹配，则称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|
定理2:(霍尔定理)设为2 .
2、若V2中的每个顶点至多与T条边相关联，则g中的V1与V2完全匹配

霍尔定理中的条件是“相异条件”，定理3中的条件是“T条件”。
满足T条件的二部图一定满足相异条件。事实上，从条件(1)可以知道，V1中的k个顶点至少与kt条边相关联。从条件(2)可以看出，这条kt边与V2中至少k个顶点相关联，所以如果g满足t条件，那么g必然满足相异条件，反之则不成立。