二分圖最大匹配必經點

下文只判定右部的必經點；顯然左部是同理的。

先按照 flow 求二分圖最大匹配建出網絡流：\((S,i\in L,1),(u\in L,v\in R,1),(v\in R,T,1)\)。

Theory：只需要從 \(T\) 出發，不斷走滿流邊（可能是反向邊滿流）。最后沒有被走到的所有點就是必經點。

先感性理解一下，過程本質會搜出來增廣路狀物，上面的邊流與不流間隔出現，顯然都能調整。

Prove：我們分兩部分證明：[1]被走到的點不是必經點；[2]沒被走到的點都是必經點。

[1]證明：觀察流出的路徑：第一步一定是走 \(T\to v\)，殘余網絡滿流，即原圖沒有選 \(v\)；第二步不能返回 \(T\)，一定是走 \(v\to u\)，殘余網絡滿流，即原圖沒有選 \((u,v)\)；第三步肯定走不回 \(S\)，所以會走 \(u\to v_1\)，此時原圖選擇了 \((u,v_1)\)；依此類推直到沒法選了。

觀察圖片，不難發現所有選出的右部點都是存在調整方案的。

[2]證明：考慮反證，假設存在一個沒被走到的點 \(u\in R\)，它不是必經點。

\(\because\) 它沒有被走到
\(\therefore\) 原圖必有 \(u\to T\) 的邊，并且流了；
\(\therefore\) 原圖必有 \(x\in L,x\to u\) 的邊，并且流了.
\(\because\) \(u\) 不是必經點
\(\therefore\) 存在一個 \(v\) 調整 \(x\)，即原圖必有 \(v\in R,x\to v\) 的邊，但是沒有流.
若 \(v\to T\) 沒有流，手玩一下，此時 \(u\) 可以被反向 visit 到，矛盾；
\(\therefore\) \(v\to T\) 必流；
\(\therefore\) 存在 \(y\to v\) 的邊，并且流了.
......繼續往下推

依此類推，發現按照這個調整流程，最后將會創建無窮個點（可以自己再手玩幾步），與二分圖有有限個點矛盾。

所以 [2] 證畢。與 [1] 結合即證命題。\(\square\)

\(\text{ }\)

二分圖最大匹配必經邊

判定條件：\(u\to v\) 流了，并且殘余網絡上不屬于相同的連通分量。

這個就顯然很多了。我懶得寫證明了。