给定赋权二分图G,如果G的相等子图G’有完美匹配M*，则M*是G的最大权匹配。
对
举一反三
内容
- 0
设G=是n阶m条边的无向图，若G是树，则G是连通的且m=n-1.
- 1
给定二分图G = 中无孤立点，其最大流算法求得最大流f, 则 G的最大匹配数=f.
- 2
设G = [V, E]中无孤立点。M为G的最大匹配, 对于G中每个未覆盖顶点v, 选取与v关联的边组成集合N,则MÈN是G的最小边覆盖。
- 3
设图G有p个顶点，如果图G的色数为p，则图G为完全图
- 4
G’是图G=的子图,若给定另外一个图G''=使得E''=E-E’,且V''中仅包含E''的边所关联的结点,则称G''是子图G’相对于图G的补图