離散數(shù)學(xué)及其應(yīng)用第10章-特殊圖模型與算法(上)課件

1、2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所1離散數(shù)學(xué)Discrete Mathematics 汪榮貴 教授合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所2第10章 特殊圖模型與算法（上）2022/7/25二分圖與匹配問題23歐拉圖與哈密頓圖1 本章學(xué)習(xí)內(nèi)容2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所4歐拉圖與哈密頓圖2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所5歐拉圖與哈密頓圖歐拉圖及其性質(zhì)哈密頓圖及其性質(zhì)中國郵路問題ADBC 歐拉圖的引入72022/7/25 歐拉圖的引入哥尼斯堡七橋問題：哥尼斯堡小鎮(zhèn)有一條貫穿全市的小河，河上有兩個(gè)小島，由七座橋?qū)⑦@兩個(gè)小島及其與河兩岸進(jìn)行互聯(lián)，如圖所示

2、。問題是怎樣才能不重復(fù)、不遺漏地走完七座橋，并回到出發(fā)點(diǎn)。 歐拉圖的定義【定義】設(shè) G=V,E是任意給定的一個(gè)圖模型，通過圖G中所有邊一次且僅一次的通路稱為歐拉通路，通過圖G中所有邊一次且僅一的回路稱為歐拉回路。如果圖G中存在歐拉回路，則稱之為歐拉圖，如果G中存在歐拉通路但不存在歐拉回路，則稱之為半歐拉圖。 規(guī)定：平凡圖為歐拉圖。以上定義既適合無向圖也適合有向圖 歐拉圖的特征 例 題【例】判斷圖中，哪些圖是歐拉圖，哪些圖是半歐拉圖? 歐拉通路的判定【定理】設(shè) G=V,E是任意給定的一個(gè)無向圖模型，則G=V,E是歐拉圖當(dāng)且僅當(dāng) G=V,E為連通圖且所有結(jié)點(diǎn)度數(shù)均為偶數(shù)?！就普摗吭O(shè) G=V,E是任

3、意給定的一個(gè)無向圖模型，則G=V,E是半歐拉圖當(dāng)且僅當(dāng) G=V,E為連通圖且恰有2個(gè)奇度數(shù)結(jié)點(diǎn)。 例 題【例】對(duì)于如圖所示的圖模型 ，試判斷哪些圖能夠一筆畫成。 歐拉通路的判定【定理】設(shè) G=V,E是任意給定的一個(gè)有向圖模型，則有：G=V,E是歐拉圖當(dāng)且僅當(dāng) G=V,E為連通圖且所有結(jié)點(diǎn)的入度等等于出度；G=V,E是半歐拉圖，當(dāng)且僅當(dāng)G=V,E連通且僅有一個(gè)結(jié)點(diǎn)的入度比出度大1，另外一個(gè)結(jié)點(diǎn)的出度比入度大1，其余結(jié)點(diǎn)的入度等于出度。 對(duì)任意給定的無向連通圖，只需通過對(duì)圖中各結(jié)點(diǎn)度數(shù)的計(jì)算，就可知它是否存在歐拉通路及歐拉回路，從而知道它是否為歐拉圖； 對(duì)任意給定的有向連通圖，只需通過對(duì)圖中各結(jié)點(diǎn)

4、出度與入度的計(jì)算，就可知它是否存在歐拉通路及歐拉回路，從而知道它是否為歐拉圖。2022/7/25 總 結(jié) 七橋問題2022/7/25弗洛萊算法 2022/7/25算法具體步驟 2022/7/25 算法關(guān)鍵 【例】對(duì)于圖所示的無向圖，用弗洛萊算法求出其的一條歐拉通路。 例 題 【解】圖中每個(gè)結(jié)點(diǎn)的度數(shù)都是偶數(shù)，故存在歐拉回路。 例 題 例 題 例 題 例 題 例 題 例 題 【例】對(duì)于圖所示三個(gè)房間布局的平面設(shè)計(jì)，其中每個(gè)房間兩兩共墻相連，每面墻上有門通向室外，能否設(shè)計(jì)一個(gè)行走路徑，使得某人從某房間里或室外開始出發(fā)，經(jīng)過且只經(jīng)過每個(gè)門一次？【解】將該平面設(shè)計(jì)圖示抽象成一個(gè)圖模型，每個(gè)房間及室外分

5、別構(gòu)成一個(gè)結(jié)點(diǎn)，每扇門對(duì)應(yīng)一條邊，則問題轉(zhuǎn)化為該圖是否存在一條歐拉道路。 例 題 例 題 【例】求出下圖的一條Euler回路。v1v2v5v3v4v6v7v8v9 例 題 【解】看每個(gè)頂點(diǎn)的度是否都是偶數(shù)。 d(V1)=2， d(V2)=4， d(V3)=2， d(V4)=4， d(V5)=4， d(V6)=4， d(V7)=2， d(V8)=2， d(V9)=4。 所以存在Euler回路。v1v2v5v3v4v6v7v8v9 例 題 可以任意一個(gè)頂點(diǎn)為起點(diǎn)，這里以v2為起點(diǎn)，依序去掉相連的邊v1v2v5v3v4v6v7v8v9 例 題 (1)先去掉(v2,v4)v1v2v5v3v4v6v7v

