Hall定理-南京大學(xué)課件

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

Hall定理(1935,MarriageTheorem)

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

AV1

，|N(A)||A

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

假設(shè)當(dāng)|V1|k(k1)時(shí)充分性命題均成立,要證:當(dāng)|V1|=k+1時(shí)充分性命題也成立。分二種情形來(lái)證明。(1)對(duì)V1的任意真子集A，|N(A)||A

|

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

|A’

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

H滿足歸納假設(shè)的條件,從而

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

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

|

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

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

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

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

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

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

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

k|S|

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

相對(duì)于M沒(méi)有增廣路徑

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

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

一族線性序(v)vV，

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

對(duì)任意一個(gè)eE\M，存在

fM滿足：(i)e

和f

有公共端點(diǎn)v，(ii)evf.穩(wěn)定匹配（穩(wěn)定的婚姻）定理1.4.(Gale&Sha穩(wěn)定匹配（穩(wěn)定的婚姻）思路男子向尚未拒絕他的最喜愛(ài)的女子求婚.女子接受目前為止最如意的求婚提議，但是，倘若有更如意的求婚者，會(huì)改變主意。穩(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)定的婚姻）術(shù)語(yǔ)給定M，a∈A可被b∈B接受(a,b)∈E\M，并且若存在(a’,b)∈M,則(a’,b)b(a,b).a∈A對(duì)M滿意a是一個(gè)尚未配對(duì)的頂點(diǎn)，或者存在(a,b)∈M,若a可被b’接受，則(a,b)>a(a,b’)穩(wěn)定匹配（穩(wěn)定的婚姻）術(shù)語(yǔ)給定M，a∈A可被b∈B接受穩(wěn)定匹配（穩(wěn)定的婚姻）算法從一個(gè)空的邊集開(kāi)始，構(gòu)造（更新）匹配M，保持“A中的所有頂點(diǎn)對(duì)M滿意”這一特性。給定這樣的一個(gè)M,對(duì)于A中尚未配對(duì)的某頂點(diǎn)a，若{(a,b)|a可被b接受}非空.按照線性序≤a找出最大元，記為(a,bj)，將這條邊添加到M中，刪除M中以bj為端點(diǎn)的邊（假如有的話）。對(duì)于A中尚未配對(duì)的所有頂點(diǎn)a，{(a,b)|a可被b接受}均為空.（結(jié)束）穩(wěn)定匹配（穩(wěn)定的婚姻）算法從一個(gè)空的邊集開(kāi)始，構(gòu)造（更新穩(wěn)定匹配（穩(wěn)定的婚姻）算法正確性分析結(jié)束之時(shí)A中的所有頂點(diǎn)對(duì)M滿意A中未配對(duì)的頂點(diǎn)均沒(méi)有可被接受的對(duì)象結(jié)束之時(shí)，M是穩(wěn)定的

對(duì)任意一個(gè)eE\M，存在fM滿足

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

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

iff.ai

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

E

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

都存在一個(gè)相同的代表集。

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

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

Hall定理(1935,MarriageTheorem)

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

AV1

，|N(A)||A

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

假設(shè)當(dāng)|V1|k(k1)時(shí)充分性命題均成立,要證:當(dāng)|V1|=k+1時(shí)充分性命題也成立。分二種情形來(lái)證明。(1)對(duì)V1的任意真子集A，|N(A)||A

|

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

|A’

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

H滿足歸納假設(shè)的條件,從而

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

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

|

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

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

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

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

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

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

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

k|S|

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

相對(duì)于M沒(méi)有增廣路徑

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

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

一族線性序(v)vV，

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

對(duì)任意一個(gè)eE\M，存在

fM滿足：(i)e

和f

有公共端點(diǎn)v，(ii)evf.穩(wěn)定匹配（穩(wěn)定的婚姻）定理1.4.(Gale&Sha穩(wěn)定匹配（穩(wěn)定的婚姻）思路男子向尚未拒絕他的最喜愛(ài)的女子求婚.女子接受目前為止最如意的求婚提議，但是，倘若有更如意的求婚者，會(huì)改變主意。穩(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)定的婚姻）術(shù)語(yǔ)給定M，a∈A可被b∈B接受(a,b)∈E\M，并且若存在(a’,b)∈M,則(a’,b)b(a,b).a∈A對(duì)M滿意a是一個(gè)尚未配對(duì)的頂點(diǎn)，或者存在(a,b)∈M,若a可被b’接受，則(a,b)>a(a,b’)穩(wěn)定匹配（穩(wěn)定的婚姻）術(shù)語(yǔ)給定M，a∈A可被b∈B接受穩(wěn)定匹配（穩(wěn)定的婚姻）算法從一個(gè)空的邊集開(kāi)始，構(gòu)造（更新）匹配M，保持“A中的所有頂點(diǎn)對(duì)M滿意”這一特性。給定這樣的一個(gè)M,對(duì)于A中尚未配對(duì)的某頂點(diǎn)a，若{(a,b)|a可被b接受}非空.按照線性序≤a找出最大元，記為(a,bj)，將這條邊添加到M中，刪除M中以bj為端點(diǎn)的邊（假如有的話）。對(duì)于A中尚未配對(duì)的所有頂點(diǎn)a，{(a,b)|a可被b接受}均為空.（結(jié)束）穩(wěn)定匹配（穩(wěn)定的婚姻）算法從一個(gè)空的邊集開(kāi)始，構(gòu)造（更新穩(wěn)定匹配（穩(wěn)定的婚姻）算法正確性分析結(jié)束之時(shí)A中的所有頂點(diǎn)對(duì)M滿意A中未配對(duì)的頂點(diǎn)均沒(méi)有可被接受的對(duì)象結(jié)束之時(shí)，M是穩(wěn)定的

對(duì)任意一個(gè)eE\M，存在fM滿足

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

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

iff.ai

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