工學(xué)圖論-的配對問題課件

第五章匹配第五章匹配1§1最大匹配－1具體問題描述：有n個女士和n個男士參加舞會，每位女士與其中若干位男士相識，每位男士與其中若干位女士相識，問如何安排，使得盡量多配對的男女舞伴相識。f1f2m1f3f4f5m2m3m4m5§1匹配§1最大匹配－1具體問題描述：f1f2m1f3f4f2§1最大匹配－1下圖就是一種分配方法：f1f2m1f3f4f5m2m3m4m5(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)§1最大匹配－1下圖就是一種分配方法：f1f2m1f3匹配問題是運(yùn)籌學(xué)的重要問題之一，也是圖論的重要內(nèi)容，它在所謂“人員分配問題”和“最優(yōu)分配問題”中有重要作用。假定有一個男生有窮集合，其中每個男生認(rèn)識一些女生，在什么條件下每個男生都可以和他認(rèn)識的女生配對？類似的工作分配問題：現(xiàn)有n個人，m份工作，每個人有其擅長的工作。在什么條件下每個人都可以得到一份他擅長的工作？如何分配？匹配問題是運(yùn)籌學(xué)的重要問題之一，也是圖論的4§1最大匹配－定義定義：若圖G=(V,E)的頂點(diǎn)可以分成X，Y兩個子集，每個子集里的頂點(diǎn)互不相鄰，這樣的圖稱為二分圖。f1f2m1f3f4f5m2m3m4m5§1最大匹配－定義定義：若圖G=(V,E)的頂點(diǎn)可以5§1最大匹配－定義1定義：若M是圖G=(V,E)的邊子集，且M中的任意兩條邊在G中不相鄰，則稱M為G中的一個匹配，M中的每條邊的兩個端點(diǎn)稱為是M-飽和的的。f1f2m1f3f4f5m2m3m4m5M={(f1,m2),(f2,m1),(f3,m4),(f4,m5)}§1最大匹配－定義1定義：若M是圖G=(V,E)的邊6§1最大匹配－定義2定義：若圖G中每個頂點(diǎn)均被M許配時(shí)，稱M為G中的一個完美匹配。f1f2m1f3f4f5m2m3m4m5M={(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)}§1最大匹配－定義2定義：若圖G中每個頂點(diǎn)均被M許配7§1最大匹配－定義3定義：圖G中邊數(shù)最多的匹配M，稱為G中的一個最大匹配。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m5§1最大匹配－定義3定義：圖G中邊數(shù)最多的匹配M，稱8§1最大匹配－定義4定義：若匹配M的某邊和頂點(diǎn)v關(guān)聯(lián)，稱v是M-飽和的，否則就是M-不飽和的。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m5飽和的不飽和的§1最大匹配－定義4定義：若匹配M的某邊和頂點(diǎn)v關(guān)聯(lián)9§1最大匹配－定義5定義：若M是圖G的一個匹配，若從G中一個頂點(diǎn)到另一個頂點(diǎn)存在一條道路，此路徑由屬于M和不屬于M的邊交替出現(xiàn)組成的，則稱此路徑為M-交錯路。f1f2m1f3f4f5m2m3m4m5M={(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)}P=f1m3f4m5f2m1f5m4§1最大匹配－定義5定義：若M是圖G的一個匹配，若從10§1最大匹配－定義6定義：若交錯路的兩個端點(diǎn)為關(guān)于M的不飽和頂點(diǎn)時(shí)，稱此交互道為可增廣道路。M={(f2,m5),(f3,m2),(f4,m3),(f5,m4)}P=m1f2m5f4m3f1是一條可增廣道路。f1f2m1f3f4f5m2m3m4m5f1f2m1f3f4f5m2m3m4m5§1最大匹配－定義6定義：若交錯路的兩個端點(diǎn)為關(guān)于M11§1最大匹配－定義8f1f2m1f3f4f5m2m3m4m5M={(f2,m5),(f3,m2),(f4,m3),(f5,m4)}P=m1f2m5f4m3f1是一條可增廣道路。f1f2m1f3f4f5m2m3m4m5M={(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)}§1最大匹配－定義8f1f2m1f3f4f5m2m312§1最大匹配－Berge定理定理7.1(Berge1957)：M為最大匹配的充要條件是：圖G中不存在可增廣道路。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m5§1最大匹配－Berge定理定理7.1(Berge13[引理]設(shè)P是匹配Ｍ-可增廣道路，則PM是一個比M更大的匹配，且|PM｜＝|M|+1.[定理1](Berge)設(shè)G=(V,E)，M為G中匹配，則M為G的最大匹配當(dāng)且僅當(dāng)G中不存在M可增廣道。[證明]必要性：如有M-可增廣道路，則有更大匹配。矛盾！充分性：如果有最大匹配M’,|M’|>|M|.考慮MM’，在可增廣路中，第一條邊與最后一條邊都不是中的邊，因而可增廣路中屬于的邊數(shù)比不在中邊數(shù)少一條。[引理]設(shè)P是匹配Ｍ-可增廣道路，則PM是一個比M更大的14M實(shí)線邊，M’虛線邊MM’其中每個結(jié)點(diǎn)的最多與Ｍ邊和一個M’邊關(guān)聯(lián)，每條道路是M邊和M’邊交互道路。其中回路包含相同數(shù)目的M邊和M’邊。由|M’|>|M|,必存在M’邊開始，M‘邊終止的M交互道路，即M-可增廣道路，矛盾！M實(shí)線邊，M’虛線邊MM’其中每個結(jié)點(diǎn)的最多與Ｍ邊和一個M15§2Hall定理設(shè)有m個人，n項(xiàng)工作，每個人會做其中的若干項(xiàng)工作，能不能適當(dāng)安排，使得每個人都有工作做？w1w2m1w3w4w5m2m3m4§2Hall定理設(shè)有m個人，n16§2Hall定理當(dāng)m>n時(shí)，肯定是不可能的，即使是m≤n也不一定。但如果每個人能做的工作越多，越容易實(shí)現(xiàn)。w1w2m1w3w4w5m2m3m4§2Hall定理當(dāng)m>n時(shí)，肯17§2Hall定理－1Hall定理(1935)：二分圖G存在一匹配M，使得X的所有頂點(diǎn)關(guān)于M飽和的充要條件是：對于X任一子集A，及與A鄰接的點(diǎn)集為N(A)，恒有：|N(A)|≥|A|。w1w2m1w3w4w5m2m3m4YX§2Hall定理－1Hall定理(1935)：w1w18§3人員分派問題1965年，匈牙利著名數(shù)學(xué)家Edmonds設(shè)計(jì)了一種求最大匹配的算法，稱為匈牙利(Hungarian)算法。工作分配問題：現(xiàn)有n個人，n份工作，每個人有其擅長的工作。在什么條件下每個人都可以得到一份他擅長的工作？如何分配？§3人員分派問題1965年，匈19§3匈牙利算法匈牙利(Hungarian)算法：（1）任給一個初始匹配；（2）若X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)（3）；（3）在X中找一個非飽和點(diǎn)x0，V1={x0}，V2=空集；（4）若N(V1)=V2則停止，否則任選一點(diǎn)y∈N(V1)-V2；（5）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進(jìn)行增廣；轉(zhuǎn)（2）】§3匈牙利算法匈牙利(Hungarian)算法：20§3匈牙利算法例用匈牙利算法求下圖的最大匹配：例x1x2y1x3x4x5y2y3y4y5§3匈牙利算法例用匈牙利算法求下圖的最大匹配：例x121§3匈牙利算法例解（1）任給一個初始匹配；（2）若X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)（3）；解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}§3匈牙利算法例解（1）任給一個初始匹配；解x1x222§3匈牙利算法例解1（3）在X中找一個非飽和點(diǎn)x0，V1={x0}，V2=空集（4）若N(V1)=V2則停止，否則任選一點(diǎn)y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2},V2=空集N(V1)={y2,

y3}§3匈牙利算法例解1（3）在X中找一個非飽和點(diǎn)x0，23§3匈牙利算法例解2（5）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進(jìn)行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1=V1∪{x5}={x2,x5}；V2=V2∪

