圖論模型基礎(chǔ)第1頁，共78頁，2023年，2月20日，星期六1.圖論的基本概念1)圖的概念2)賦權(quán)圖與子圖3)圖的矩陣表示4)圖的頂點度5)路和連通第2頁，共78頁，2023年，2月20日，星期六1)圖的概念

定義

一個圖G是指一個二元組(V(G),E(G))，其中:其中元素稱為圖G的頂點.組成的集合，即稱為邊集,其中元素稱為邊.

定義圖G的階是指圖的頂點數(shù)|V(G)|,用來表示；圖的邊的數(shù)目|E(G)|用來表示.也用來表示邊是非空有限集，稱為頂點集，1)2)

E(G)是頂點集V(G)中的無序或有序的元素偶對表示圖，簡記用第3頁，共78頁，2023年，2月20日，星期六

定義若一個圖的頂點集和邊集都是有限集，則稱其為有限圖.只有一個頂點的圖稱為平凡圖，其他的所有圖都稱為非平凡圖.第4頁，共78頁，2023年，2月20日，星期六

定義若圖G中的邊均為有序偶對,稱G為有向邊為無向邊，稱e連接和，頂點和稱圖.稱邊為有向邊或弧,稱是從連接，稱為e的尾，稱為e的頭.若圖G中的邊均為無序偶對，稱G為無向圖.稱為e的端點.既有無向邊又有有向邊的圖稱為混合圖.第5頁，共78頁，2023年，2月20日，星期六

常用術(shù)語1)邊和它的兩端點稱為互相關(guān)聯(lián).2)與同一條邊關(guān)聯(lián)的兩個端點稱為相鄰的頂點，與同一個頂點點關(guān)聯(lián)的兩條邊稱為相鄰的邊.3)端點重合為一點的邊稱為環(huán)，端點不相同的邊稱為連桿.4)若一對頂點之間有兩條以上的邊聯(lián)結(jié)，則這些邊稱為重邊．5)既沒有環(huán)也沒有重邊的圖，稱為簡單圖．第6頁，共78頁，2023年，2月20日，星期六

常用術(shù)語6)任意兩頂點都相鄰的簡單圖,稱為完全圖.記為Kv.7)若，

，且X中任意兩頂點不，

相鄰，Y中任意兩頂點不相鄰，則稱為二部圖或偶圖；若X中每一頂點皆與Y中一切頂點相鄰,稱為完全二部圖或完全偶圖,記為(m=|X|,n=|Y|)．8)圖叫做星.二部圖第7頁，共78頁，2023年，2月20日，星期六2)賦權(quán)圖與子圖

定義若圖的每一條邊e都賦以一個實數(shù)w(e)，稱w(e)為邊e的權(quán)，G連同邊上的權(quán)稱為賦權(quán)圖.

定義設(shè)和是兩個圖.1)若,稱是的一個子圖,記2)若，，則稱是的生成子圖.

3)若，且，以為頂點集，以兩端點均在中的邊的全體為邊集的圖的子圖，稱為的由導(dǎo)出的子圖，記為.4)若，且，以為邊集，以的端點集為頂點集的圖的子圖，稱為的由導(dǎo)出的邊導(dǎo)出的子圖，記為.第8頁，共78頁，2023年，2月20日，星期六3)若，且，以為頂點集，以兩端點均在中的邊的全體為邊集的圖的子圖，稱4)若，且，以為邊集，以的端點集為頂點集的圖的子圖，稱為的由導(dǎo)出的邊導(dǎo)出的子圖，記為.為的由導(dǎo)出的子圖，記為.第9頁，共78頁，2023年，2月20日，星期六3)圖的矩陣表示

鄰接矩陣:1)對無向圖，其鄰接矩陣，其中：(以下均假設(shè)圖為簡單圖).第10頁，共78頁，2023年，2月20日，星期六2)對有向圖,其鄰接矩陣,其中：第11頁，共78頁，2023年，2月20日，星期六其中：3)對有向賦權(quán)圖,其鄰接矩陣,對于無向賦權(quán)圖的鄰接矩陣可類似定義.第12頁，共78頁，2023年，2月20日，星期六關(guān)聯(lián)矩陣1)對無向圖，其關(guān)聯(lián)矩陣,其中：第13頁，共78頁，2023年，2月20日，星期六2)對有向圖，其關(guān)聯(lián)矩陣,其中：第14頁，共78頁，2023年，2月20日，星期六4)圖的頂點度定義1)在無向圖G中，與頂點v關(guān)聯(lián)的邊的數(shù)目(環(huán)算兩次),稱為頂點v的度或次數(shù)，記為d(v)或dG(v).稱度為奇數(shù)的頂點為奇點，度為偶數(shù)的頂點為偶點.2)在有向圖中，從頂點v引出的邊的數(shù)目稱為頂點

