第15節(jié)偶圖與匹配.

1、集合集合論論與圖論與圖論1/29第第15節(jié)節(jié) 偶圖與匹配偶圖與匹配主要內(nèi)容主要內(nèi)容：l 偶圖偶圖l 匹配匹配集合集合論論與圖論與圖論2/29結婚結婚(婚配婚配)問題問題結婚問題結婚問題：已知由若干個小伙子組成的集合：已知由若干個小伙子組成的集合F，若干，若干個姑娘之集為個姑娘之集為G。姑娘們都渴望結婚，但也不希望媒。姑娘們都渴望結婚，但也不希望媒人介紹，隨便嫁給一個她不認識或不可接受的小伙人介紹，隨便嫁給一個她不認識或不可接受的小伙子。實際上，每個姑娘心中都有一張可接受為配偶子。實際上，每個姑娘心中都有一張可接受為配偶的小伙子名單。問在什么條件下才能把所有的姑娘的小伙子名單。問在什么條件下才能

2、把所有的姑娘都嫁出去？都嫁出去？對這個問題，若把姑娘和小伙對這個問題，若把姑娘和小伙子用點來表示，若某位姑娘能子用點來表示，若某位姑娘能接受某個小伙子，則在相應點接受某個小伙子，則在相應點間連一條線，則可以得到一個間連一條線，則可以得到一個無向圖無向圖G. 集合集合論論與圖論與圖論3/29工作安排問題工作安排問題工作安排問題：工作安排問題：一個車間有一個車間有m個工人和個工人和n件不同的工件不同的工作，每件工作只需一位工人干，而每位工人僅能熟作，每件工作只需一位工人干，而每位工人僅能熟練地干其中的幾件工作練地干其中的幾件工作. 問在什么條件下車間主任問在什么條件下車間主任能為每位工人分配一件他

3、能勝任的工作呢？能為每位工人分配一件他能勝任的工作呢？對這個問題，若把工人和每件對這個問題，若把工人和每件工作用點來表示，若一位工人工作用點來表示，若一位工人能勝任某項工作，則在相應點能勝任某項工作，則在相應點之間連一條線，則得到一個無之間連一條線，則得到一個無向圖向圖G.集合集合論論與圖論與圖論4/29偶圖偶圖(二部圖、雙圖二部圖、雙圖)定義定義1 G=(V, E)稱為稱為偶圖偶圖，如果，如果G的頂點集的頂點集V有一個二劃有一個二劃分分V1, V2，使得，使得G的任一條邊的兩個端點一個在的任一條邊的兩個端點一個在V1中，中，另一個在另一個在V2中中. 這個偶圖有時記為這個偶圖有時記為(V1,

4、 V2), E).定義定義1 G=(V, E), 如果能將如果能將V分成分成V1和和V2使得使得V1V2=V, V1V2=, 且且G中的每條邊的兩個端點都一個屬于中的每條邊的兩個端點都一個屬于V1, 另一個屬于另一個屬于V2.集合集合論論與圖論與圖論5/29 如果如果 u V1，v V2均有均有u, v E，則這個偶圖稱為，則這個偶圖稱為完全偶圖完全偶圖，并記為，并記為K(m, n)或或Km, n，其中，其中V1 =m， V2 =n.完全偶圖完全偶圖1、完全偶圖、完全偶圖Km,n有多少條邊有多少條邊?有有mn條邊條邊.2、完全偶圖中有沒有三角形、完全偶圖中有沒有三角形?沒有三角形沒有三角形.集

5、合集合論論與圖論與圖論6/29定義定義2 G=(V,E)是一個圖，是一個圖，u和和v是是G的頂點，聯(lián)結的頂點，聯(lián)結u和和v的的最短路的長稱為最短路的長稱為u與與v之間的距離，并記為之間的距離，并記為d(u,v).如果如果u與與v之間沒有路，則定義之間沒有路，則定義d(u, v)=.兩點之間的距離兩點之間的距離性質(zhì)：性質(zhì)：(1) d(u,v) 0, 且且d(u,v)=0 u=v.(2) d(u,v)=d(v,u).(3) d(u,v)+d(v,w) d(u,w).例如例如: a與與e之間的最短路：之間的最短路：ace，afe. d(a,e)=2, d(a,h)= 集合集合論論與圖論與圖論7/29