{y3}

={y3}V1={x2},V2=空集§3匈牙利算法例解2（5）若y已飽和，M中必有(y24§3匈牙利算法例解3（4）若N(V1)=V2則停止，否則任選一點(diǎn)y∈N(V1)-V2；解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2,x5}；V2={y3}N(V1)={y2,y3,y4,y5}§3匈牙利算法例解3（4）若N(V1)=V2則停止，25§3匈牙利算法例解4（5）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進(jìn)行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2,x5}；V2={y3}；V1=V1∪{x3}={x2,x5,x3}；V2=V2∪

{y5}

={y3,y5}§3匈牙利算法例解4（5）若y已飽和，M中必有(y26§3匈牙利算法例解5（4）若N(V1)=V2則停止，否則任選一點(diǎn)y∈N(V1)-V2；解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2,x5,

x3}；V2={y3,y5}；N(V1)={y2,y3,y4,y5}§3匈牙利算法例解5（4）若N(V1)=V2則停止，27§3匈牙利算法例解6（5）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進(jìn)行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2,x5,x3}；V2={y3,y5}；x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=ME(P)={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}?§3匈牙利算法例解6（5）若y已飽和，M中必有(y28§3匈牙利算法例解7（2）若X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)（3）；（3）在X中找一個非飽和點(diǎn)x0，V1={x0}，V2={}（4）若N(V1)=V2則停止，否則任選一點(diǎn)y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5V1={x4}；V2=空集M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}N(V1)={y3}§3匈牙利算法例解7（2）若X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)29§3匈牙利算法例解8（5）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進(jìn)行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5V1={x4}；V2=空集M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1=V1∪{x2}={x4,x2}；V2=V2∪{y3}

={y3}§3匈牙利算法例解8（5）若y已飽和，M中必有(y30§3匈牙利算法例解9（4）若N(V1)=V2則停止，否則任選一點(diǎn)y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,}；V2={y3}N(V1)={y2,y3}§3匈牙利算法例解9（4）若N(V1)=V2則停止，31§3匈牙利算法例解10（5）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進(jìn)行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,}；V2={y3}V1=V1∪{x3}={x4,x2,x3}；V2=V2∪{y2}

={y3,y2}§3匈牙利算法例解10（5）若y已飽和，M中必有(32§3匈牙利算法例解11（4）若N(V1)=V2則停止，否則任選一點(diǎn)y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3}；V2={y3,y2}N(V1)={y2,y3,y5}§3匈牙利算法例解11（4）若N(V1)=V2則停止33§3匈牙利算法例解12（5）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進(jìn)行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3}；V2={y3,y2}V1=V1∪{x5}={x4,x2,x3,x5}；V2=V2∪{y5}

