資源描述：
《二分圖匹配及其應》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、二分圖匹配及其應用劉汝佳目錄增廣路定理與Hall定理二分圖最大基數(shù)匹配二分圖最大權匹配應用二分圖最大匹配二分圖：結點可以分為兩部分X和Y，每部分內部無邊相連匹配：無公共點的邊集合未蓋點：不與任何匹配邊鄰接的點最大匹配：包含邊數(shù)最多的匹配XY增廣路從未蓋點開始經過非匹配邊、匹配邊、非匹配邊……序列，最終通過一條非匹配邊到達另一個未蓋點非匹配邊個數(shù)比匹配邊個數(shù)多一如果把匹配邊和非匹配邊互換…匹配仍合法，但基數(shù)加一增廣路定理匹配是最大匹配當且僅當不存在增廣路這個定理適用于任意圖011001011010匈牙利樹思
2、考：忽略虛線邊會導致存在增廣路卻找不到嗎？增廣路定理的證明必要性.如果存在則增廣后得到更大匹配.充分性.如果M不是最大匹配,取最大匹配M’,作M’和M的對稱差G’,則G’在M’中的邊應比M’中更多.G’有三種可能的連通分支孤立點.當某邊(u,v)同時屬于兩個匹配,則u和v都是孤立點.交互回路.該回路中屬于M和M’的邊數(shù)相同交互道路.如果不存在增廣路,則
3、M’
4、=
5、M
6、,與假設矛盾;如果存在M關于M’的增廣路,又與M’是最大匹配矛盾,因此存在M’關于M的增廣路Hall定理在二分圖(X,Y,E)中,X到Y存在
7、完全匹配(X的結點全被匹配)的充要條件是對于X的任意子集A,恒有必要性.若存在A使得右邊>左邊,則A無法全部匹配充分性.假設G的最大匹配M不是完全匹配,一定存在結點X的結點x0關于M是非飽和點.如果x0的鄰集為空,則令A={x0}引出矛盾;如果非空則其中每個結點均為飽和點(否則會有增廣路).尋找與x0為端點的關于M的一切交錯路,設其中Y結點的集合為Y’,X結點的集合為X’,則Y’結點與X’-{x0}的結點一一對應,因此
8、X’
9、>
10、Y’
11、,令A=X’引出矛盾.二分圖最大匹配算法匈牙利樹是從所有未蓋點,而不是
12、從固定未蓋點長出的樹Edmonds-Karp算法:把所有未蓋點放到隊列中,BFS尋找/增廣路時間均為O(m)最多找O(n)次時間復雜度O(nm)Hopcroft算法：每次沿多條增廣路同時增廣每次尋找若干條結點不相交最短增廣路每次的最短增廣路集是極大的時間復雜度基于DFS的算法:每次選一個未蓋點u進行DFS.如果找不到增廣路則換一個未蓋點,且以后再也不從u出發(fā)找增廣路.Hopcroft算法可以證明：如果每次找到的最短增廣路集是極大的，則只需要增廣次關鍵：用O(m)時間找一個極大最短增廣路集步驟1：用距離標號
13、擴展匈牙利樹，找到第一個未蓋點時并不停止，把此時的距離標號設為上限。這樣，找到的所有未蓋點距離標號都相同步驟2：每次任取一個未蓋點，用DFS找到它到起點的增廣路(只沿著距離標號下降的方向),標記經過的點,找所有增廣路的總時間為O(m)基于DFS的算法從貪心匹配,而不是空匹配開始每次從一個未蓋點開始DFS找增廣路,而不是一次性把所有未蓋點放入隊列進行BFS如果從一個未蓋點u開始找不到增廣路,則以后再也不用考慮u了.為什么?定理:假設G的匹配為M,不存在從非飽和點u出發(fā)的增廣路,而存在另外一條增廣路P,則G也
14、不存在從u出發(fā)關于增廣后新匹配的增廣路定理的證明(1)定理:假設G的匹配為M,不存在從非飽和點u出發(fā)的增廣路,而存在另外一條增廣路P,則G也不存在從u出發(fā)關于增廣后新匹配M’的增廣路證明:假設增廣后從u出發(fā)有增廣路Q.若Q與P不相交,則Q就是M-增廣路,矛盾.因此Q與P相交.下面借助P和Q構造出從u出發(fā)關于M的增廣路,從而得到矛盾定理的證明(2)Q與P相交.設P的兩個M-非飽和點為u0和v0,而Q的兩個M’-非飽和點是u,v.從u開始沿Q走,設第一個P中結點為w,則w把P分為兩段,其中必有一段以M中邊與w
15、關聯(lián),得到從u出發(fā)增廣路wv0u0vuPQ完全二分圖的最大權完美匹配完全二分圖，每條邊有一個非負整數(shù)權值目標：求出權和最大的完美匹配特點：完美匹配容易求，但權最大的不易可行頂標：結點函數(shù)l，對任意弧(x,y)滿足相等子圖：G的生成子圖，包含所有點，但只包含滿足l(x)+l(y)=w(x,y)的所有弧(x,y)相等子圖定理：如果相等子圖有完美匹配，則該匹配是原圖的最大權匹配證明：設M*是相等子圖的完美匹配，則根據定義設M是原圖的任意完美匹配，則關鍵：尋找好的可行頂標，使相等子圖有完美匹配算法思想關鍵：尋找好
16、的可行頂標，使相等子圖有完美匹配思想：隨便構造一個可行頂標（例如Y結點頂標為0，X結點的頂標為它出發(fā)所有弧的最大權值，然后求相等子圖的最大匹配存在完美匹配，算法終止否則修改頂標使得相等子圖的邊變多，有更大機會存在完美匹配考慮相等子圖不存在完美匹配時的情形Kuhn-Munkres算法如右圖，相等子圖的最大匹配基數(shù)為6，不是完美匹配算法在尋找增廣路失敗的同時得到了一棵匈牙利樹雖然此匈牙利樹并沒有包含未蓋點（因此沒有找到增廣路），但
