Matching - 演算法筆記

maximum matching 一張圖中，配對數最多的匹配。

也是maximal matching。

perfect matching 一張圖中，所有點都送作堆的匹配。

也是maximum matching。

Weight. 當圖上的 ... Matching Matching 一張無向圖，相鄰兩點配成一對。

但是呢——一個點最多只能與一個鄰點配成一對，寧可孤家寡人，不可三妻四妾。

雙雙對對的邊，整體形成一個「匹配」。

換句話說：挑選一些邊，讓圖上每一點僅接觸零條邊或一條邊。

這些邊構成的集合，稱作一個「匹配」。

MatchedVertex與UnmatchedVertex 一個點要嘛跟另一個點比翼雙飛，要嘛孑然一身──前者為「匹配點」，後者為「未匹配點」。

MatchedEdge與UnmatchedEdge 出雙入對的兩點之間的邊為「匹配邊」，除此以外則為「未匹配邊」。

一個匹配由許多匹配邊組成。

Cardinality 一個匹配擁有的匹配邊數目，稱作「基數」。

「基數」源自集合論，意義是集合的大小。

順便介紹一些特別的匹配： maximalmatching 一張圖中，沒有辦法直接增加配對數的匹配。

maximummatching 一張圖中，配對數最多的匹配。

也是maximalmatching。

perfectmatching 一張圖中，所有點都送作堆的匹配。

也是maximummatching。

Weight 當圖上的邊都有權重，一個匹配的權重是所有匹配邊的權重總和。

順便介紹一些特別的匹配： maximumweightmatching 一張圖中，權重最大的匹配。

maximumweightmaximum(cardinality)matching 一張圖中，配對數最多的前提下，權重最大的匹配。

maximumweightperfectmatching 一張圖中，所有點都送作堆的前提下，權重最大的匹配。

BipartiteMatching BipartiteGraph 「二分圖」是圖的一種特例。

一張二分圖的結構是：兩群點（通常標記作X集合與Y集合）、橫跨這兩群點的邊（X與Y之間）。

至於兩群點各自之內是沒有邊的（X與X、Y與Y間）。

順帶一提，二分圖構造較單純，其資料結構可以進行精簡： BipartiteMatching 一張二分圖上的匹配，稱作「二分匹配」。

所有的匹配邊，都是這橫跨這兩群點的邊，就像是連連看。

使用Flow尋找BipartiteMatching 一側接上源點，一側接上匯點，即可利用網路流來解決最大二分匹配問題、最大（小）權二分匹配問題。

AugmentingPathTheorem（Berge'sTheorem） 導讀 AugmentingPathTheorem是尋找最大匹配的重要理論。

本章節當中，首先介紹相關元件，然後證明理論，最後提出一種尋找最大匹配的手段。

AlternatingPath與AlternatingCycle 「交錯路徑」與「交錯環」。

在一張存在匹配的圖上，匹配邊和未匹配邊彼此相間的一條路徑與一個環。

交錯環有個有趣的特性：顛倒交錯環上的匹配邊和未匹配邊，可以改變匹配，但是不影響Cardinality。

AugmentingPath 「擴充路徑」。

一條交錯路徑，第一個點和最後一個點都是未匹配點。

因此第一條邊和最後一條邊都是未匹配邊。

擴充路徑有個更有趣的特性：顛倒擴充路徑上的匹配邊和未匹配邊，可以改變匹配，並且讓Cardinality加一。

SymmetricDifference 兩個集合A和B的「對稱差集」定義為A⊕B=(A∪B)-(A∩B)。

例如A={1,3,4,5}、B={2,4,5,7}、A⊕B={1,2,3,7}，沒有重複出現的元素將會留下，重複出現的元素將會消失。

對稱差集非常適合用來描述「顛倒擴充路徑上的匹配邊與未匹配邊」這件事情。

現在有一個匹配M，和一條擴充路徑P（拆開成邊），那麼M⊕P會等於新匹配。

坊間書籍常以對稱差集來表述匹配相關理論。

在此特別將對稱差集的概念介紹給各位，希望各位往後遇到⊕這個符號時，不會下意識地認為它艱深晦澀。

SymmetricDifferenceofMatchings 同一張圖上的兩種匹配M和M*也可以計算對稱差集M⊕M*，總共會產生六大類connectedcomponent，都是交錯路徑或者交錯環，各位若是不信可以親自實驗看看： 兩個匹配的對稱差集，提供了這兩個匹配互相變換的管道：對其中一個匹配來說，只要顛倒整個對稱差集當中的匹配邊與未匹配邊，就變成另一個匹配。

寫成數學式子就是：令M⊕M*=P，則M⊕P=M*、M*⊕P=M。

AugmentingPathTheorem 從圖上任取一個未匹配點，如果找不到以此點作為端點的擴充路徑，那麼這張圖會有一些最大匹配不會包含此點。