v的出度，記為d+(v)，從頂點v引入的邊的數(shù)目稱為

v的入度，記為d-(v).稱d(v)=d+(v)+d-(v)為頂點v的

度或次數(shù)．定理的個數(shù)為偶數(shù)．推論任何圖中奇點第15頁，共78頁，2023年，2月20日，星期六5)路和連通定義1)無向圖G的一條途徑（或通道或鏈）是指一個有限非空序列，它的項交替

地為頂點和邊，使得對，的端點是和,稱W是從到的一條途徑，或一條途徑.整數(shù)k稱為W的長.頂點和分別稱為的起點和終點,而稱為W的內(nèi)部頂點.2)若途徑W的邊互不相同但頂點可重復(fù)，則稱W為跡或簡單鏈.3)若途徑W的頂點和邊均互不相同，則稱W為路或路徑.一條起點為,終點為的路稱為路記為第16頁，共78頁，2023年，2月20日，星期六定義1)途徑中由相繼項構(gòu)成子序列稱為途徑W的節(jié).

2)起點與終點重合的途徑稱為閉途徑.

3)起點與終點重合的的路稱為圈(或回路)，長為k的圈稱為k階圈，記為Ck.

4)若在圖G中存在(u,v)路，則稱頂點u和v在圖G中連通.

5)若在圖G中頂點u和v是連通的，則頂點u和v之之間的距離d(u,v)是指圖G中最短(u,v)路的長；若沒沒有路連接u和v，則定義為無窮大.第17頁，共78頁，2023年，2月20日，星期六

6)圖G中任意兩點皆連通的圖稱為連通圖．

7)對于有向圖G，若，且有類似地，可定義有向跡，有向路和有向圈.頭和尾，則稱W為有向途徑.例在右圖中：途徑或鏈：跡或簡單鏈：路或路徑：圈或回路：第18頁，共78頁，2023年，2月20日，星期六2．最短路問題及算法最短路問題是圖論應(yīng)用的基本問題，很多實際問題，如線路的布設(shè)、運輸安排、運輸網(wǎng)絡(luò)最小費用流等問題,都可通過建立最短路問題模型來求解.最短路的定義最短路問題的兩種方法：Dijkstra和Floyd算法.1)求賦權(quán)圖中從給定點到其余頂點的最短路.2)求賦權(quán)圖中任意兩點間的最短路.第19頁，共78頁，2023年，2月20日，星期六

2)在賦權(quán)圖G中，從頂點u到頂點v的具有最小權(quán)定義1)若H是賦權(quán)圖G的一個子圖，則稱H的各邊的權(quán)和為H的權(quán).類似地，若稱為路P的權(quán)．若P(u,v)是賦權(quán)圖G中從u到v的路,稱的路P*(u,v)，稱為u到v的最短路．

3)把賦權(quán)圖G中一條路的權(quán)稱為它的長，把(u,v)路的最小權(quán)稱為u和v之間的距離，并記作d(u,v).第20頁，共78頁，2023年，2月20日，星期六1)賦權(quán)圖中從給定點到其余頂點的最短路假設(shè)G為賦權(quán)有向圖或無向圖，G邊上的權(quán)均非負．若，則規(guī)定最短路是一條路，且最短路的任一節(jié)也是最短路．求下面賦權(quán)圖中頂點u0到其余頂點的最短路．第21頁，共78頁，2023年，2月20日，星期六Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第22頁，共78頁，2023年，2月20日，星期六Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第23頁，共78頁，2023年，2月20日，星期六Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第24頁，共78頁，2023年，2月20日，星期六Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第25頁，共78頁，2023年，2月20日，星期六Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第26頁，共78頁，2023年，2月20日，星期六Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第27頁，共78頁，2023年，2月20日，星期六Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第28頁，共78頁，2023年，2月20日，星期六Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第29頁，共78頁，2023年，2月20日，星期六Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第30頁，共78頁，2023年，2月20日，星期六Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第31頁，共78頁，2023年，2月20日，星期六Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第32頁，共78頁，2023年，2月20日，星期六Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第33頁，共78頁，2023年，2月20日，星期六第34頁，共78頁，2023年，2月20日，星期六定義根據(jù)頂點v的標號l(v)的取值途徑，使到v的最短路中與v相鄰的前一個頂點w，稱為v的先驅(qū)點，記為z(v),即z(v)=w.先驅(qū)點可用于追蹤最短路徑.例5的標號過程也可按如下方式進行：首先寫出左圖帶權(quán)鄰接矩陣因G是無向圖，故W是對稱陣．第35頁，共78頁，2023年，2月20日，星期六第36頁，共78頁，2023年，2月20日，星期六第37頁，共78頁，2023年，2月20日，星期六Dijkstra算法：求G中從頂點u0到其余頂點的最短路設(shè)G為賦權(quán)有向圖或無向圖，G邊上的權(quán)均均非負.對每個頂點，定義兩個標記（l(v)，z(v)），其中:l(v)：表從頂點u0到v的一條路的權(quán)．