6、定理定理1 圖圖G為偶圖的充分必要條件是它的所有圈的長度為偶圖的充分必要條件是它的所有圈的長度都是偶數(shù)都是偶數(shù).證證: 必要性必要性設設P=u1u2u3.um-1umu1是是G的一個長為的一個長為m的圈。的圈。 因為因為G=(V, E)是一個偶圖，則是一個偶圖，則V存在一個二劃分存在一個二劃分V1,V2，對于任意，對于任意u,v E，u V1，v V2， 在圈在圈P中，若設中，若設u1 V1，那么所有圈上奇數(shù)下標，那么所有圈上奇數(shù)下標的的頂點都在頂點都在V1中，偶數(shù)下標的頂點全在中，偶數(shù)下標的頂點全在V2中，中，下標下標m必必然是偶數(shù)，也就是這個圈的長度為偶數(shù)然是偶數(shù)，也就是這個圈的長度為偶數(shù)

7、. 偶圖的判別定理偶圖的判別定理集合集合論論與圖論與圖論8/29充分性充分性 設設G的每個圈的長為偶數(shù)，需證的每個圈的長為偶數(shù)，需證G是偶圖是偶圖.不妨設不妨設G是連通圖，否則可分別考慮是連通圖，否則可分別考慮G的每個支的每個支.任取任取G的一個頂點的一個頂點u，定義集合，定義集合 V1=vv V，d(u,v)是偶數(shù)是偶數(shù)， V2=vv V，d(u,v)是奇數(shù)是奇數(shù)， 則則V1,V2是是V的一個二劃分，只要證明的一個二劃分，只要證明V1中任意二頂中任意二頂點間無邊，同時點間無邊，同時V2中任意兩頂點間也無邊即可中任意兩頂點間也無邊即可. 假設假設w與與v是是V1的兩個不同頂點，并且的兩個不同頂

8、點，并且v,w E，則令則令P是是u與與v間的最短路，間的最短路，Q為為u與與w間的最短路，間的最短路，u1為從為從u開始，開始，P與與Q的最后的一個公共頂點的最后的一個公共頂點.用反證法：用反證法： 偶圖的判別定理偶圖的判別定理集合集合論論與圖論與圖論9/29 因為因為P與與Q是最短路，所以是最短路，所以P和和Q上的上的u到到u1段也是段也是最短的最短的u與與u1間路間路. 設設P中從中從u1到到v的那一段為的那一段為P1，Q中中u1到到w的那一段的那一段為為Q1. 因為因為P與與Q都是偶數(shù)，因此都是偶數(shù)，因此P1與與Q1有相同的奇偶性有相同的奇偶性. 于是，邊于是，邊v,w， Q1，P1構

9、成構成G中一個奇數(shù)長的圈，中一個奇數(shù)長的圈，這與已知矛盾，所以這與已知矛盾，所以V1的任兩不同頂點的任兩不同頂點v與與w間無邊間無邊. 用完全一樣的方法可證用完全一樣的方法可證V2的任兩頂點間也沒邊，的任兩頂點間也沒邊，因此因此G是一個偶圖是一個偶圖.偶圖的判別定理偶圖的判別定理集合集合論論與圖論與圖論10/29不是偶圖不是偶圖不是不是偶圖偶圖實實 例例集合集合論論與圖論與圖論11/29匹匹 配配 定義定義3 設設G=(V,E)是一個圖，則是一個圖，則 (1)G的任兩條不相鄰的邊的任兩條不相鄰的邊x與與y稱為是互相獨立的稱為是互相獨立的. (2)若若Y E，且，且Y中任兩條邊都是互相獨立的，則