6、8v91 例 題 (2) 接著去掉(v4,v3)v1v2v5v3v4v6v7v8v912 例 題 (3)接著去掉(v3,v2)v1v2v5v3v4v6v7v8v9123 例 題 依序去掉相連的邊。v1v2v5v3v4v6v7v8v9123 例 題 v1v2v5v3v4v6v7v8v912345678這時(shí)，如果去掉(v6,v5)將導(dǎo)致圖不連通 例 題 v1v2v5v3v4v6v7v8v91234567891011121314V2-v4-v3-v2-v1-v4-v5-v9-v6-v8-v9-v7-v6-v5-v2Euler回路：從上例可知， Euler回路不唯一。 例 題 2022/7/25 例

7、題 2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所38 歐拉圖與哈密頓圖 歐拉圖及其性質(zhì) 哈密頓圖及其性質(zhì) 中國郵路問題 哈密頓圖的引入 哈密頓圖的引入 哈密頓圖的定義【定義】經(jīng)過圖中每個(gè)結(jié)點(diǎn)一次且僅一次的通路稱為哈密頓通路。經(jīng)過圖中每個(gè)結(jié)點(diǎn)一次且僅一次的回路稱為哈密頓回路。存在哈密頓回路的圖稱為哈密頓圖；存在哈密頓通路的圖稱為半哈密頓圖。規(guī)定：平凡圖為哈密頓圖。 哈密頓圖 哈密頓路徑的特點(diǎn) 哈密頓通路是經(jīng)過圖中所有結(jié)點(diǎn)的最短通路，即：經(jīng)過圖中所有結(jié)點(diǎn)的基本通路。 哈密頓回路是經(jīng)過圖中所有結(jié)點(diǎn)的最短回路，即：經(jīng)過圖中所有結(jié)點(diǎn)的基本回路。 事實(shí)上，哈密頓通路就是圖中所有結(jié)點(diǎn)的一個(gè)全排列。2022/7/2

8、5 例 題 【例】下面各圖是否哈密頓圖？是否存在哈密頓通路？2022/7/25 例 題 哈密頓圖的必要條件哈密頓圖的必要條件哈密頓圖的推論2022/7/25 例 題 2022/7/25 通常利用定理的逆否命題判斷某圖不是哈密頓圖。 必要但非充分2022/7/25 例 題 2022/7/25 例 題 哈密頓圖的充分條件定理的證明定理的證明定理的證明奧爾定理 充分而非必要2022/7/25 例 題 【例】由7個(gè)外交官舉行一場(chǎng)重要會(huì)議，其中A只會(huì)講英語，B會(huì)講英語和漢語，C會(huì)講英語、意大利語和俄語，D會(huì)講日語和漢語，E會(huì)講德語和意大利語，F(xiàn)會(huì)講法語、日語和俄語，G會(huì)講法語和德語。問如何安排座位，使得

9、在沒有翻譯官的情況下，這7個(gè)人都能夠和他身邊的人交談?！窘狻?022/7/25 例 題 2022/7/25 例 題 2022/7/25 例 題 2022/7/25 例 題 2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所64 歐拉圖與哈密頓圖 歐拉圖及其性質(zhì) 哈密頓圖及其性質(zhì) 中國郵路問題2022/7/25 中國郵路問題2022/7/25 數(shù)學(xué)模型2022/7/25 問題分析2022/7/25 構(gòu)造算法2022/7/25 構(gòu)造算法2022/7/25 例 題 【例】圖所示圖模型表示某郵遞員負(fù)責(zé)投遞街道的結(jié)構(gòu)圖，其中每條邊分別表示一條街道，每個(gè)結(jié)點(diǎn)表示街道的交叉路口，每條邊的權(quán)值表示該邊所對(duì)應(yīng)街道長(zhǎng)度，單位

10、是公里。如何設(shè)計(jì)線路使得郵遞員在經(jīng)過每條街道至少一次的前期下總路程最短。2022/7/25 例 題 【解】步驟1需向其添加平行邊擴(kuò)展為歐拉圖。2022/7/25 例 題 2022/7/25 例 題 2022/7/25 例 題 2022/7/25 例 題 2022/7/25歐拉圖與哈密頓圖1二分圖與匹配問題2 本章學(xué)習(xí)內(nèi)容2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所77二分圖與匹配問題2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所78 二分圖與匹配問題二分圖的概念與性質(zhì)完備匹配與最大匹配最大匹配判定與構(gòu)造2022/7/25 二分圖實(shí)例【解】可將如圖所示圖模型的所有結(jié)點(diǎn)劃分為應(yīng)聘者和崗位這兩個(gè)不同的集合，屬于同