={y3,y2,y5}§3匈牙利算法例解12（5）若y已飽和，M中必有(34§3匈牙利算法例解13（4）若N(V1)=V2則停止，否則任選一點(diǎn)y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3,x5}；V2={y3,y2,y5}N(V1)={y2,y3,y5,y4}§3匈牙利算法例解13（4）若N(V1)=V2則停止35§3匈牙利算法例解14（5）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進(jìn)行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3,

x5}；V2={y3,y2,y5}x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=ME(P)={(x1,y1),(x2,y2),(x3,y5),(x4,y3),(x5,y4)}?§3匈牙利算法例解14（5）若y已飽和，M中必有(36§3匈牙利算法例解15（2）若X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)（3）；解x1x2y1x3x4x5y2y3y4y5這時(shí)，M={(x1,y1),(x2,y2),(x3,y5),(x4,y3),(x5,y4)}就是所求的最大匹配?！?匈牙利算法例解15（2）若X已經(jīng)飽和，結(jié)束；否則37§4最佳匹配公司里有n名工作人員，他們每個人都能承擔(dān)n項(xiàng)工作的其中若干項(xiàng)，因?yàn)槊總€人的特長不同，所以對每項(xiàng)工作創(chuàng)造的價(jià)值也有所不同。問如何安排，使得他們總的創(chuàng)造價(jià)值最大？§4最佳匹配公司里有n名工作人38§4最佳匹配x對每項(xiàng)工作創(chuàng)造的價(jià)值的如右邊的矩陣所表示：x1x2y1x3x4x5y2y3y4y53554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y5§4最佳匹配x對每項(xiàng)工作創(chuàng)造的價(jià)39§5最佳匹配算法及例Kuhn和Munkras設(shè)計(jì)了求最佳匹配的有效算法，他們把求最佳匹配的問題轉(zhuǎn)化成可用匈牙利算法求另一個圖的完美匹配的問題?！?最佳匹配算法及例Kuhn和40§5最佳匹配算法1為此，他們對加權(quán)的二分圖每個頂點(diǎn)v給一個頂標(biāo)l(v)，當(dāng)xi∈X，yj∈Y，l(xi)+l(yj)≥cij時(shí)，稱這樣的頂標(biāo)為可行頂點(diǎn)a標(biāo)號（feasiblevertexlabelling）。§5最佳匹配算法1為此，他們對加權(quán)41§5最佳匹配算法2初始的時(shí)候，令l(xi)=maxci*；l(yi)=0；x1x2y1x3x4x5y2y3y4y53554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0§5最佳匹配算法2初始的時(shí)候，令x1x2y1x3x442最佳匹配定理設(shè)二分圖Kn,n=G是具有正常頂標(biāo)l的加權(quán)圖，取G的邊子集El={eij|eij∈E(G),l(i)+l(j)=cij}。令Gl是以El為邊集的生成子圖，如果有Gl完美匹配M，則M即為G的最佳匹配。x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5最佳匹配定理設(shè)二分圖Kn,n=G是具有正常頂標(biāo)l的加權(quán)圖，取43§5最佳匹配算法3KM算法：（1）選定初始正常標(biāo)頂l，構(gòu)作圖Gl，在Gl中用匈牙利算法求一個最大匹配；（2）若X飽和則結(jié)束，此時(shí)所得匹配就是最佳匹配，否則在X中任選一個非飽和點(diǎn)x0，令V1={x0}，V2={}；（3）若NGl(V1)=V2，則取α=min(l(xi)+l(yj)-cij)，其中xi∈V1，yj∈NG(V1)-V2，使得

l(v)-αv∈V1

l(v)=l(v)+αv∈V2

l(v)其他

重新構(gòu)作圖Gl，在NGl(V1)-V2任取一點(diǎn)y，轉(zhuǎn)向（4）；否則在NGl(V1)-V2任取一點(diǎn)y，轉(zhuǎn)向（4）§5最佳匹配算法3KM算法：44§5最佳匹配算法4（4）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（3）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進(jìn)行增廣；轉(zhuǎn)（2）】§5最佳匹配算法4（4）若y已飽和，M中必有(y,45§5最佳匹配算法例求下圖的最佳匹配例x1x2y1x3x4x5y2y3y4y53554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y5§5最佳匹配算法例求下圖的最佳匹配例x1x2y1x346§5最佳匹配算法例解1（1）選定初始正常標(biāo)頂l，構(gòu)作圖Gl，在Gl中用匈牙利算法求一個最大匹配；解x1x2y1x3x4x5y2y3y4y53554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5§5最佳匹配算法例解1（1）選定初始正常標(biāo)頂l，構(gòu)作47§5最佳匹配算法例解2（2）若X飽和則結(jié)束，此時(shí)所得匹配就是最佳匹配，否則在X中任選一個非飽和點(diǎn)x0，令V1={x0}，V2=空集；解x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}V1={x4},V2=空集§5最佳匹配算法例解2（2）若X飽和則結(jié)束，此時(shí)所得48§5最佳匹配算法例解3（3）若NGl(V1)=V2，則……；否則在NGl(V1)-V2任取一點(diǎn)y，轉(zhuǎn)向（4）解x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}V1={x4},V2={}§5最佳匹配算法例解3（3）若NGl(V1)=V2，49§5最佳匹配算法例解4（4）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（3）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進(jìn)行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}V1={x4,x3},V2={y3}§5最佳匹配算法例解4（4）若y已飽和，M中必有(50§5最佳匹配算法例解5（3）若NGl(V1)=V2，則……；否則在NGl(V1)-V2任取一點(diǎn)y，轉(zhuǎn)向（4）解x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}V1={x4,x3},V2={y3}§5最佳匹配算法例解5（3）若NGl(V1)=V2，51§5最佳匹配算法例解6（4）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（3）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進(jìn)行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}V1={x4,x3,x1},V2={y3,y2}§5最佳匹配算法例解6（4）若y已飽和，M中必有(52§5最佳匹配算法例解7（3）若NGl(V1)=V2，取α=min(l(xi)+l(yj)-cij)，其中xi∈V1，yj∈NG(V1)-V2解x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}V1={x4,x3,x1},V2={y3,y2},3554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y5α=1NG(V1)={y1,y2,y3,y4,y5}§5最佳匹配算法例解7（3）若NGl(V1)=V2，53§5最佳匹配算法例解8l(v)-αv∈V1

