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

1、2022/7/19計(jì)算機(jī)應(yīng)用技術(shù)研究所11離散數(shù)學(xué)Discrete Mathematics 汪榮貴 教授合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院2022/7/19計(jì)算機(jī)應(yīng)用技術(shù)研究所2第10章 特殊圖模型與算法(下)2022/7/19 本章學(xué)習(xí)內(nèi)容網(wǎng)絡(luò)流圖及其優(yōu)化問(wèn)題4平面圖與著色問(wèn)題35特殊圖模型的應(yīng)用2022/7/19計(jì)算機(jī)應(yīng)用技術(shù)研究所4平面圖與著色問(wèn)題2022/7/19計(jì)算機(jī)應(yīng)用技術(shù)研究所5 平面圖與著色問(wèn)題 平面圖的概念與性質(zhì) 平面圖的對(duì)偶圖 著色問(wèn)題與算法2022/7/19 應(yīng)用實(shí)例 2022/7/19 交叉點(diǎn)與交叉邊2022/7/19 可平面圖 2022/7/19 平面圖的定義 2022/7

2、/19 非平面圖 2022/7/19 最大平面圖 2022/7/19 面與邊界思想2022/7/19 面與邊界的定義2022/7/19 對(duì)面理解2022/7/19 例 題2022/7/19 一點(diǎn)說(shuō)明2022/7/19 次數(shù)與邊的關(guān)系2022/7/19 歐拉公式2022/7/19 歐拉公式2022/7/19 歐拉公式2022/7/19 定理2022/7/19 定理2022/7/19 非平面圖的判定2022/7/19 例 題2022/7/19 定理2022/7/19 例 題2022/7/19 定義2022/7/19 例 題2022/7/19 定義2022/7/19庫(kù)拉托夫斯基定理2022/7/19

3、 例 題2022/7/19 例 題【例】證明圖（a）所示的圖G不是平面圖。2022/7/19計(jì)算機(jī)應(yīng)用技術(shù)研究所33 平面圖與著色問(wèn)題 平面圖的概念與性質(zhì) 平面圖的對(duì)偶圖 著色問(wèn)題與算法2022/7/19 對(duì)偶圖的概念2022/7/19 例 題2022/7/19 對(duì)偶圖的性質(zhì)2022/7/19 對(duì)偶圖的定理2022/7/19計(jì)算機(jī)應(yīng)用技術(shù)研究所38平面圖與著色問(wèn)題平面圖的概念與性質(zhì)平面圖的對(duì)偶圖著色問(wèn)題與算法2022/7/19 四色猜想2022/7/19 應(yīng)用實(shí)例【解】可用一個(gè)無(wú)向圖模型表示上述問(wèn)題，圖的每個(gè)結(jié)點(diǎn)分別代表一種食物，如果兩種食物不能放在一起，則在這兩種食物之間畫(huà)一條無(wú)向邊。202

4、2/7/19 應(yīng)用實(shí)例可通過(guò)對(duì)該圖的結(jié)進(jìn)行著色的方法實(shí)現(xiàn)對(duì)上述問(wèn)題的求解。具體地說(shuō)，就是對(duì)圖中每個(gè)結(jié)點(diǎn)分別涂上或者標(biāo)注一種顏色，并滿(mǎn)足相鄰的結(jié)點(diǎn)之間具有不同的顏色，將相同顏色結(jié)點(diǎn)所代表的食物放在同一個(gè)隔間，則所需要的最少顏色數(shù)目顯然就是所求的冰箱隔間數(shù)目。一種著色方案：2022/7/19 結(jié)點(diǎn)著色2022/7/19 例 題2022/7/19 例 題2022/7/19 例 題2022/7/19 點(diǎn)色數(shù)的性質(zhì)2022/7/19 布魯克斯定理2022/7/19 例 題2022/7/19 例 題2022/7/19 邊著色2022/7/19 維津定理2022/7/19 例 題2022/7/19 例 題2