更進一步來說，就算從這張圖上刪除此點（以及相連的邊），以剩餘的點和邊，還是可以找到原本那張圖的其中一些最大匹配。

證明不困難，利用一下先前所學到的東西，便可以推理出來： 令當下的匹配M找不到以未匹配點p作為端點的擴充路徑。

令M*是該圖的其中一個最大匹配。

一、如果p不在M*上： 　　刪除此點完全不會對M和M*有任何影響，定理成立。

二、如果p在M*上： 　甲、p對於M來說是未匹配點。

理所當然p不在M上。

　乙、考慮M⊕M*的六種情形。

p不在M上，且p在M*上，所以只有d或e符合條件。

　丙、M找不到以p作為端點的擴充路徑，所以d不符合條件，只有e符合條件。

　丁、對於M*來說，只要照著e顛倒匹配邊和未匹配邊， 　　　就可以製造出另一個不會包含p的最大匹配， 　　　成為步驟一的情況，定理還是成立。

這個理論相當重要，它表明了一個找最大匹配的手段： 遞歸法，不斷刪除找不到擴充路徑的未匹配點，減小問題規模，減小圖的規模。

無論刪除多少點，依然能保留原圖的某些最大匹配。

一、一開始圖上所有點都是未匹配點。

二、每個未匹配點，依序嘗試作為擴充路徑的端點： 　甲、如果找得到擴充路徑： 　　　沿著擴充路徑修改現有匹配，以增加Cardinality。

　　　（此未匹配點變成了匹配點。

） 　乙、如果找不到擴充路徑： 　　　直接刪除此點。

繼續下去仍然可以找到原圖的其中一個最大匹配。

　　　（此未匹配點被刪除。

） 所有的未匹配點，要嘛變成匹配點、要嘛被刪除。

未匹配點盡數消失，同時產生其中一個最大匹配。

AugmentingPathTheorem另一種形式 一個匹配，若無擴充路徑，即是最大匹配。

要是圖上所有未匹配點都不能當作擴充路徑的端點，就代表著圖上根本就沒有擴充路徑。

Cardinality無法增加，就代表著當下的匹配就是最大匹配囉！ 這個理論相當重要，它表明了一個找最大匹配的手段： 不斷找擴充路徑，直到找不到為止。

此時的匹配就是最大匹配。

MaximumBipartiteMatching:AugmentingPathAlgorithm 導讀 以下章節將介紹Matching的各種演算法。

每當講解一個演算法，先談比較簡單的特例BipartiteMatching，再談比較複雜的通例Matching，循序漸進講解。

用途 找出一張二分圖的其中一個最大二分匹配。

AlternatingTree 選定一個未匹配點作為起點，嘗試列出所有的交錯路徑──藉此尋找擴充路徑。

有個重要的發現：當兩條交錯路徑撞在同一個點，將來還是只能選擇其中一條路徑來進行擴充，所以只要留下一條路徑就夠了。

根據這個重要的發現，圖上的每個點、每條邊只需出現一次。

我們得以使用GraphTraversal來尋找一條擴充路徑，並形成一棵樹，稱作「交錯樹」。

二分圖當中，每條交錯路徑都在X與Y之間來回。

演算法 一、一開始圖上所有點都是未匹配點。

二、X的每個未匹配點，依序嘗試作為擴充路徑的端點。

　　以GraphTraversal建立交錯樹，以尋找擴充路徑。

　　（X的未匹配點一旦處理完畢，Y的未匹配點不會再有擴充路徑，故只需找X側。

） 　甲、如果找得到擴充路徑： 　　　沿著擴充路徑修改現有匹配，以增加Cardinality。

　　　（此未匹配點變成了匹配點。

） 　乙、如果找不到擴充路徑： 　　　直接刪除此點。

繼續下去仍然可以找到原圖的其中一個最大匹配。

　　　（此未匹配點被刪除。

） 這個演算法運作起來，如同接上了源點與匯點再進行Ford-FulkersonAlgorithm（AugmentingPathAlgorithm）。

時間複雜度 時間複雜度是O(V)次GraphTraversal的時間。

圖的資料結構為AdjacencyMatrix，便是O(V³)；圖的資料結構為AdjacencyLists，便是O(VE)。

找出一個最大二分匹配 以DFS尋找擴充路徑，程式碼變得相當精簡。

採用BFS也是可以的，這裡就不贅述了。

constintX=100; //X的點數 constintY=100; //Y的點數 intmx[X],my[Y]; //X各點的配對對象、Y各點的配對對象 boolvy[Y]; //記錄GraphTraversal拜訪過的點 booladj[X][Y]; //精簡過的adjacencymatrix //以DFS建立一棵交錯樹 boolDFS(intx) { for(inty=0;y GreedyMatching 這裡介紹一個加速手段：明顯可以配對的點，預先配對。