l(v)=l(v)+αv∈V2

l(v)其他解x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}V1={x4,x3,x1},V2={y3,y2}α=1l(x1)=4l(x3)=3l(x4)=0l(y2)=1l(y3)=1§5最佳匹配算法例解854§5最佳匹配算法例解9重新構(gòu)作圖Gl，在NGl(V1)-V2任取一點(diǎn)y，轉(zhuǎn)向（4）解x1x2y1x3x4x5y2y3y4y5l(x1)=4l(x2)=2l(x3)=3l(x4)=0l(x5)=3l(y5)=0l(y1)=0l(y2)=1l(y3)=1l(y4)=0M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}V1={x4,x3,x1},V2={y3,y2}3554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y5x1x2y1x3x4x5y2y3y4y5l(xi)+l(yj)＝cij§5最佳匹配算法例解9重新構(gòu)作圖Gl，在NGl(V155§5最佳匹配算法例解10（4）若y已飽和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；轉(zhuǎn)（3）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進(jìn)行增廣；轉(zhuǎn)（2）】x1x2y1x3x4x5y2y3y4y5解V1={x4,x3,x1},V2={y3,y2}l(x1)=4l(x2)=2l(x3)=3l(x4)=0l(x5)=3l(y5)=0l(y1)=0l(y2)=1l(y3)=1l(y4)=0x1x2y1x3x4x5y2y3y4y5M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}M={(x1,y4),(x2,y1),(x3,y3),

(x4,y4),

(x5,y5),}§5最佳匹配算法例解10（4）若y已飽和，M中必有56§5最佳匹配算法例解11（2）若X飽和則結(jié)束，此時(shí)所得匹配就是最佳匹配，否則在X中任選一個非飽和點(diǎn)x0，令V1={x0}，V2={}；x1x2y1x3x4x5y2y3y4y5解M={(x1,y4),(x2,y1),(x3,y3),

(x4,y4),

(x5,y5),}l(x1)=4l(x2)=2l(x3)=3l(x4)=0l(x5)=3l(y5)=0l(y1)=0l(y2)=1l(y3)=1l(y4)=0W=4+2+4+1+3=14§5最佳匹配算法例解11（2）若X飽和則結(jié)束，此時(shí)所57課堂練習(xí)1、用匈牙利算法求下圖的最大匹配。x1x2y1x3x4x5y2y3y4y5課堂練習(xí)1、用匈牙利算法求下圖的最大匹配。x1x2y1x3x58課堂練習(xí)2、若二分圖K5,5的權(quán)值矩陣如下，求其最佳匹配。0554033033144301220113144C=x1x2x3x4x5y1y2y3y4y5課堂練習(xí)2、若二分圖K5,5的權(quán)值矩陣如下，求其最佳匹配。059§6色數(shù)問題邊的著色問題頂點(diǎn)的著色問題§6色數(shù)問題邊的著色問題60一、邊的著色問題定義：給圖G的邊著色，使得有共同頂點(diǎn)的邊異色的最少顏色數(shù)，稱為邊色數(shù)。邊色數(shù)=3邊色數(shù)=5一、邊的著色問題定義：給圖G的邊著色，使得有共同頂點(diǎn)的邊異色61一、邊的著色問題妖怪圖（snarkgraph）妖怪圖每個點(diǎn)都關(guān)聯(lián)著3條邊，用4種顏色可以把每條邊涂上顏色，使得有公共端點(diǎn)的邊異色，而用3種顏色辦不到，切斷任意3條邊不會使它斷裂成2個有邊的圖。一、邊的著色問題妖怪圖（snarkgraph）62一、邊的著色問題1單星妖怪和雙星妖怪：單星妖怪雙星妖怪一、邊的著色問題1單星妖怪和雙星妖怪：單星妖怪雙星妖怪63一、邊的著色問題時(shí)間表問題；設(shè)x1,x2,…,xm為m個工作人員，y1,y2,…,yn表為n種設(shè)備，工作人員對設(shè)備提出要求，使用時(shí)間均假定以單位時(shí)間計(jì)算，自然每一個工作人員在同一個時(shí)間只能使用一種設(shè)備，某一種設(shè)備在同一時(shí)間里只能為一個工作人員使用，問應(yīng)如何合理安排，使得盡可能短時(shí)間里滿足工作人員的要求？問題轉(zhuǎn)換為X={x1,x2,…,xm}，Y={y1,y2,…,yn}的二分圖G，工作人員xi要求使用設(shè)備yj，每單位時(shí)間對應(yīng)一條從xi到y(tǒng)j的邊，這樣所得的二分圖過xi，yj的邊可能不止一條。問題變?yōu)閷λ枚謭DG的邊著色問題。有相同顏色的邊可以安排在同一時(shí)間里。一、邊的著色問題時(shí)間表問題；問題轉(zhuǎn)換為X={64一、邊的著色問題3定理：二分圖G的邊色數(shù)＝圖中頂點(diǎn)的最大度。x1x2y1x3x4x5y2y3y4y5一、邊的著色問題3定理：二分圖G的邊色數(shù)＝圖中頂點(diǎn)的最大度。65一、邊的著色問題3定理(Vizing1964)：若圖G為簡單圖，圖中頂點(diǎn)最大度為d，則G的邊色數(shù)為d或d+1。x1x2y1x3x4x5y2y3y4y5單星妖怪第一類圖第二類圖目前仍無有效區(qū)分(判別)任給定圖屬第幾類圖的有效方法。一、邊的著色問題3定理(Vizing1964)：若圖G為簡66一、邊的著色問題4邊的著色問題可以轉(zhuǎn)化為頂點(diǎn)的著色問題。一、邊的著色問題4邊的著色問題可以轉(zhuǎn)化為頂點(diǎn)的著色問題。67二、頂點(diǎn)的著色問題定義：給圖G的頂點(diǎn)著色，使得相鄰的頂點(diǎn)異色的最少顏色數(shù)，稱為圖G頂色數(shù)，簡稱色數(shù)；記作χ(G)。χ(G)=2二、頂點(diǎn)的著色問題定義：給圖G的頂點(diǎn)著色，使得相鄰的頂點(diǎn)異色68二、頂點(diǎn)的著色問題四色猜想：平面圖的色數(shù)不大于5。二、頂點(diǎn)的著色問題四色猜想：69一、邊的著色問題課程考試安排；用頂點(diǎn)v1,v2,…,vn表示n門課程，若其中兩門課i,j被同時(shí)選，則vi,vj間連一條邊?？荚嚢才艈栴}相當(dāng)于圖的頂點(diǎn)染色問題，著同一顏色的頂點(diǎn)對應(yīng)的課程可以同時(shí)進(jìn)行考試，使圖的相鄰頂點(diǎn)有不同顏色的最少顏色數(shù)目，便是進(jìn)行考試的最少場次。物資存儲問題；一、邊的著色問題課程考試安排；706.2排課表問題

