Hall定理-南京大學課件

二部圖中的匹配離散數(shù)學課程組南京大學計算機科學與技術系二部圖中的匹配離散數(shù)學課程組內容提要引言二部圖中完備匹配（Hall定理）二部圖中的最大匹配二部圖中的穩(wěn)定匹配內容提要引言孤島上的婚姻成就最多幸?；橐龅呐鋵Ψ桨富ゲ幌噜彽倪吋聧u上的婚姻成就最多幸?；橐龅呐鋵Ψ桨富ゲ幌噜彽倪吋瘓D中的匹配匹配（邊獨立集）：互不相鄰的邊的集合M-飽和點：M中各邊的端點匹配數(shù)1=3匹配數(shù)1=4極大匹配最大匹配完美匹配M-飽和點M-飽和點圖中的匹配匹配（邊獨立集）：互不相鄰的邊的集合匹配數(shù)匹配數(shù)極二部圖中的完備匹配定義：設G是二部圖，二部劃分為<V1,V2>，若G中的匹配M飽和V1中所有頂點，則稱M為V1到V2的完備匹配。注意：完備匹配一定是最大匹配，但僅當|V1|=|V2|才是完美匹配。無完備匹配？V1到V2的完備匹配存在完美匹配二部圖中的完備匹配定義：設G是二部圖，二部劃分為<V1,V二部圖中的完備匹配（舉例）V1={1,2,3,4,5,6},是否存在飽和V1的配對方案？A1B2C3D4E5F6G{A,C,F}{A,C}{A,F}{C,F}飽和{1,3,4,6}？二部圖中的完備匹配（舉例）V1={1,2,3,4,5Hall定理

Hall定理(1935,MarriageTheorem)

設二部圖G=<V1,V2,E>,則G有V1到V2的完備匹配

AV1

，|N(A)||A

|證明.必要性易證，下證充分性（使用強歸納法）。如果|V1|=1,充分性命題顯然成立。

假設當|V1|k(k1)時充分性命題均成立,要證:當|V1|=k+1時充分性命題也成立。分二種情形來證明。(1)對V1的任意真子集A，|N(A)||A

|

(2)存在V1的一個真子集A’，|N(A’)|=

|A’

|Hall定理Hall定理(1935,MarriageTHall定理

H滿足歸納假設的條件,從而

H有V1-{v}到V2-{w}的完備匹配.

這個匹配加上邊(v,w)構成G的從V1到V2的完備匹配.vw歸納證明.(1)對V1的任意真子集A,|N(A)||A

|

任取一個頂點vV1,任取wN({v}).H=G-{v,w}是一個二部圖（非空）.

Hall定理H滿足歸納假設的條件,從而vw歸納Hall定理

(2)存在V1的一個真子集A’,|N(A’)|=|A’

|.記B’=N(A’).據(jù)歸納假設,存在A’到B’的完備匹配.二部圖H=G-A’-B’滿足歸納假設條件.

A’B’否則,存在CV1-A’.|NH(C)|<|C|.|NG(CA’)||NH(C)|+|B’|<|C|+|B’|=|C|+|A’|=|CA’|.矛盾.據(jù)歸納假設,存在V1-A’到V2-B’的完備匹配.合并上述兩個匹配得到一個V1到V2的完備匹配.得證

Hall定理(2)存在V1的一個真子集A’,|N(A’Hall定理的推論設二部圖G是一個k-正則的(k1),則G有完美匹配.證明.不妨設G=<A,B,E>,k|A|=k|B|,所以|A|=|B|.下證G有A到B的完備匹配.

對任一SA，S與N(S)之間總共有k|S|條邊，而與N(S)相關的邊總共有k|N(S)|條邊?！?/p>

k|S|

k|N(S)|∴|N(S)||S|根據(jù)Hall定理，G有A到B的完備匹配，因|A|=|B|，該匹配是完美匹配。Hall定理的推論設二部圖G是一個k-正則的(k1),完備匹配的一個充分條件二部圖G=(V1,V2,E),若V1中每個頂點至少關聯(lián)t條邊，而若V2中每個頂點至多關聯(lián)t條邊，則G中存在V1到V2的完備匹配。證明類似于上述推論，t|S|…t|N(S)|。完備匹配的一個充分條件二部圖G=(V1,V2,E),若V交錯路徑與可增廣交錯路徑定義：設M是G中一個匹配。若G中路徑P中M與EG-M中的邊交替出現(xiàn)，則稱P為M-交錯路徑(也可以是回路)；若P的起點與終點都是M-非飽和點（沒有被匹配的頂點），則稱P是可增廣交錯路徑（增廣路徑）?？稍鰪V交錯路交錯路徑與可增廣交錯路徑定義：設M是G中一個匹配。若G中路徑最大匹配Berge’sLemma(1957).M是最大匹配

相對于M沒有增廣路徑

證明.容易證明必要性，下證充分性.

假設有一個更大的匹配M′.令G′=(V,M⊕M′).G′中各頂點的度最多為2.因此,G′的各連通分支要么是路徑(孤立點也看作路徑),要么是回路.無論是路徑還是回路，來自M的邊與來自M′的邊一定是交錯的.最大匹配Berge’sLemma(1957).M是最大最大匹配若是回路,來自M的邊數(shù)等于來自M′的邊數(shù).因為|M′||M|,故必有一條路徑包含M′的邊多于M的邊,從而是相對于M的增廣路徑.得證最大匹配若是回路,來自M的邊數(shù)等于來自M′的邊數(shù).因為增廣路徑的算法思想在二部圖中直接使用增廣路徑的匹配算法找增廣路徑,對M進行增廣,一直至沒有增廣路徑.復雜度O(|V||E|)，最大匹配的元素個數(shù)|V|/2增廣路徑的算法思想在二部圖中直接使用增廣路徑的匹配算法穩(wěn)定匹配（穩(wěn)定的婚姻）G的一個偏好集

一族線性序(v)vV，

其中，v是E(v)上的線性序。Unstable:IfMisamatchingande=(a,b)isanedgenotinMsuchthatbothaandbpreferetotheircurrentmatchingedge.egfab穩(wěn)定匹配（穩(wěn)定的婚姻）G的一個偏好集Unstable:If穩(wěn)定匹配（穩(wěn)定的婚姻）定理1.4.(Gale&Shapley1962)任意給定一個偏好集，二步圖G有一個穩(wěn)定的匹配。efevfefevfG中一個匹配M是穩(wěn)定的

對任意一個eE\M，存在

fM滿足：(i)e

和f

有公共端點v，(ii)evf.穩(wěn)定匹配（穩(wěn)定的婚姻）定理1.4.(Gale&Sha穩(wěn)定匹配（穩(wěn)定的婚姻）思路男子向尚未拒絕他的最喜愛的女子求婚.女子接受目前為止最如意的求婚提議，但是，倘若有更如意的求婚者，會改變主意。穩(wěn)定匹配（穩(wěn)定的婚姻）思路穩(wěn)定匹配（穩(wěn)定的婚姻）Example.Givenmenx,y,z,w,womena,b,c,d,andpreferenceslistedbelow,thematching{xa,yb,zd,wc}isastablematching.Men{x,y,z,w}Women{a,b,c,d}x:a>

b

>c>d

a:z>x>y

>wy:a

>c>b>d

b:y>

w>x

>

zz:c

>d>a>b

c:w>x>y>zw:

c>b>a>d

d:x>y>z>wXaYbZcWd穩(wěn)定匹配（穩(wěn)定的婚姻）Example.Givenmen穩(wěn)定匹配（穩(wěn)定的婚姻）x:a>

b

>c>d

a:z>x>y

>wy:a

>c>b>d

b:y>

w>x

>

zz:c

>d>a>b

c:w>x>y>zw:

c>b>a>d

d:x>y>z>wXaYbZcWdY穩(wěn)定匹配（穩(wěn)定的婚姻）x:a>b>c>d穩(wěn)定匹配（穩(wěn)定的婚姻）術語給定M，a∈A可被b∈B接受(a,b)∈E\M，并且若存在(a’,b)∈M,則(a’,b)b(a,b).a∈A對M滿意a是一個尚未配對的頂點，或者存在(a,b)∈M,若a可被b’接受，則(a,b)>a(a,b’)穩(wěn)定匹配（穩(wěn)定的婚姻）術語給定M，a∈A可被b∈B接受穩(wěn)定匹配（穩(wěn)定的婚姻）算法從一個空的邊集開始，構造（更新）匹配M，保持“A中的所有頂點對M滿意”這一特性。給定這樣的一個M,對于A中尚未配對的某頂點a，若{(a,b)|a可被b接受}非空.按照線性序≤a找出最大元，記為(a,bj)，將這條邊添加到M中，刪除M中以bj為端點的邊（假如有的話）。對于A中尚未配對的所有頂點a，{(a,b)|a可被b接受}均為空.（結束）穩(wěn)定匹配（穩(wěn)定的婚姻）算法從一個空的邊集開始，構造（更新穩(wěn)定匹配（穩(wěn)定的婚姻）算法正確性分析結束之時A中的所有頂點對M滿意A中未配對的頂點均沒有可被接受的對象結束之時，M是穩(wěn)定的

對任意一個eE\M，存在fM滿足

：(i)e和f有公共端點;(ii)evf.egf穩(wěn)定匹配（穩(wěn)定的婚姻）算法正確性分析結束之時egf穩(wěn)定匹配（穩(wěn)定的婚姻）算法正確性分析算法是否會結束？M越來越好，至于不能更好。何為“好”:M比M’好對于B中任一頂點b，若b是某個邊f(xié)’∈M’的端點，則b必是某個邊f(xié)∈M的端點，且f’≤b

f.（B中頂點有更好的配對）穩(wěn)定匹配（穩(wěn)定的婚姻）算法正確性分析算法是否會結束？工作分配問題問題：n個畢業(yè)生有可供選擇的m個崗位，每個畢業(yè)生給出若干個志愿，是否存在每個人都滿意的分配方案。數(shù)學模型：建立二部圖，V1中每個點對應一個畢業(yè)生，V2中每個點對應一個可選的崗位，uvE當且僅當u對應的畢業(yè)生愿意選擇v對應的崗位。問題的解：問題有解當且僅當G有飽和V1中所有頂點的完備匹配。工作分配問題問題：n個畢業(yè)生有可供選擇的m個崗位，每個畢業(yè)生工作分配問題的一般形式工作分配問題某機構提供m個空缺職位,有n個申請者。每個申請者滿足某些職位的要求。是否可能使每個申請者得到一個他/她適合的職位？若不能，最多多少申請者能夠被分配到合適的職位？如何實現(xiàn)一個最佳分配方案？工作分配問題的一般形式工作分配問題工作分配問題的求解模型AaiBbj......申請者集合職位的集合aibjEG

iff.ai

適合于bj在此模型中如何解釋問題的解？工作分配問題的求解模型AaiBbj......申請者集合職位棋盤上的士兵要在左圖所示的棋盤上放置4個士兵，任何一行或者一列恰好放一個，但不能放在有標記的格子中。構造一個二步圖，ai表示行，bi表示列。aibj

E

當且僅當?shù)趇行第j列的方格沒有標記。oooo棋盤上的士兵要在左圖所示的棋盤上放置4個士兵，任何一行或者一作業(yè)教材[9.2]p.468：27,28作業(yè)教材[9.2]Exercise(II)從下圖G=(A,B,E)中,找出相對于匹配M(粗邊的集合)的任意三條交錯路徑(alternatingpath)和兩條增廣路徑(augmentingpath)。然后利用找出的增廣路徑擴大M.a0a1a2a3a4a5b0b1b2b3b4b5Exercise(II)從下圖G=(A,B,E)中,找出Exercise(II)對于每一個二部圖G=(A,B,E),判斷G是否有飽和A的匹配。如果沒有，請說明理由a0a1a2a3b2b1b0AB1)a0a1a2b3b2b1b0AB2)a0a1a2a3b2b1b0AB3)a4b3b4b5a0a1a2a3b2b1b0AB4)a4b3b4Exercise(II)對于每一個二部圖G=(A,B,E)Exercise(II)3.令k為一整數(shù)。對于任意有限集合，證明對它的任意兩個ｋ劃分