11、一個(gè)集合的結(jié)點(diǎn)之間無邊聯(lián)結(jié)，圖中所有邊的兩個(gè)端點(diǎn)均分屬兩個(gè)不同的集合。具有這種特征的圖模型就是二分圖。2022/7/25 二分圖的定義2022/7/25 二分圖的概念2022/7/25 完全二分圖2022/7/25 例 題 【例】如圖所示的圖G和H是否為二分圖。【解】圖G是二分圖。圖H則不是二分圖。2022/7/25 例 題 2022/7/25 二分圖的判定 2022/7/25 二分圖的判定 2022/7/25 二分圖的判定 2022/7/25 二分圖的判定 2022/7/25 例 題 【例】判定如圖所示圖模型是否為二分圖。2022/7/25 例 題 【例】a,b,c,d,e,f分別為某次國際

12、學(xué)術(shù)會(huì)議的六個(gè)成員，其中：a只會(huì)說德語、日語和俄語；b只會(huì)說漢語、法語和日語；c只會(huì)說俄語和西班牙語；d只會(huì)說漢語和西班牙語；e只會(huì)說英語和德語；f只會(huì)說英語和法語。會(huì)議時(shí)需要將該六人分為兩組，是否會(huì)發(fā)生同一組內(nèi)的任意兩個(gè)成員不能互相直接交談的情況？2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所91 二分圖與匹配問題 二分圖的概念與性質(zhì) 完備匹配與最大匹配 最大匹配判定與構(gòu)造2022/7/25 匹配問題 2022/7/25 匹配問題 2022/7/25 匹配的概念 2022/7/25 匹配的概念 2022/7/25 例題 2022/7/25 霍爾定理2022/7/25 霍爾定理的思想2022/7/25

13、 例題 2022/7/25 t-條件判定 2022/7/25 t條件判定 2022/7/25 例題 2022/7/25 例題 2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所104二分圖與匹配問題二分圖的概念與性質(zhì)完備匹配與最大匹配最大匹配判定與構(gòu)造2022/7/25 可增廣道 2022/7/25 例題 2022/7/25 可增廣道 2022/7/25 匈牙利算法 1965年，匈牙利的著名數(shù)學(xué)家Edmonds設(shè)計(jì)了一種求最大匹配的算法，稱為匈牙利(Hungarian)算法。2022/7/25 算法基本思想 2022/7/25 算法描述 用匈牙利算法求下圖的最大匹配：x1x2y1x3x4x5y2y3y4y

14、5 例 題 （1）任給一個(gè)初始匹配；（2）若X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)（3）；x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)（3）在X中找一個(gè)非飽和點(diǎn)x2，V1=x2，V2=（4）若N(V1)=V2則停止，否則任選一點(diǎn)yN(V1)-V2x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)V1=x2,V2=N(V1)=y2, y3 （5）若y已飽和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對(duì)之進(jìn)行增廣；轉(zhuǎn)（2）】x1x2y1x3x4

15、x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)V1=V1x5=x2,x5；V2=V2 y3 =y3V1=x2,V2=（4）若N(V1)=V2則停止，否則任選一點(diǎn)yN(V1)-V2；x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)V1=x2,x5；V2=y3N(V1)=y2, y3 , y5 （5）若y已飽和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對(duì)之進(jìn)行增廣；轉(zhuǎn)（2）】x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5

16、),(x5,y3)V1=x2,x5；V2=y3；V1=V1x3=x2,x5, x3；V2=V2 y5 =y3 ,y5（4）若N(V1)=V2則停止，否則任選一點(diǎn)yN(V1)-V2；x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)V1=x2,x5, x3；V2 =y3 ,y5；N(V1)=y2, y3 , y5（5）若y已飽和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對(duì)之進(jìn)行增廣；轉(zhuǎn)（2）】x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x

17、5,y3)V1=x2,x5, x3；V2 =y3 ,y5；x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=M E(P)=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)（2）若X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)（3）；（3）在X中找一個(gè)非飽和點(diǎn)x0，V1=x0，V2=（4）若N(V1)=V2則停止，否則任選一點(diǎn)yN(V1)-V2x1x2y1x3x4x5y2y3y4y5V1=x4；V2 =M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)N(V1)=y3（5）若y已飽和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V

18、2 y； 轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對(duì)之進(jìn)行增廣；轉(zhuǎn)（2）】x1x2y1x3x4x5y2y3y4y5V1=x4；V2 =M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)V1=V1x2=x4,x2；V2=V2y3 =y3（4）若N(V1)=V2則停止，否則任選一點(diǎn)yN(V1)-V2x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)V1=x4,x2,；V2 =y3 N(V1)=y2, y3（5）若y已飽和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 轉(zhuǎn)（4）】，否則

19、【求一條從x0到y(tǒng)的可增廣道路P，對(duì)之進(jìn)行增廣；轉(zhuǎn)（2）】x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)V1=x4,x2,；V2 =y3 V1=V1x3=x4,x2 ,x3；V2=V2y2 =y3,y2（4）若N(V1)=V2則停止，否則任選一點(diǎn)yN(V1)-V2x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)V1=x4,x2 ,x3；V2=y3,y2N(V1)=y2, y3 , y5（5）若y已飽和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對(duì)之進(jìn)行增廣；轉(zhuǎn)（2）】x1x2y1x3x4