離散數學及其應用第10章-特殊圖模型與算法(下)課件

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

2、/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 定理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

3、 例 題2022/7/19 例 題【例】證明圖（a）所示的圖G不是平面圖。2022/7/19計算機應用技術研究所33 平面圖與著色問題 平面圖的概念與性質 平面圖的對偶圖 著色問題與算法2022/7/19 對偶圖的概念2022/7/19 例 題2022/7/19 對偶圖的性質2022/7/19 對偶圖的定理2022/7/19計算機應用技術研究所38平面圖與著色問題平面圖的概念與性質平面圖的對偶圖著色問題與算法2022/7/19 四色猜想2022/7/19 應用實例【解】可用一個無向圖模型表示上述問題，圖的每個結點分別代表一種食物，如果兩種食物不能放在一起，則在這兩種食物之間畫一條無向邊。202

4、2/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 例 題2

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

6、。四色猜想：連通簡單平面圖的色數不超過4。2022/7/19 結點著色算法對下圖頂點進行著色。v1v2v3v4v5v7v6 例 題（1）對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）標頂點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）對頂點vi的所有鄰接點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）轉到（2），直到所有頂點都著色為止（2）標頂點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）對頂點vi的所有鄰接點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）轉到（2），直到所有頂點都著色為止（2）標頂點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）對頂點vi的所有鄰接點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）轉到（2），直到所有頂點都著色為止（2）標頂點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）對頂點vi的所有鄰接點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）轉到（2），直到所有頂點都著色為止（2）標頂點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）對頂點vi的所有鄰接點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）轉到（2），直到所有頂點都著色為止（2）標頂點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）對頂點vi的所有鄰接點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）轉到（2），直到所有頂點都著色為止（2）標頂點vi (i=1,2,n)的顏色集Ci的第一種顏色ckc3c1c2c3c2【例】用韋爾奇鮑威爾算法對圖(a)所示連通無向圖進行結點著色 例 題2022/7/19 本章學習內容平面圖與著色問題3網絡流圖及其優(yōu)化問題45特殊圖模型的應用2022/7/19計算機應用技術研究所78網絡流圖及其優(yōu)化問題2022/7/19計算機應用技術研究所79網絡流圖及其優(yōu)化問題流網絡與切割最大流求解算法2022/7/19 流網絡與切割2022/7/19 可行流2022/7/19 例題2022/7/19 幾個概念202

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

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

16、19例題2022/7/19例題6）類似地，按照步驟3再次進行標號。2022/7/19例題2022/7/19例題8）同理，再對源點s標號(-，)，其他結點均未標號。2022/7/19例題9）按步驟3，再次進行標號。2022/7/19例題2022/7/19例題2022/7/19例題2022/7/19例題2022/7/19例題2022/7/19例題【解】2022/7/19 本章學習內容平面圖與著色問題34網絡流圖及其優(yōu)化問題特殊圖模型的應用52022/7/19計算機應用技術研究所112特殊圖模型的應用2022/7/19計算機應用技術研究所113特殊圖模型的應用鼓輪設計問題最優(yōu)路線問題穩(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計算機應用技術研究所121 特殊圖模型的應用鼓輪設計問題最優(yōu)路線問題穩(wěn)定婚配問題2022/7/19 最優(yōu)路線問題如果想在較短的時間內旅游較多的景點，則需要確定一個合理的路線，盡量縮短旅游的路程，使總路程最短。該問題可用哈密頓圖模型求解。尋找旅游各個景點近似最佳旅行線路問題就轉化為：在給定的加權無向圖中，尋找從給定的結點出發(fā)，行遍所有結點僅一次再回到該指定的結點，使得總權數最

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