5、022/7/19 例 題2022/7/19 例 題【解】（1）該問(wèn)題可用如圖所示二分圖G的邊著色方法求解。一節(jié)課的時(shí)段對(duì)應(yīng)邊的一個(gè)著色組。由于G是二分圖，故邊色數(shù)是G的最大度35，即最少總課時(shí)時(shí)段為35節(jié)。故平均每天要安排7節(jié)課。（2）若每天安排8節(jié)課，則由G的總邊數(shù)240知需要240/40=6間教室。2022/7/19 平面圖的面著色2022/7/19 面著色的定義2022/7/19 面著色猜想2022/7/19 面著色的性質(zhì)面著色可以轉(zhuǎn)化為點(diǎn)著色來(lái)完成【定理】地圖G是k-面可色的，當(dāng)且僅當(dāng)它的對(duì)偶圖G*是k-可色圖?！径ɡ怼咳魣DG是一個(gè)簡(jiǎn)單平面圖，則該圖中至少存在一個(gè)度數(shù)小于或等于5的結(jié)點(diǎn)

6、。四色猜想：連通簡(jiǎn)單平面圖的色數(shù)不超過(guò)4。2022/7/19 結(jié)點(diǎn)著色算法對(duì)下圖頂點(diǎn)進(jìn)行著色。v1v2v3v4v5v7v6 例 題（1）對(duì)i=1,2,n,作Ci=c1,c2,ci；v1v2v3v4v5v7v6C1=c1C2=c1,c2C3=c1,c2,c3C4=c1,c2,c3,c4C5=c1,c2,c3,c4,c5C6=c1,c2,c3,c4,c5,c6C7=c1,c2,c3,c4,c5,c6,c7 例 題（2）標(biāo)頂點(diǎn)vi (i=1,2,n)的顏色集Ci的第一種顏色ck；C1=c1C2=c1,c2C3=c1,c2,c3C4=c1,c2,c3,c4C5=c1,c2,c3,c4,c5C6=c1,

7、c2,c3,c4,c5,c6C7=c1,c2,c3,c4,c5,c6,c7v1v2v3v4v5v7v6c1 例 題（3）對(duì)頂點(diǎn)vi的所有鄰接點(diǎn)vj(ji)，作Cj= Cj-ck；v1v2v3v4v5v7v6c1C1=c1C2=c1,c2C3=c1,c2,c3C4=c1,c2,c3,c4C5=c1,c2,c3,c4,c5C6=c1,c2,c3,c4,c5,c6C7=c1,c2,c3,c4,c5,c6,c7C2=c2 C3=c2, c3 C7=c2,c3,c4,c5,c6,c7 C5=c2,c3,c4,c5 C6=c2,c3,c4,c5,c6 （4）轉(zhuǎn)到（2），直到所有頂點(diǎn)都著色為止（2）標(biāo)頂點(diǎn)v

8、i (i=1,2,n)的顏色集Ci的第一種顏色ckv1v2v3v4v5v7v6c1C1=c1C2=c2C3=c2,c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（3）對(duì)頂點(diǎn)vi的所有鄰接點(diǎn)vj(ji)，作Cj= Cj-ck；v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c2,c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2C3=c3 v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c

9、1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（4）轉(zhuǎn)到（2），直到所有頂點(diǎn)都著色為止（2）標(biāo)頂點(diǎn)vi (i=1,2,n)的顏色集Ci的第一種顏色ckc3v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（3）對(duì)頂點(diǎn)vi的所有鄰接點(diǎn)vj(ji)，作Cj= Cj-ck；c3C5=c2,c4,c5 C1=c1,c2,c4 v1v2v3v4v5v7v6c1C1=c1C2=c2C

10、3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（4）轉(zhuǎn)到（2），直到所有頂點(diǎn)都著色為止（2）標(biāo)頂點(diǎn)vi (i=1,2,n)的顏色集Ci的第一種顏色ckc3c1v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（3）對(duì)頂點(diǎn)vi的所有鄰接點(diǎn)vj(ji)，作Cj= Cj-ck；c3c1v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,