問題m位教師和n個班級，其中教師Xi要給班級Yj上pij節(jié)課。欲在最少節(jié)次p內(nèi)排完所有的課。將偶圖G=(X,Y,E)的邊集E劃分成互不相交的p個匹配(E1，…，Ep)，且使p為最小，其中X={x1,…,xm},Y={y1,…,yn}求偶圖G的p-邊著色，其中p==。由習(xí)題6.1.4知，上述問題有好算法。當(dāng)上述問題中教室數(shù)有限時(shí)（教室數(shù)≥），若要在p（

）節(jié)內(nèi)排完全部（l=E）節(jié)課，所需教室數(shù)c

問題能否適當(dāng)排課，使全部節(jié)課在p（

）節(jié)內(nèi)排完，且每節(jié)課所用教室數(shù)？（∴1ip）6.2排課表問題問題m位教師和n個班級，其中教師716.2排課表問題

引理6.3設(shè)M，N為G的二不相交匹配，且M>N，則存在G的二不相交匹配M’，N’使M’=M-1，N’=N+1，且M’∪N’=M∪

N。證明：令H=G[M∪

N]，則H的每個分支為一路或圈，由M及N的邊交錯組成。且由于M>N，存在H的一個分支，它是路P，起、止于M邊。因此

M’=ME(P)及N’=NE(P)

即為所求。定理6.3設(shè)G為偶圖，p

，則存在G的p個互不相交的匹配使

E=M1∪……∪Mp。

且,1ip。6.2排課表問題引理6.3設(shè)M，N為G的二不相交726.2排課表問題

證明：由定理6.1,E可劃分為個互不相交的匹配

M1，……，M。

因此，對p

，G有p個互不相交的匹配

M1，……，M，……，Mp。（令Mi=當(dāng)i>p）

使E=M1……Mp。今對邊數(shù)差>1的兩個匹配，反復(fù)使用引理6.3，最后可得所求的匹配M1，……，Mp。

注在實(shí)際應(yīng)用中，教師和班級往往會提出一些，例如所上節(jié)次時(shí)間的要求，問題變得很復(fù)雜。Even，Itai&Shmir（1976）證明：在教師和班級提出條件時(shí)，判定課表的存在性問題是個NP-complete問題。甚至當(dāng)G為簡單偶圖，且學(xué)生不提出要求的情況下，也是如此。6.2排課表問題證明：由定理6.1,E可劃分為73二、頂點(diǎn)的著色問題1色數(shù)的性質(zhì)：（1）圖G只有孤立點(diǎn)時(shí)，χ(G)=1；（2）n個頂點(diǎn)的完全圖G有χ(G)=n；二、頂點(diǎn)的著色問題1色數(shù)的性質(zhì)：74二、頂點(diǎn)的著色問題1（3）若圖G是n個頂點(diǎn)的回路，則

χ(G)=2n為偶數(shù)