z(v)：v的先驅(qū)點，用以確定最短路的路線.l(v)為從頂點u0到v的最短路的權(quán)．算法的過程就是在每一步改進這兩個標記，使最終S：具有永久標號的頂點集.輸入:G的帶權(quán)鄰接矩陣w(u,v)備用-將求最短路與最短路徑結(jié)合起來:第38頁，共78頁，2023年，2月20日，星期六算法步驟：l(v)u0vl(u)uw(u,v)第39頁，共78頁，2023年，2月20日，星期六首先寫出帶權(quán)鄰接矩陣例求下圖從頂點u0到其余頂點的最短路．因G是無向圖，故W是對稱陣．第40頁，共78頁，2023年，2月20日，星期六第41頁，共78頁，2023年，2月20日，星期六見Matlab程序-Dijkstra.doc第42頁，共78頁，2023年，2月20日，星期六2)求賦權(quán)圖中任意兩頂點間的最短路算法的基本思想（I）求距離矩陣的方法.（II）求路徑矩陣的方法.（III）查找最短路路徑的方法.Floyd算法：求任意兩頂點間的最短路.舉例說明第43頁，共78頁，2023年，2月20日，星期六

算法的基本思想

第44頁，共78頁，2023年，2月20日，星期六（I）求距離矩陣的方法.第45頁，共78頁，2023年，2月20日，星期六（II）求路徑矩陣的方法.在建立距離矩陣的同時可建立路徑矩陣R．第46頁，共78頁，2023年，2月20日，星期六（III）查找最短路路徑的方法.然后用同樣的方法再分頭查找．若：第47頁，共78頁，2023年，2月20日，星期六（IV）Floyd算法：求任意兩頂點間的最短路.第48頁，共78頁，2023年，2月20日，星期六例求下圖中加權(quán)圖的任意兩點間的距離與路徑.第49頁，共78頁，2023年，2月20日，星期六插入點v1，得：矩陣中帶“=”的項為經(jīng)迭代比較以后有變化的元素.第50頁，共78頁，2023年，2月20日，星期六插入點v2，得：矩陣中帶“=”的項為經(jīng)迭代比較以后有變化的元素.第51頁，共78頁，2023年，2月20日，星期六插入點v3，得：第52頁，共78頁，2023年，2月20日，星期六插入點v4，得：插入點v5，得：第53頁，共78頁，2023年，2月20日，星期六插入點v6，得：第54頁，共78頁，2023年，2月20日，星期六故從v5到v2的最短路為8

由v6向v5追溯:由v6向v2追溯:所以從到的最短路徑為：見Matlab程序-Floyd.doc第55頁，共78頁，2023年，2月20日，星期六3．最小生成樹及算法1)樹的定義與樹的特征定義連通且不含圈的無向圖稱為樹．常用T表示.樹中的邊稱為樹枝.樹中度為1的頂點稱為樹葉.孤立頂點稱為平凡樹.平凡樹第56頁，共78頁，2023年，2月20日，星期六定理2設(shè)G是具有n個頂點的圖，則下述命題等價：1)G是樹（G無圈且連通）；2)G無圈，且有n-1條邊；3)G連通，且有n-1條邊；4)G無圈，但添加任一條新邊恰好產(chǎn)生一個圈;5)G連通，且刪去一條邊就不連通了（即G為最最小連通圖）；6)G中任意兩頂點間有唯一一條路.第57頁，共78頁，2023年，2月20日，星期六2）圖的生成樹定義若T是包含圖G的全部頂點的子圖,它又是樹,則稱T是G的生成樹.圖G中不在生成樹的邊叫做弦.定理3圖G=(V,E)有生成樹的充要條件是圖G是連通的.證明

必要性是顯然的.第58頁，共78頁，2023年，2月20日，星期六第59頁，共78頁，2023年，2月20日，星期六（II）找圖中生成樹的方法可分為兩種：避圈法和破圈法A避圈法:深探法和廣探法B破圈法第60頁，共78頁，2023年，2月20日，星期六A避圈法

