设G = 为二分图, |V1|≤|V2|, M为G中一个最大匹配, 且|M| = |V1|, 则称M为G的完备匹配，也是最大匹配。
举一反三
- 设G = [V, E]中无孤立点。M为G的最大匹配, 对于G中每个未覆盖顶点v, 选取与v关联的边组成集合N,则MÈN是G的最小边覆盖。
- 设无向图G=<V，E>，则对任意V1⊂V且V1≠∅，若p(G - V1)≥|V1|，则G不是哈密顿图.
- 设 G=[V,E]为一个无向图，若能将 V分成 V1和V2(V1∪V2=V，V1∩V2=∅)，使得 G 中的每条边的两个端点都是 一个属于V1，另一个属于V2，则称这样的图为（ ） A: 无向图 B: 有向图 C: 二部图
- 设G＝，|V1|≤|V2|，G中存在从V1到V2的完备匹配当且仅当V1中任意k个结点(k＝1，2，…，|V1|)至多邻接V2中的k个结点。
- 给定赋权二分图G,如果G的相等子图G’有完美匹配M*，则M*是G的最大权匹配。