=3n為奇數(shù)；二、頂點(diǎn)的著色問題1（3）若圖G是n個頂點(diǎn)的回路，則75二、頂點(diǎn)的著色問題1（4）圖G是頂點(diǎn)數(shù)超過1的樹時(shí)，χ(G)=2；二、頂點(diǎn)的著色問題1（4）圖G是頂點(diǎn)數(shù)超過1的樹時(shí)，χ(G)76二、頂點(diǎn)的著色問題1（5）若圖G是二分圖，則χ(G)=2。x1x2y1x3x4x5y2y3y4y5二、頂點(diǎn)的著色問題1（5）若圖G是二分圖，則χ(G)=2。x77二、頂點(diǎn)的著色問題2定理：圖G=(V,E)的色數(shù)χ(G)=2的充要條件是：(1)|E|≥1；(2)G不存在邊數(shù)為奇數(shù)的回路。二、頂點(diǎn)的著色問題2定理：圖G=(V,E)的色數(shù)χ(G)=278二、頂點(diǎn)的著色問題2定理：若圖G=(V,E)，d=max{d(vi)},vi∈V，則χ(G)≤d+1。二、頂點(diǎn)的著色問題2定理：若圖G=(V,E)，d=max{d79三、頂點(diǎn)著色的算法下面給出頂點(diǎn)著色的算法(假定G的頂點(diǎn)為v1,v2,…,vn;用來染色的顏色為c1,c2,…cn)：（1）對i=1,2,…,n,作Ci={c1,c2,…,ci}；（2）標(biāo)頂點(diǎn)vi(i=1,2,…,n)的顏色集Ci的第一種顏色ck；（3）對頂點(diǎn)vi的所有鄰接點(diǎn)vj(j>i)，作Cj=Cj-{ck}；（4）轉(zhuǎn)到（2），直到所有頂點(diǎn)都著色為止。三、頂點(diǎn)著色的算法下面給出頂點(diǎn)著色的算法(假定G的頂點(diǎn)為v180三、頂點(diǎn)著色的算法例對下圖頂點(diǎn)進(jìn)行著色。例v1v2v3v4v5v7v6三、頂點(diǎn)著色的算法例對下圖頂點(diǎn)進(jìn)行著色。例v1v2v3v4v81三、頂點(diǎn)著色的算法例解（1）對i=1,2,…,n,作Ci={c1,c2,…,ci}；解v1v2v3v4v5v7v6C1={c1}C2={c1,c2}C3={c1,c2,c3}C4={c1,c2,c3,c4}C5={c1,c2,c3,c4,c5}C6={c1,c2,c3,c4,c5,c6}C7={c1,c2,c3,c4,c5,c6,c7}三、頂點(diǎn)著色的算法例解（1）對i=1,2,…,n,作Ci={82三、頂點(diǎn)著色的算法例解1（2）標(biāo)頂點(diǎn)vi(i=1,2,…,n)的顏色集Ci的第一種顏色ck；解C1={c1}C2={c1,c2}C3={c1,c2,c3}C4={c1,c2,c3,c4}C5={c1,c2,c3,c4,c5}C6={c1,c2,c3,c4,c5,c6}C7={c1,c2,c3,c4,c5,c6,c7}v1v2v3v4v5v7v6c1三、頂點(diǎn)著色的算法例解1（2）標(biāo)頂點(diǎn)vi(i=1,2,…,83三、頂點(diǎn)著色的算法例解2（3）對頂點(diǎn)vi的所有鄰接點(diǎn)vj(j>i)，作Cj=Cj-{ck}；解v1v2v3v4v5v7v6c1C1={c1}C2={c1,c2}C3={c1,c2,c3}C4={c1,c2,c3,c4}C5={c1,c2,c3,c4,c5}C6={c1,c2,c3,c4,c5,c6}C7={c1,c2,c3,c4,c5,c6,c7}C2={c2}C3={c2,c3}C7={c2,c3,c4,c5,c6,c7}C5={c2,c3,c4,c5}C6={c2,c3,c4,c5,c6}三、頂點(diǎn)著色的算法例解2（3）對頂點(diǎn)vi的所有鄰接點(diǎn)vj(j84三、頂點(diǎn)著色的算法例解3（4）轉(zhuǎn)到（2），直到所有頂點(diǎn)都著色為止（2）標(biāo)頂點(diǎn)vi(i=1,2,…,n)的顏色集Ci的第一種顏色ck解v1v2v3v4v5v7v6c1C1={c1}C2={c2}C3={c2,c3}C4={c1,c2,c3,c4}C5={c2,c3,c4,c5}C6={c2,c3,c4,c5,c6}C7={c2,c3,c4,c5,c6,c7}c2三、頂點(diǎn)著色的算法例解3（4）轉(zhuǎn)到（2），直到所有頂點(diǎn)都著色85三、頂點(diǎn)著色的算法例解4（3）對頂點(diǎn)vi的所有鄰接點(diǎn)vj(j>i)，作Cj=Cj-{ck}；解v1v2v3v4v5v7v6c1C1={c1}C2={c2}C3={c2,c3}C4={c1,c2,c3,c4}C5={c2,c3,c4,c5}C6={c2,c3,c4,c5,c6}C7={c2,c3,c4,c5,c6,c7}c2C3={c3}三、頂點(diǎn)著色的算法例解4（3）對頂點(diǎn)vi的所有鄰接點(diǎn)vj(j86三、頂點(diǎn)著色的算法例解5解v1v2v3v4v5v7v6c1C1={c1}C2={c2}C3={c3}C4={c1,c2,c3,c4}C5={c2,c3,c4,c5}C6={c2,c3,c4,c5,c6}C7={c2,c3,c4,c5,c6,c7}c2（4）轉(zhuǎn)到（2），直到所有頂點(diǎn)都著色為止（2）標(biāo)頂點(diǎn)vi(i=1,2,…,n)的顏色集Ci的第一種顏色ckc3三、頂點(diǎn)著色的算法例解5解v1v2v3v4v5v7v6c1C87三、頂點(diǎn)著色的算法例解6解v1v2v3v4v5v7v6c1C1={c1}C2={c2}C3={c3}C4={c1,c2,c3,c4}C5={c2,c3,c4,c5}C6={c2,c3,c4,c5,c6}C7={c2,c3,c4,c5,c6,c7}c2（3）對頂點(diǎn)vi的所有鄰接點(diǎn)vj(j>i)，作Cj=Cj-{ck}；c3C5={c2,c4,c5}C1={c1,c2,c4}三、頂點(diǎn)著色的算法例解6解v1v2v3v4v5v7v6c1C88三、頂點(diǎn)著色的算法例解7解v1v2v3v4v5v7v6c1C1={c1}C2={c2}C3={c3}C4={c1,c2,c4}C5={c2,c4,c5}C6={c2,c3,c4,c5,c6}C7={c2,c3,c4,c5,c6,c7}c2（4）轉(zhuǎn)到（2），直到所有頂點(diǎn)都著色為止（2）標(biāo)頂點(diǎn)vi(i=1,2,…,n)的顏色集Ci的第一種顏色ckc3c1三、頂點(diǎn)著色的算法例解7解v1v2v3v4v5v7v6c1C89三、頂點(diǎn)著色的算法例解8解v1v2v3v4v5v7v6c1C1={c1}C2={c2}C3={c3}C4={c1,c2,c4}C5={c2,c4,c5}C6={c2,c3,c4,c5,c6}C7={c2,c3,c4,c5,c6,c7}c2（3）對頂點(diǎn)vi的所有鄰接點(diǎn)vj(j>i)，作Cj=Cj-{ck}；c3c1三、頂點(diǎn)著色的算法例解8解v1v2v3v4v5v7v6c1C90三、頂點(diǎn)著色的算法例解9解v1v2v3v4v5v7v6c1C1={c1}C2={c2}C3={c3}C4={c1,c2,c4}C5={c2,c4,c5}C6={c2,c3,c4,c5,c6}C7={c2,c3,c4,c5,c6,c7}c2（4）轉(zhuǎn)到（2），直到所有頂點(diǎn)都著色為止（2）標(biāo)頂點(diǎn)vi(i=1,2,…,n)的顏色集Ci的第一種顏色ckc3c1c2三、頂點(diǎn)著色的算法例解9解v1v2v3v4v5v7v6c1C91三、頂點(diǎn)著色的算法例解10解v1v2v3v4v5v7v6c1C1={c1}C2={c2}C3={c3}C4={c1,c2,c4}C5={c2,c4,c5}C6={c2,c3,c4,c5,c6}C7={c2,c3,c4,c5,c6,c7}c2（3）對頂點(diǎn)vi的所有鄰接點(diǎn)vj(j>i)，作Cj=Cj-{ck}；c3c1c2C6={c3,c4,c5,c6}三、頂點(diǎn)著色的算法例解10解v1v2v3v4v5v7v6c192三、頂點(diǎn)著色的算法例解11解v1v2v3v4v5v7v6c1C1={c1}C2={c2}C3={c3}C4={c1,c2,c4}C5={c2,c4,c5}C6={c3,c4,c5,c6}C7={c2,c3,c4,c5,c6,c7}c2（4）轉(zhuǎn)到（2），直到所有頂點(diǎn)都著色為止（2）標(biāo)頂點(diǎn)vi(i=1,2,…,n)的顏色集Ci的第一種顏色ckc3c1c2c3三、頂點(diǎn)著色的算法例解11解v1v2v3v4v5v7v6c193三、頂點(diǎn)著色的算法例解12解v1v2v3v4v5v7v6c1C1={c1}C2={c2}C3={c3}C4={c1,c2,c4}C5={c2,c4,c5}C6={c3,c4,c5,c6}C7={c2,c3,c4,c5,c6,c7}c2（3）對頂點(diǎn)vi的所有鄰接點(diǎn)vj(j>i)，作Cj=Cj-{ck}；c3c1c2C7={c2,c4,c5,c6,c7}c3三、頂點(diǎn)著色的算法例解12解v1v2v3v4v5v7v6c194三、頂點(diǎn)著色的算法例解13解v1v2v3v4v5v7v6c1C1={c1}C2={c2}C3={c3}C4={c1,c2,c4}C5={c2,c4,c5}C6={c3,c4,c5,c6}C7={c2,c4,c5,c6,c7}c2（4）轉(zhuǎn)到（2），直到所有頂點(diǎn)都著色為止（2）標(biāo)頂點(diǎn)vi(i=1,2,…,n)的顏色集Ci的第一種顏色ckc3c1c2c3c2三、頂點(diǎn)著色的算法例解13解v1v2v3v4v5v7v6c195三、頂點(diǎn)著色的算法注：上述算法并不能保證求出的著色方案用的顏色是最少的。三、頂點(diǎn)著色的算法注：上述算法并不能保證求出的著色方案用的顏96第一章圖的基本概念七橋問題：背景、結(jié)果；路徑問題：引入矩陣、a(k)ij值的實(shí)際意義；哈密頓回路問題到貨郎問題：NP問題；四色問題Ramsey問題：r(p,q)的含義、證明r(3,3)=6；妖怪圖圖的概念：握手定理及推論；第一章圖的基本概念七橋問題：背景、結(jié)果；97第一章圖的基本概念Euler回路：判定定理及推論及定理的證明；Hamilton回路：判定定理及推論；圖的矩陣表示法：鄰接矩陣中圖的性質(zhì)、圖的同構(gòu)；中國郵路問題：W(C∩E*)≤W(E(C)-E*)平面圖：一系列定理、對偶圖；第一章圖的基本概念Euler回路：判定定理及推論及定理的98第二章樹樹的概念和基本性質(zhì)：

5個等價(jià)命題及定理；幾類常用樹：

判定樹、決策樹、有序二元樹、Huffman樹；最小生成樹：

Prim、Kruskal、破圈法；第二章樹樹的概念和基本性質(zhì)：

5個等價(jià)命題及定理99第三章圖的算法最短路徑問題：

（1）Bellman-Ford算法算法、Dijkstra算法；

（2）動態(tài)規(guī)劃算法、Floyd-Warshall算法；圖的遍歷算法：DFS、BFS；圖的劃分：切割點(diǎn)；第三章圖的算法最短路徑問題：

（1）Bellman-Fo100第六章網(wǎng)絡(luò)流圖問題網(wǎng)絡(luò)流圖問題和最大流：定義、定理；割切及割切定理：求最大流算法：

（1）2F算法、EK修正算法：標(biāo)號，增流；

（2）Dinic算法：分層、增流；第六章網(wǎng)絡(luò)流圖問題網(wǎng)絡(luò)流圖問題和最大流：定義、定理101第七章匹配理論和色數(shù)問題最大匹配和匹配定理：

（1）定義；

（2）匹配定理；匈牙利算法；最佳匹配

（1）定義；

（2）最佳匹配算法；色數(shù)問題：定義、性質(zhì)、定理，算法；第七章匹配理論和色數(shù)問題最大匹配和匹配定理：

（1）102第五章匹配第五章匹配103§1最大匹配－1具體問題描述：有n個女士和n個男士參加舞會，每位女士與其中若干位男士相識，每位男士與其中若干位女士相識，問如何安排，使得盡量多配對的男女舞伴相識。f1f2m1f3f4f5m2m3m4m5§1匹配§1最大匹配－1具體問題描述：f1f2m1f3f4f104§1最大匹配－1下圖就是一種分配方法：f1f2m1f3f4f5m2m3m4m5(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)§1最大匹配－1下圖就是一種分配方法：f1f2m1f105匹配問題是運(yùn)籌學(xué)的重要問題之一，也是圖論的重要內(nèi)容，它在所謂“人員分配問題”和“最優(yōu)分配問題”中有重要作用。假定有一個男生有窮集合，其中每個男生認(rèn)識一些女生，在什么條件下每個男生都可以和他認(rèn)識的女生配對？類似的工作分配問題：現(xiàn)有n個人，m份工作，每個人有其擅長的工作。在什么條件下每個人都可以得到一份他擅長的工作？如何分配？匹配問題是運(yùn)籌學(xué)的重要問題之一，也是圖論的106§1最大匹配－定義定義：若圖G=(V,E)的頂點(diǎn)可以分成X，Y兩個子集，每個子集里的頂點(diǎn)互不相鄰，這樣的圖稱為二分圖。f1f2m1f3f4f5m2m3m4m5§1最大匹配－定義定義：若圖G=(V,E)的頂點(diǎn)可以107§1最大匹配－定義1定義：若M是圖G=(V,E)的邊子集，且M中的任意兩條邊在G中不相鄰，則稱M為G中的一個匹配，M中的每條邊的兩個端點(diǎn)稱為是M-飽和的的。f1f2m1f3f4f5m2m3m4m5M={(f1,m2),(f2,m1),(f3,m4),(f4,m5)}§1最大匹配－定義1定義：若M是圖G=(V,E)的邊108§1最大匹配－定義2定義：若圖G中每個頂點(diǎn)均被M許配時(shí)，稱M為G中的一個完美匹配。f1f2m1f3f4f5m2m3m4m5M={(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)}§1最大匹配－定義2定義：若圖G中每個頂點(diǎn)均被M許配109§1最大匹配－定義3定義：圖G中邊數(shù)最多的匹配M，稱為G中的一個最大匹配。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m5§1最大匹配－定義3定義：圖G中邊數(shù)最多的匹配M，稱110§1最大匹配－定義4定義：若匹配M的某邊和頂點(diǎn)v關(guān)聯(lián)，稱v是M-飽和的，否則就是M-不飽和的。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m5飽和的不飽和的§1最大匹配－定義4定義：若匹配M的某邊和頂點(diǎn)v關(guān)聯(lián)111§1最大匹配－定義5定義：若M是圖G的一個匹配，若從G中一個頂點(diǎn)到另一個頂點(diǎn)存在一條道路，此路徑由屬于M和不屬于M的邊交替出現(xiàn)組成的，則稱此路徑為M-交錯路。f1