一张图带你看完图论第五章（包含全部考点，含定义、定理、公式、推导证明和所有例题）-Toy模板网

这篇具有很好参考价值的文章主要介绍了一张图带你看完图论第五章（包含全部考点，含定义、定理、公式、推导证明和所有例题）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

付费大佬可以联系我把你们加入思维导图协作，看更加具体清楚地思维导图/敬礼

（思维导图在最后，可以直接看图不看文字）

5.1 匹配文章来源地址https://www.toymoban.com/news/detail-485601.html

匹配（边独立集）M是G的不相邻边组成的边子集（无环）
- 饱和点 v是匹配M中某边的端点，则称v为M饱和点
- 完美匹配 G中每个顶点均为M饱和点，则M为G的完美匹配
  - 最优匹配在赋权完全偶图寻找一个具有最大权值的完美匹配
- 最大匹配若M是G包含边数最多的匹配，则M为G的最大匹配
M交错路 M中的边和非M的边交替组成的路
- M可扩路起点与终点为M非饱和点的路
  - M是G的最大匹配当且仅当 G不含M可扩路
  - 中间的点一定都是M饱和点，起始非M边然后交错最后非M边
5.3 Tutte定理与完美匹配
- 偶数阶图G 有完美匹配当且仅当 o(G-S)≤|S| 对所有S属于V成立（任意删去s个顶点，所得图奇分支个数<=删去点数）
  - 奇分支o(G) 拥有奇数个顶点
- 没有割边的三正则图一定有完美匹配（每条边都在圈之中，彼得森图）有割边的三正则图不一定没有完美匹配
- 什么样的树有完美匹配？o(T‒v)=1
  - 因为T有完美匹配，由Tutte定理知o(T‒v)≤1显然，T是偶数阶的图，于是o(T‒v)≥1。因此，o(T‒v)=1。
5.4 因子分解
- 因子：至少含G一条边的生成子图（非空生成子图）K因子-K正则的因子
  - 一因子的边集构成一个完美匹配（因为因子是边导出生成子图，要包含所有顶点，所以存在1因子必然有完美匹配）二因子的连通分支为一个圈（多个独立圈，H圈一定是二因子，但二因子不一定是H圈，连