图论记事
由于我是图论**,本文定理一般情况下不给出证明。
二分图
定义
二分图又称作二部图,是图论中的一种特殊模型。
设 $G=(V, E)$ 是一个无向图。如果顶点集 $V$ 可分割为两个互不相交的子集 $X$ 和 $Y$,并且图中每条边连接的两个顶点一个在 $X$ 中,另一个在 $Y$ 中,则称图 $G$ 为二分图。
判定
- 一个图是二分图当且仅当它无奇环。
匹配
给定一个二分图 $G$ ,在 $G$ 的一个子图 $M$ 中,$M$ 的边集 ${E}$ 中的任意两条边都不依附于同一个顶点,则称 $M$ 是一个匹配。
最大匹配就是选择边数最大的匹配。
如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。
显然完备匹配一定是最大匹配,而最大匹配不一定是完备匹配。
最大匹配算法
匈牙利算法
最大流
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Pozhu's blog!
评论
GiscusValine