【摘要】：，|V1|）至少邻接V2中的k个结点.定理9.22（t条件）设G=＜V1，V2，E＞，若V1中每个结点至少关联t（t＞0）条边，而V2中每个结点至多关联t条边，则G中存在V1到V2的完备匹配.
二部图（偶图）、完全二部图：设G=＜V，E＞是一个无向图，若V=V1∪V2，V1∩V2=Ø，且G中任一条边的两个端点分别属于V1和V2，则称G为二部图或偶图，记为G=＜V1，V2，E＞.在二部图G=＜V1，V2，E＞中，若|V1|=m，|V2|=n，且对任意的u∈V1和v∈V2均有［u，v］∈E，称G为完全二部图，记为Km，n.
定理9.20 简单图G为二部图⇔G中所有基本回路的长度为偶数.
匹配：设无向图G=＜V，E＞，M⊆E，若M中任意两条边都不相邻，则称M为G的一个匹配，并把M中的边所关联的两个结点称为在M下是匹配的.若在M中再加入任何一条边就不是匹配了，称M为极大匹配.边数最多的极大匹配称为G的最大匹配.最大匹配的边数称为G的匹配数.
M是G中的一个匹配，若结点v与M中的边关联，称v为M饱和点，否则称v为M非饱和点.若G中每个结点都是M饱和点，称M是完全匹配.(www.xing528.com)
最大匹配、完备匹配、完全匹配：设G=＜V1，V2，E＞为二部图，M是G中一个最大匹配，若|M|=min｛|V1|，|V2|｝，称M为G中的一个完备匹配.若此时|V1|≤|V2|，称M为V1到V2的一个完备匹配.若|V1|=|V2|，称M为G的完全匹配.
定理9.21（Hall定理） 设G=＜V1，V2，E＞，|V1|≤|V2|，G中存在从V1到V2的完备匹配⇔V1中任意k个结点（k=1，2，…，|V1|）至少邻接V2中的k个结点.
定理9.22（t条件） 设G=＜V1，V2，E＞，若V1中每个结点至少关联t（t＞0）条边，而V2中每个结点至多关联t条边，则G中存在V1到V2的完备匹配.
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