10、中任兩條邊都是互相獨立的，則稱稱Y為為G的一個的一個匹配匹配. (顯然，若顯然，若Y是圖是圖G的一個匹配，則任意的的一個匹配，則任意的vV，v至多與至多與Y 中的一條邊關聯(lián)中的一條邊關聯(lián).) (3)設設Y是圖是圖G的一個匹配，若對的一個匹配，若對G的任一匹配的任一匹配Y ，恒有恒有|Y |Y |，則稱，則稱Y是圖是圖G的一個的一個最大匹配最大匹配. 集合集合論論與圖論與圖論12/29定義定義4 設設G=(V,E)是一個偶圖且是一個偶圖且V=V1V2，對，對任意任意xE，x是連接是連接V1的一個頂點與的一個頂點與V2的一個頂?shù)囊粋€頂點的邊，則若存在一個點的邊，則若存在一個 匹配匹配Y使得使得|Y

11、|=min|V1|，|V2|，則稱則稱Y是偶圖是偶圖G的的完全匹配完全匹配.若若|V1|V2|，則稱，則稱Y為為G的一個的一個完美匹配完美匹配.說明：說明：(1)若偶圖若偶圖G有完全匹配，則有完全匹配，則Y必是必是G的最大匹的最大匹配，但反過來不一定；配，但反過來不一定；(2)若若G有完美匹配，則有完美匹配，則G的頂點數(shù)必是偶數(shù)并且的頂點數(shù)必是偶數(shù)并且對任意對任意v，Y中恰好有一條邊與中恰好有一條邊與v關聯(lián)關聯(lián). 匹匹 配配 集合集合論論與圖論與圖論13/29圖中，圖中，粗邊粗邊組成各圖的一個匹配組成各圖的一個匹配.(1)中為完全匹配，中為完全匹配，(2)中匹配不是中匹配不是完全匹配完全匹配，

12、(2)中無完全匹配，中無完全匹配，(3)中匹配是完全匹配，也是完美匹配中匹配是完全匹配，也是完美匹配. 匹匹 配配 集合集合論論與圖論與圖論14/29匹配問題匹配問題 結婚問題結婚問題：已知由若干個小伙子組成的集合：已知由若干個小伙子組成的集合F，若干，若干個姑娘之集為個姑娘之集為G。姑娘們都渴望結婚，但也不希望媒。姑娘們都渴望結婚，但也不希望媒人介紹，隨便嫁給一個她不認識或不可接受的小伙人介紹，隨便嫁給一個她不認識或不可接受的小伙子。實際上，每個姑娘心中都有一張可接受為配偶子。實際上，每個姑娘心中都有一張可接受為配偶的小伙子名單。問在什么條件下才能把所有的姑娘的小伙子名單。問在什么條件下才能

13、把所有的姑娘都嫁出去？都嫁出去？工作安排問題：工作安排問題：一個車間有一個車間有m個工人和個工人和n件不同的工件不同的工作，每件工作只需一位工人干，而每位工人僅能熟作，每件工作只需一位工人干，而每位工人僅能熟練地干其中的幾件工作練地干其中的幾件工作. 問在什么條件下車間主任問在什么條件下車間主任能為每位工人分配一件他能勝任的工作呢？能為每位工人分配一件他能勝任的工作呢？2個問題最終都抽象成偶圖的個問題最終都抽象成偶圖的完全匹配完全匹配是否存在是否存在的問題！的問題！集合集合論論與圖論與圖論15/29定理定理3(Hall定理定理, 1935年年) 設設G=(V1V2，E)是一個是一個偶圖，偶圖，

14、|V1|V2|. G中存在從中存在從V1到到V2的完全匹配的完全匹配充分必要條件充分必要條件是是V1中任意中任意k個頂點個頂點(k=1, 2, , |V1|)至少與至少與V2中的中的k個頂點相連接個頂點相連接. 該條件稱為該條件稱為相異性條件，相異性條件，Hall條件條件.Hall定理（相異性條件）定理（相異性條件）許多問題提出了偶圖的完全匹配的存在性問題許多問題提出了偶圖的完全匹配的存在性問題. .集合集合論論與圖論與圖論16/29例例1 現(xiàn)有現(xiàn)有4名教師：張、王、李、趙，要求他們?nèi)ッ處煟簭垺⑼?、李、趙，要求他們?nèi)?教教4門課程：數(shù)學、物理、電工和計算機科學門課程：數(shù)學、物理、電工和計算機