都存在一個相同的代表集。

說明：１）ｋ劃分指劃分為大小相同的互不想交的ｋ個子集，為簡便起見，設集合的大小為ｋ的整數(shù)倍從而每個子集均有相同個元素。２）一個劃分的代表集指從每個子集中取出一個元素而構成的集合。

舉例：集合{1,2,3,4}的一個２劃分為A:{1,2}{3,4}.此劃分的代表集有{1,3}，{2,3}，{1,4}，{2,4},但{1,2}不是其代表集.集合的另外一個劃分為B:{2,3}{1,4}.易見，Ａ與Ｂ存在相同的代表集{1,3}?？梢栽囼?，任意兩個２劃分均存在相同的代表集。Exercise(II)3.令k為一整數(shù)。對于任意有限集拓展題4.找出一個二部圖和一組偏好(preference),使得在此圖中所有最大匹配均不是穩(wěn)定匹配而所有穩(wěn)定匹配均不是最大匹配（Findabipartitegraphandasetofpreferencessuchthatnomatchingofmaximalsizeisstableandnostablematchinghasmaximalsize.）5.找出一個非二部圖（non-bipartitegraph）和一組偏好，使得圖中不存在穩(wěn)定匹配。拓展題4.找出一個二部圖和一組偏好(preference)Q&A參考文獻ReinhardDiestel.GraphTheory.Springer,Heidelberg,2005Q&A參考文獻二部圖中的匹配離散數(shù)學課程組南京大學計算機科學與技術系二部圖中的匹配離散數(shù)學課程組內容提要引言二部圖中完備匹配（Hall定理）二部圖中的最大匹配二部圖中的穩(wěn)定匹配內容提要引言孤島上的婚姻成就最多幸?；橐龅呐鋵Ψ桨富ゲ幌噜彽倪吋聧u上的婚姻成就最多幸?；橐龅呐鋵Ψ桨富ゲ幌噜彽倪吋瘓D中的匹配匹配（邊獨立集）：互不相鄰的邊的集合M-飽和點：M中各邊的端點匹配數(shù)1=3匹配數(shù)1=4極大匹配最大匹配完美匹配M-飽和點M-飽和點圖中的匹配匹配（邊獨立集）：互不相鄰的邊的集合匹配數(shù)匹配數(shù)極二部圖中的完備匹配定義：設G是二部圖，二部劃分為<V1,V2>，若G中的匹配M飽和V1中所有頂點，則稱M為V1到V2的完備匹配。注意：完備匹配一定是最大匹配，但僅當|V1|=|V2|才是完美匹配。無完備匹配？V1到V2的完備匹配存在完美匹配二部圖中的完備匹配定義：設G是二部圖，二部劃分為<V1,V二部圖中的完備匹配（舉例）V1={1,2,3,4,5,6},是否存在飽和V1的配對方案？A1B2C3D4E5F6G{A,C,F}{A,C}{A,F}{C,F}飽和{1,3,4,6}？二部圖中的完備匹配（舉例）V1={1,2,3,4,5Hall定理

Hall定理(1935,MarriageTheorem)

設二部圖G=<V1,V2,E>,則G有V1到V2的完備匹配

AV1

，|N(A)||A

|證明.必要性易證，下證充分性（使用強歸納法）。如果|V1|=1,充分性命題顯然成立。

假設當|V1|k(k1)時充分性命題均成立,要證:當|V1|=k+1時充分性命題也成立。分二種情形來證明。(1)對V1的任意真子集A，|N(A)||A

|

(2)存在V1的一個真子集A’，|N(A’)|=

|A’

|Hall定理Hall定理(1935,MarriageTHall定理

H滿足歸納假設的條件,從而

H有V1-{v}到V2-{w}的完備匹配.

這個匹配加上邊(v,w)構成G的從V1到V2的完備匹配.vw歸納證明.(1)對V1的任意真子集A,|N(A)||A

|

任取一個頂點vV1,任取wN({v}).H=G-{v,w}是一個二部圖（非空）.

Hall定理H滿足歸納假設的條件,從而vw歸納Hall定理

(2)存在V1的一個真子集A’,|N(A’)|=|A’

|.記B’=N(A’).據(jù)歸納假設,存在A’到B’的完備匹配.二部圖H=G-A’-B’滿足歸納假設條件.

A’B’否則,存在CV1-A’.|NH(C)|<|C|.|NG(CA’)||NH(C)|+|B’|<|C|+|B’|=|C|+|A’|=|CA’|.矛盾.據(jù)歸納假設,存在V1-A’到V2-B’的完備匹配.合并上述兩個匹配得到一個V1到V2的完備匹配.得證

Hall定理(2)存在V1的一個真子集A’,|N(A’Hall定理的推論設二部圖G是一個k-正則的(k1),則G有完美匹配.證明.不妨設G=<A,B,E>,k|A|=k|B|,所以|A|=|B|.下證G有A到B的完備匹配.

對任一SA，S與N(S)之間總共有k|S|條邊，而與N(S)相關的邊總共有k|N(S)|條邊?！?/p>

k|S|

k|N(S)|∴|N(S)||S|根據(jù)Hall定理，G有A到B的完備匹配，因|A|=|B|，該匹配是完美匹配。Hall定理的推論設二部圖G是一個k-正則的(k1),完備匹配的一個充分條件二部圖G=(V1,V2,E),若V1中每個頂點至少關聯(lián)t條邊，而若V2中每個頂點至多關聯(lián)t條邊，則G中存在V1到V2的完備匹配。證明類似于上述推論，t|S|…t|N(S)|。完備匹配的一個充分條件二部圖G=(V1,V2,E),若V交錯路徑與可增廣交錯路徑定義：設M是G中一個匹配。若G中路徑P中M與EG-M中的邊交替出現(xiàn)，則稱P為M-交錯路徑(也可以是回路)；若P的起點與終點都是M-非飽和點（沒有被匹配的頂點），則稱P是可增廣交錯路徑（增廣路徑）?？稍鰪V交錯路交錯路徑與可增廣交錯路徑定義：設M是G中一個匹配。若G中路徑最大匹配Berge’sLemma(1957).M是最大匹配

相對于M沒有增廣路徑

證明.容易證明必要性，下證充分性.

假設有一個更大的匹配M′.令G′=(V,M⊕M′).G′中各頂點的度最多為2.因此,G′的各連通分支要么是路徑(孤立點也看作路徑),要么是回路.無論是路徑還是回路，來自M的邊與來自M′的邊一定是交錯的.最大匹配Berge’sLemma(1957).M是最大最大匹配若是回路,來自M的邊數(shù)等于來自M′的邊數(shù).因為|M′||M|,故必有一條路徑包含M′的邊多于M的邊,從而是相對于M的增廣路徑.得證最大匹配若是回路,來自M的邊數(shù)等于來自M′的邊數(shù).因為增廣路徑的算法思想在二部圖中直接使用增廣路徑的匹配算法找增廣路徑,對M進行增廣,一直至沒有增廣路徑.復雜度O(|V||E|)，最大匹配的元素個數(shù)|V|/2增廣路徑的算法思想在二部圖中直接使用增廣路徑的匹配算法穩(wěn)定匹配（穩(wěn)定的婚姻）G的一個偏好集

一族線性序(v)vV，

其中，v是E(v)上的線性序。Unstable:IfMisamatchingande=(a,b)isanedgenotinMsuchthatbothaandbpreferetotheircurrentmatchingedge.egfab穩(wěn)定匹配（穩(wěn)定的婚姻）G的一個偏好集Unstable:If穩(wěn)定匹配（穩(wěn)定的婚姻）定理1.4.(Gale&Shapley1962)任意給定一個偏好集，二步圖G有一個穩(wěn)定的匹配。efevfefevfG中一個匹配M是穩(wěn)定的

對任意一個eE\M，存在

fM滿足：(i)e

和f

有公共端點v，(ii)evf.穩(wěn)定匹配（穩(wěn)定的婚姻）定理1.4.(Gale&Sha穩(wěn)定匹配（穩(wěn)定的婚姻）思路男子向尚未拒絕他的最喜愛的女子求婚.女子接受目前為止最如意的求婚提議，但是，倘若有更如意的求婚者，會改變主意。穩(wěn)定匹配（穩(wěn)定的婚姻）思路穩(wěn)定匹配（穩(wěn)定的婚姻）Example.Givenmenx,y,z,w,womena,b,c,d,andpreferenceslistedbelow,thematching{xa,yb,zd,wc}isastablematching.Men{x,y,z,w}Women{a,b,c,d}x:a>

b

>c>d

a:z>x>y

>wy:a

>c>b>d

b:y>

w>x

>

zz:c

>d>a>b

c:w>x>y>zw:

c>b>a>d

d:x>y>z>wXaYbZcWd穩(wěn)定匹配（穩(wěn)定的婚姻）Example.Givenmen穩(wěn)定匹配（穩(wěn)定的婚姻）x:a>

b

>c>d

a:z>x>y

>wy:a

>c>b>d

b:y>

w>x

>

zz:c

>d>a>b

c:w>x>y>zw:

c>b>a>d

d:x>y>z>wXaYbZcWdY穩(wěn)定匹配（穩(wěn)定的婚姻）x:a>b>c>d穩(wěn)定匹配（穩(wěn)定的婚姻）術語給定M，a∈A可被b∈B接受(a,b)∈E\M，并且若存在(a’,b)∈M,則(a’,b)b(a,b).a∈A對M滿意a是一個尚未配對的頂點，或者存在(a,b)∈M,若a可被b’接受，則(a,b)>a(a,b’)穩(wěn)定匹配（穩(wěn)定的婚姻）術語給定M，a∈A可被b∈B接受穩(wěn)定匹配（穩(wěn)定的婚姻）算法從一個空的邊集開始，構造（更新）匹配M，保持“A中的所有頂點對M滿意”這一特性。給定這樣的一個M,對于A中尚未配對的某頂點a，若{(a,b)|a可被b接受}非空.按照線性序≤a找出最大元，記為(a,bj)，將這條邊添加到M中，刪除M中以bj為端點的邊（假如有的話）。對于A中尚未配對的所有頂點a，{(a,b)|a可被b接受}均為空.（結束）穩(wěn)定匹配（穩(wěn)定的婚姻）算法從一個空的邊集開始，構造（更新穩(wěn)定匹配（穩(wěn)定的婚姻）算法正確性分析結束之時A中的所有頂點對M滿意A中未配對的頂點均沒有可被接受的對象結束之時，M是穩(wěn)定的

對任意一個eE\M，存在fM滿足

：(i)e和f有公共端點;(ii)evf.egf穩(wěn)定匹配（穩(wěn)定的婚姻）算法正確性分析結束之時egf穩(wěn)定匹配（穩(wěn)定的婚姻）算法正確性分析算法是否會結束？M越來越好，至于不能更好。何為“好”:M比M’好對于B中任一頂點b，若b是某個邊f(xié)’∈M’的端點，則b必是某個邊f(xié)∈M的端點，且f’≤b

f.（B中頂點有更好的配對）穩(wěn)定匹配（穩(wěn)定的婚姻）算法正確性分析算法是否會結束？工作分配問題問題：n個畢業(yè)生有可供選擇的m個崗位，每個畢業(yè)生給出若干個志愿，是否存在每個人都滿意的分配方案。數(shù)學模型：建立二部圖，V1中每個點對應一個畢業(yè)生，V2中每個點對應一個可選的崗位，uvE當且僅當u對應的畢業(yè)生愿意選擇v對應的崗位。問題的解：問題有解當且僅當G有飽和V1中所有頂點的完備匹配。工作分配問題問題：n個畢業(yè)生有可供選擇的m個崗位，每個畢業(yè)生工作分配問題的一般形式工作分配問題某機構提供m個空缺職位,有n個申請者。每個申請者滿足某些職位的要求。是否可能使每個申請者得到一個他/她適合的職位？若不能，最多多少申請者能夠被分配到合適的職位？如何實現(xiàn)一個最佳分配方案？工作分配問題的一般形式工作分配問題工作分配問題的求解模型AaiBbj......申請者集合職位的集合aibjEG

iff.ai

適合于bj在此模型中如何解釋問題的解？工作分配問題的求解模型AaiBbj......申請者集合職位棋盤上的士兵要在左圖所示的棋盤上放置4個士兵，任何一行或者一列恰好放一個，但不能放在有標記的格子中。構造一個二步