如此一來這些點就不必建立交錯樹。

圖很龐大的時候，得以發揮功效。

雖然多了一次GraphTraversal，但是少了許多棵交錯樹。

intgreedy_matching() { intc=0; for(intx=0;x UVa259670753100801009210243104181098466311148 MaximumMatching:BlossomAlgorithm（Edmonds'Algorithm） 用途 找出一張無向圖的其中一個最大匹配。

AlternatingTree:CrossEdge 交錯樹當中，「偶點」距離樹根偶數條邊，「奇點」距離樹根奇數條邊。

一般圖的交錯樹、二分圖的交錯樹，兩者有個不同之處──偶點到偶點的邊。

二分圖的交錯樹 偶點到奇點：一定是未匹配邊。

奇點到偶點：一定是已匹配邊。

偶點到偶點：二分圖不會有這種邊。

奇點到奇點：二分圖不會有這種邊。

一般圖的交錯樹 偶點到奇點：一定是未匹配邊。

奇點到偶點：一定是已匹配邊。

偶點到偶點：一定是未匹配邊，且會形成「花」。

奇點到奇點：交錯樹不會有這種邊，因為不會形成交錯路徑。

AlternatingTree:Cycle 偶點到偶點的邊，在交錯樹上形成一個環。

只要穿越這條偶點到偶點的邊，以繞遠路的方式，環上所有奇點都能夠成為偶點，而且延伸出更多條交錯路徑。

一般圖的交錯樹，多了偶點到偶點的邊，奇點因此活躍了。

環上的所有奇點，可以搖身一變成為偶點，然後重新延伸出交錯路徑！ Blossom與Base 在交錯樹上，分岔的兩段交錯路徑，接上一條偶點到偶點的邊，所形成的奇數條邊的環，就稱作「花」。

花上兩條未匹配邊的銜接點，則稱作「花托」，宛如花開在交錯樹上。

BlossomContraction 既然花上的點都可以成為偶點，那麼乾脆把花直接縮成一個偶點，讓交錯樹更簡潔明白。

交錯樹上可能會有許多偶點到偶點的邊，形成許多朵重重疊疊的花，我們可以用任意順序縮花。

實作時，為了容易找到花，可以在建立交錯樹的途中，一旦發現偶點到偶點的邊就立即縮花。

一句話，一旦發現花就立即縮花。

縮花的次數呢？一朵花最少有三個點，縮花後成為一個點，前前後後少了兩個點。

由此推得：V個點的圖建立一棵交錯樹，最多縮花V/2次；如果再多縮幾朵花，樹上就沒有點了。

路徑沿著花繞來繞去，繞得你暈頭轉向。

演算法 一、一開始圖上所有點都是未匹配點。

二、每個未匹配點，依序嘗試作為擴充路徑的端點， 　　並以GraphTraversal建立交錯樹，以尋找擴充路徑。

　甲、走到未拜訪過的點： 　　a.如果是已匹配點，則延伸交錯樹，一條未匹配邊再加一條已匹配邊。

　　b.如果是未匹配點，則找到擴充路徑。

　乙、走到已拜訪過的點： 　　a.如果是偶點，形成花。

做花的處理。

　　b.如果是奇點，根據只需留一條路徑的性質，什麼都不必做。

花的處理： 一、找出花托：crossedge兩端點的LowestCommonAncestor。

二、建立從樹根到花上各奇點之交錯路徑。

　　一定會經過crossedge。

小心別重複經過花托。

三、把花上面的點全部當作偶點。

　　或者，乾脆把花直接縮成一個偶點。

　　縮花可用DisjointSets資料結構。

找出一個最大匹配 採用BFS建立交錯樹。

採用Array記錄交錯路徑，以大量Array紀錄交錯樹上每一條交錯路徑。

不縮花。

一、V個未匹配點分別建立交錯樹。

二、一棵交錯樹最多V條交錯路徑，一條交錯路徑長度最多V條邊。

三、一棵交錯樹最多E朵花，每朵花需要O(V)時間找花托。

時間複雜度O(V³+V²E)，通常簡單寫成O(V²E)。

constintV=50; //圖的點數 booladj[V][V]; //adjacencymatrix dequep[V]; //p[x]記錄了樹根到x點的交錯路徑。

intm[V]; //記錄各點所配對的點，值為-1為未匹配點。

intd[V]; //值為-1未拜訪、0偶點、1奇點。

intq[V],*qf,*qb; //queue，只塞入偶點。

//設定好由樹根至花上各個奇點的交錯路徑，並讓奇點變成偶點。

//只處理花的其中一邊。

//邊xy是crossedge。

b是花托。

voidlabel_one_side(intx,inty,intb) { for(inti=b+1;i>V; intx,y; while(cin>>x>>y) adj[x][y]=adj[y][x]=true; cout<