浅谈二分图

• 2022 年 1 月 6 日
• 笔记

二分图

\(\mathcal{No.1} 二分图的定义及其基本性质\)

\(1.定义\)

\(节点由两个集合组成，且两个集合内部没有边的图\)

\(2.性质\)

\(二分图不存在奇数环\)

\(证明:考虑一个环，点一定是在左部图与右部图中交错出现，如果存在奇数环，那环的末端与始端连上的边使得一部中有边相连\)

\(根据定义，可以用染色来判定二分图\)

\(\mathcal{No.2}二分图最大匹配\)

\(1.增广路\)

\(如果在二分图中存在一条连接两个非匹配点的路径 path，使得非匹配边与匹配边在 path 上交替出现，那么称 path 是匹配 S 的一条增广路\)

\(而交错路即是一条路径非匹配边与匹配边交替出现\)

\(2.匈牙利算法\)

\(显然，每一次增广都会让匹配边加一\)

\(设M为当前匹配，M’为更大的一个匹配\)

\(D=M\oplus M'(即为对称差)\)

\(D对于每一个点,最多度数为2，分别为M,M’上的点\)

\(度数为2的点有的是一个环，且环是有M，M’的边交错出现\)

\(取出环，|M’|>|M|,此时，D中只存在几条交错链\)

\(考虑D的每一个链，如果链长为偶数，那么该链对M，M’的贡献是相同的\)

\(而对于奇数\because|M’|>|M|\therefore 一定存在奇链是M的增广路即为当前奇链\)

\(\therefore 最大匹配当且仅当不存在增广路\)

\(\mathcal{No.3}二分图最大匹配的关键点,关键边,可行边\)

\(1对称差的性质\)

\(考虑两个不同的最大匹配M,M’\)

\(D=M\oplus M’\)

\(由上面的证明可得，D一定由偶数交替环与偶数交替链组成\)

\(2.关键点\)

\(考虑两个不同的最大匹配，M，M’,D=M\oplus M’\)

\(设p为M中的匹配点，但不是M’中的匹配点\)

\(\because p\in M,且p\notin M’\therefore p一定没有偶数环，且存在一条交错路经过p，末端与p同侧，为未匹配点\)

\(而对于这条交错路，M，M’的边是可以互换的，因此一条交错路上的点都不是关键点\)

\(具体的，可以对于每一个未匹配点再跑增广路，访问到的点便不是关键点\)

\(即是非匹配边左连右，匹配边右连左\)