15、科學. 已已知張能教數(shù)學和計算機科學；王能教物理和電工；知張能教數(shù)學和計算機科學；王能教物理和電工；李能教數(shù)學、物理和電工；趙只能教電工李能教數(shù)學、物理和電工；趙只能教電工. 如何安如何安排才能使排才能使4位教師都能教課，并且每門課都有人位教師都能教課，并且每門課都有人教？共有幾種方案？教？共有幾種方案？ 解解: 設設V1=張、王、李、趙張、王、李、趙，V2=數(shù)學、物理、計數(shù)學、物理、計算機、電工算機、電工. 某人能教某課程就在相應的頂點之間某人能教某課程就在相應的頂點之間連一條線，得到一個偶圖連一條線，得到一個偶圖. 此偶圖此偶圖G滿足滿足“相異性相異性條條件件”，因此存在，因此存在V1到到

16、V2的完全匹配的完全匹配. 但因趙只能教電工，因而王只能教物理，李就只能但因趙只能教電工，因而王只能教物理，李就只能教數(shù)學，張也就只能教計算機科學了教數(shù)學，張也就只能教計算機科學了. 即方案只有即方案只有一種一種.實實 例例集合集合論論與圖論與圖論17/29實實 例例例例2 (派遣問題派遣問題)某課題組要從某課題組要從a, b, c, d, e 5人中派人中派3人分別到上海、廣州、香港去開會人分別到上海、廣州、香港去開會. 已知已知a只想去只想去海，海，b只想去廣州，只想去廣州，c, d, e都表示想去廣州或香港都表示想去廣州或香港. 問該課題組在滿足個人要求的條件下，共有幾種問該課題組在滿足

17、個人要求的條件下，共有幾種派遣方案？派遣方案？ 解：解：令令G=(V1V2,E)，其中其中V1=s, g, x，s, g, x分別表示上海、廣州分別表示上海、廣州和香港和香港. V2=a, b, c, d, e, E=(u,v) | u V1, v V2, v想去想去u. 共有共有9 種派遣方案種派遣方案.集合集合論論與圖論與圖論18/29匹配問題進一步分析匹配問題進一步分析 結婚問題結婚問題工作安排問題工作安排問題2個問題最終都抽象成偶圖的個問題最終都抽象成偶圖的完全匹配完全匹配是否存在是否存在的問題！的問題！如果完全匹配存在如果完全匹配存在 (Hall條件成立條件成立)，那么如何找，那么如

18、何找到完全匹配呢？到完全匹配呢？如果完全匹配不存在如果完全匹配不存在 (Hall條件成立條件成立)，那么如何，那么如何找到最大匹配呢？找到最大匹配呢？集合集合論論與圖論與圖論19/29穩(wěn)定婚配問題穩(wěn)定婚配問題2012年年10月月15日晚間，瑞典皇家科學院宣布，將日晚間，瑞典皇家科學院宣布，將2012年諾貝爾經(jīng)濟學獎授予年諾貝爾經(jīng)濟學獎授予阿爾文阿爾文E羅斯羅斯(Alvin E. Roth, 美國經(jīng)濟學家，哈佛大學商學院經(jīng)濟與商業(yè)管理學教美國經(jīng)濟學家，哈佛大學商學院經(jīng)濟與商業(yè)管理學教授授)和和羅伊德羅伊德S沙普利沙普利（Lloyd S. Shapley, 美國數(shù)學美國數(shù)學家、經(jīng)濟學家，加州大學洛