定理3的充分性的證明提供了一種構(gòu)造圖的生成樹的方法.這種方法就是在已給的圖G中，每步選出一條邊使它與已選邊不構(gòu)成圈，直到選夠n-1條邊為止.這種方法可稱為“避圈法”或“加邊法”在避圈法中，按照邊的選法不同，找圖中生成樹的方法可分為兩種：深探法和廣探法.第61頁，共78頁，2023年，2月20日，星期六a)深探法若這樣的邊的另一端均已有標號，就退到標號為步驟如下：i)在點集V中任取一點u,ii)若某點v已得標號，檢端是否均已標號.若有邊vw之w未標號,則給w代v，重復(fù)ii).i-1的r點,以r代v,重復(fù)ii),直到全部點得到標號為止.給以標號0.查一端點為v的各邊，另一w以標號i+1，記下邊vw.令例用深探法求出下圖10的一棵生成樹

圖10012345678910111213第62頁，共78頁，2023年，2月20日，星期六13a)深探法圖100123456789101112步驟如下：若這樣的邊的另一端均已有標號，就退到標號為i)在點集V中任取一點u,ii)若某點v已得標號，檢端是否均已標號.若有邊vw之w未標號,則給w代v，重復(fù)ii).i-1的r點,以r代v,重復(fù)ii),直到全部點得到標號為止.給u以標號0.查一端點為v的各邊，另一w以標號i+1，記下邊vw.令例用深探法求出下圖10的一棵生成樹

第63頁，共78頁，2023年，2月20日，星期六3b)廣探法步驟如下：i)在點集V中任取一點u,ii)令所有標號i的點集為是否均已標號.對所有未標號之點均標以i+1,記下這些iii)對標號i+1的點重復(fù)步步驟ii)，直到全部點得到給u以標號0.Vi,檢查[Vi,V\Vi]中的邊端點邊.例用廣探法求出下圖10的一棵生成樹

圖101012213212234標號為止.圖10第64頁，共78頁，2023年，2月20日，星期六3b)廣探法步驟如下：i)在點集V中任取一點u,ii)令所有標號i的點集為是否均已標號.對所有未標號之點均標以i+1,記下這些iii)對標號i+1的點重復(fù)步步驟ii)，直到全部點得到給u以標號0.Vi,檢查[Vi,V\Vi]中的邊端點邊.例用廣探法求出下圖10的一棵生成樹

圖101012213212234標號為止.顯然圖10的生成樹不唯一.第65頁，共78頁，2023年，2月20日，星期六B破圈法相對于避圈法，還有一種求生成樹的方法叫做“破圈法”.這種方法就是在圖G中任取一個圈，任意舍棄一條邊，將這個圈破掉，重復(fù)這個步驟直到圖G中沒有圈為止.例用破圈法求出下圖的一棵生成樹.第66頁，共78頁，2023年，2月20日，星期六B破圈法例用破圈法求出下圖的另一棵生成樹.不難發(fā)現(xiàn)，圖的生成樹不是唯一的.第67頁，共78頁，2023年，2月20日，星期六3)最小生成樹與算法介紹最小樹的兩種算法：Kruskal算法（或避圈法）和破圈法.第68頁，共78頁，2023年，2月20日，星期六AKruskal算法（或避圈法）步驟如下：1)選擇邊e1，使得w(e1)盡可能??；2)若已選定邊，則從中選取，使得:i)為無圈圖，

ii)是滿足i)的盡可能小的權(quán)，3)當(dāng)?shù)?)步不能繼續(xù)執(zhí)行時，則停止.定理4由Kruskal算法構(gòu)作的任何生成樹都是最小樹.第69頁，共78頁，2023年，2月20日，星期六例10用Kruskal算法求下圖的最小樹.在左圖中權(quán)值最小的邊有任取一條在中選取權(quán)值最小的邊中權(quán)值最小邊有,從中選任取一條邊會與已選邊構(gòu)成圈,故停止,得中選取在中選取中選取.但與都第70頁，共78頁，2023年，2月20日，星期六B破圈法算法2步驟如下：1)從圖G中任選一棵樹T1.2)加上一條弦e1，T1+e1中立即生成一個圈.去掉此圈中最大權(quán)邊，得到新樹T2,以T2代T1,重復(fù)2)再檢查剩余的弦，直到全部弦檢查完畢為止.例11用破圈法求下圖的最小樹.先求出上圖的一棵生成樹.

加以弦e2,得到的圈v1v3v2v1,去掉最大的權(quán)邊e2,得到一棵新樹仍是原來的樹；

再加上弦e7，得到圈v4v5v2v