11、c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（4）轉(zhuǎn)到（2），直到所有頂點(diǎn)都著色為止（2）標(biāo)頂點(diǎn)vi (i=1,2,n)的顏色集Ci的第一種顏色ckc3c1c2v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（3）對(duì)頂點(diǎn)vi的所有鄰接點(diǎn)vj(ji)，作Cj= Cj-ck；c3c1c2C6=c3,c4,c5,c6 v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=

12、c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（4）轉(zhuǎn)到（2），直到所有頂點(diǎn)都著色為止（2）標(biāo)頂點(diǎn)vi (i=1,2,n)的顏色集Ci的第一種顏色ckc3c1c2c3v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（3）對(duì)頂點(diǎn)vi的所有鄰接點(diǎn)vj(ji)，作Cj= Cj-ck；c3c1c2C7=c2,c4,c5,c6,c7 c3v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c3,c

13、4,c5,c6C7=c2,c4,c5,c6,c7c2（4）轉(zhuǎn)到（2），直到所有頂點(diǎn)都著色為止（2）標(biāo)頂點(diǎn)vi (i=1,2,n)的顏色集Ci的第一種顏色ckc3c1c2c3c2【例】用韋爾奇鮑威爾算法對(duì)圖(a)所示連通無(wú)向圖進(jìn)行結(jié)點(diǎn)著色 例 題2022/7/19 本章學(xué)習(xí)內(nèi)容平面圖與著色問(wèn)題3網(wǎng)絡(luò)流圖及其優(yōu)化問(wèn)題45特殊圖模型的應(yīng)用2022/7/19計(jì)算機(jī)應(yīng)用技術(shù)研究所78網(wǎng)絡(luò)流圖及其優(yōu)化問(wèn)題2022/7/19計(jì)算機(jī)應(yīng)用技術(shù)研究所79網(wǎng)絡(luò)流圖及其優(yōu)化問(wèn)題流網(wǎng)絡(luò)與切割最大流求解算法2022/7/19 流網(wǎng)絡(luò)與切割2022/7/19 可行流2022/7/19 例題2022/7/19 幾個(gè)概念202

14、2/7/19 最大流問(wèn)題2022/7/19 殘留網(wǎng)絡(luò)2022/7/19 例題2022/7/19 增廣路徑2022/7/19 切割2022/7/19 例題2022/7/19最大流最小割定理2022/7/19計(jì)算機(jī)應(yīng)用技術(shù)研究所91網(wǎng)絡(luò)流圖及其優(yōu)化問(wèn)題流網(wǎng)絡(luò)與切割最大流求解算法2022/7/19Ford-Fulkerson算法Ford-Fulkerson算法是一種迭代算法，基本思路如下：首先，對(duì)所有結(jié)點(diǎn)u,vV令f(u,v)=0。然后，通過(guò)迭代的方式不斷在殘留網(wǎng)絡(luò)中尋找一個(gè)增廣路徑來(lái)增加流值，直到殘留網(wǎng)絡(luò)中不包括增廣路徑為止。2022/7/19Ford-Fulkerson算法2022/7/19算法

15、基本過(guò)程1）對(duì)網(wǎng)絡(luò)G=V,E初始化，使f(e)=0，eE； 2）給源點(diǎn)s標(biāo)號(hào)(-，)，其它結(jié)點(diǎn)均未標(biāo)號(hào)；3）依次選一個(gè)未標(biāo)號(hào)的結(jié)點(diǎn)，根據(jù)其方向進(jìn)行標(biāo)號(hào)，若當(dāng)前標(biāo)號(hào)的結(jié)點(diǎn)為匯點(diǎn)t，轉(zhuǎn)步驟4），否則轉(zhuǎn)步驟6）；4）選擇一條標(biāo)號(hào)過(guò)的增流路徑進(jìn)行增流；5）轉(zhuǎn)步驟2）；6）這時(shí)得到的f就是最大可行流。2022/7/19例題【例】對(duì)于如圖所示為初始網(wǎng)絡(luò)G，其中邊上的數(shù)字表示對(duì)應(yīng)邊的容量，下面介紹通過(guò)Ford-Fulkerson算法尋找其的最大可行流的具體實(shí)現(xiàn)過(guò)程2022/7/19例題2022/7/19例題2）給源點(diǎn)s標(biāo)號(hào)(-,)，其它結(jié)點(diǎn)均未標(biāo)號(hào)。2022/7/19例題2022/7/19例題2022/7/