19、杉磯分校數(shù)學和經(jīng)濟學名家、經(jīng)濟學家，加州大學洛杉磯分校數(shù)學和經(jīng)濟學名譽教授譽教授)。授獎原因：穩(wěn)定分配理論和市場設計中的實踐。授獎原因：穩(wěn)定分配理論和市場設計中的實踐。2012年兩位經(jīng)濟學諾貝爾獎得主的年兩位經(jīng)濟學諾貝爾獎得主的“穩(wěn)定配置理論穩(wěn)定配置理論”是他們獲獎的基礎。這個理論在現(xiàn)實中，包括男女是他們獲獎的基礎。這個理論在現(xiàn)實中，包括男女婚姻搭配、病人和醫(yī)院的配置、學生和學校的選配、婚姻搭配、病人和醫(yī)院的配置、學生和學校的選配、病人互換捐腎者，等等，都有著廣泛的、富有現(xiàn)實病人互換捐腎者，等等，都有著廣泛的、富有現(xiàn)實意義的意義的“市場設計實踐市場設計實踐”。集合集合論論與圖論與圖論20/29

20、2012年諾貝爾經(jīng)濟學獎關注了一個經(jīng)濟學的中心問題年諾貝爾經(jīng)濟學獎關注了一個經(jīng)濟學的中心問題:如何盡可能恰當?shù)仄ヅ洳煌氖袌鲋黧w。如何盡可能恰當?shù)仄ヅ洳煌氖袌鲋黧w。比如比如: 學生須與學校相匹配，人體器官的捐獻者必須學生須與學校相匹配，人體器官的捐獻者必須同需要器官移植的患者相匹配。同需要器官移植的患者相匹配。怎樣才能使匹配盡可能有效地完成？怎樣才能使匹配盡可能有效地完成？什么樣的方法對什么樣的團體有益？什么樣的方法對什么樣的團體有益？2012年諾貝爾經(jīng)濟學獎授予的這兩位學者，分別從年諾貝爾經(jīng)濟學獎授予的這兩位學者，分別從穩(wěn)穩(wěn)定匹配定匹配的抽象理論和市場制度的實際設計這兩個角的抽象理論和市場

21、制度的實際設計這兩個角度，對這些問題作出了回答。度，對這些問題作出了回答。穩(wěn)定婚配問題穩(wěn)定婚配問題集合集合論論與圖論與圖論21/29穩(wěn)定婚配問題穩(wěn)定婚配問題羅伊德羅伊德S沙普利沙普利(Lloyd S. Shapley)使用合作博弈的方使用合作博弈的方法來法來研究和比對不同的匹配方法研究和比對不同的匹配方法。關鍵問題在于保證一個配對是穩(wěn)定的；關鍵問題在于保證一個配對是穩(wěn)定的；所謂穩(wěn)定，指的是兩個主體都無法找到比當前匹配的所謂穩(wěn)定，指的是兩個主體都無法找到比當前匹配的主體更佳的匹配對象。主體更佳的匹配對象。Shapley和他的同事找到了一個方法和他的同事找到了一個方法:GS算法算法(Gale-Sh

22、apley algorithm)亦稱亦稱 延遲認可算法延遲認可算法 這種方法能確保匹配是穩(wěn)定的。這種方法能確保匹配是穩(wěn)定的。集合集合論論與圖論與圖論22/29穩(wěn)定婚配問題穩(wěn)定婚配問題Shapley和已故的加州大學伯克利分校的數(shù)學及經(jīng)濟和已故的加州大學伯克利分校的數(shù)學及經(jīng)濟學學教授大衛(wèi)教授大衛(wèi)-蓋爾（蓋爾（David Gale, 1921-2008）于）于1962年發(fā)年發(fā)表的一篇相關論文：穩(wěn)定婚配問題表的一篇相關論文：穩(wěn)定婚配問題(Stable Marriage Problem)，是，是Shapley獲得經(jīng)濟學諾貝爾獎的最有革命獲得經(jīng)濟學諾貝爾獎的最有革命性的文章。性的文章。集合集合論論與圖論與

23、圖論23/29匈牙利算法匈牙利算法匈牙利算法匈牙利算法(Hungarian method)It was developed and published by Harold Kuhn in 1955, who gave the name Hungarian method because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dnes Knig and Jen Egervry.James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial. Since then the algorithm has been known also as KuhnMunkres algorithm or Munkres assignment algorithm. time complexity: O(n4)集合集合論論與圖論與圖論24/29匈牙利算法匈牙利算法匈牙利算法匈牙利算法(Hun