淺談二分圖
- 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』的邊是可以互換的，因此一條交錯路上的點都不是關鍵點\)
\(具體的，可以對於每一個未匹配點再跑增廣路，訪問到的點便不是關鍵點\)
\(即是非匹配邊左連右，匹配邊右連左\)