16、19例題2022/7/19例題6）類(lèi)似地，按照步驟3再次進(jìn)行標(biāo)號(hào)。2022/7/19例題2022/7/19例題8）同理，再對(duì)源點(diǎn)s標(biāo)號(hào)(-，)，其他結(jié)點(diǎn)均未標(biāo)號(hào)。2022/7/19例題9）按步驟3，再次進(jìn)行標(biāo)號(hào)。2022/7/19例題2022/7/19例題2022/7/19例題2022/7/19例題2022/7/19例題2022/7/19例題【解】2022/7/19 本章學(xué)習(xí)內(nèi)容平面圖與著色問(wèn)題34網(wǎng)絡(luò)流圖及其優(yōu)化問(wèn)題特殊圖模型的應(yīng)用52022/7/19計(jì)算機(jī)應(yīng)用技術(shù)研究所112特殊圖模型的應(yīng)用2022/7/19計(jì)算機(jī)應(yīng)用技術(shù)研究所113特殊圖模型的應(yīng)用鼓輪設(shè)計(jì)問(wèn)題最優(yōu)路線(xiàn)問(wèn)題穩(wěn)定婚配問(wèn)題20

17、22/7/19 三位輪鼓 2022/7/19 三位輪鼓 2022/7/19 8位布魯英序列2022/7/19 四位輪鼓 2022/7/19 四位輪鼓2022/7/19 四位輪鼓2022/7/19 四位輪鼓 2022/7/19計(jì)算機(jī)應(yīng)用技術(shù)研究所121 特殊圖模型的應(yīng)用鼓輪設(shè)計(jì)問(wèn)題最優(yōu)路線(xiàn)問(wèn)題穩(wěn)定婚配問(wèn)題2022/7/19 最優(yōu)路線(xiàn)問(wèn)題如果想在較短的時(shí)間內(nèi)旅游較多的景點(diǎn)，則需要確定一個(gè)合理的路線(xiàn)，盡量縮短旅游的路程，使總路程最短。該問(wèn)題可用哈密頓圖模型求解。尋找旅游各個(gè)景點(diǎn)近似最佳旅行線(xiàn)路問(wèn)題就轉(zhuǎn)化為：在給定的加權(quán)無(wú)向圖中，尋找從給定的結(jié)點(diǎn)出發(fā)，行遍所有結(jié)點(diǎn)僅一次再回到該指定的結(jié)點(diǎn)，使得總權(quán)數(shù)最

18、小，即總路程最短?？梢赃\(yùn)用圖論中的最鄰近插入法來(lái)尋找近似最佳旅游線(xiàn)路和路程。2022/7/19 算法步驟2022/7/19 例題2022/7/19 例題2022/7/19 例題在上表所示回路中選取長(zhǎng)度最短的兩個(gè)回路1326751或1675231，其長(zhǎng)度均為75。將結(jié)點(diǎn)4分別插入上面的兩個(gè)最短回路，得到如表所示的回路及其長(zhǎng)度。在表所示的回路中，選取長(zhǎng)度最短的旅程12345761，其長(zhǎng)度為125，則該回路就是所求的近似最佳旅游線(xiàn)路2022/7/19 貨郎擔(dān)問(wèn)題遍歷多個(gè)景點(diǎn)的最短旅游路線(xiàn)問(wèn)題，其實(shí)就是從具有n個(gè)結(jié)點(diǎn)的無(wú)向帶權(quán)完全圖中尋找一條哈密頓回路的問(wèn)題。如果景點(diǎn)個(gè)數(shù)較多的時(shí)候，比如說(shuō)幾十個(gè)或者上百個(gè)，則上述算法就非常復(fù)雜甚至不可行。這其實(shí)是圖論中的一個(gè)著名問(wèn)題，通常稱(chēng)之為貨郎擔(dān)問(wèn)題。因?yàn)樵搯?wèn)題也可以描述為：某地區(qū)共有n個(gè)村莊，某