1、第七章第七章 圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析1.圖的基本概念圖的基本概念2.最小樹問題最小樹問題3.最短路問題最短路問題4.最大流問題最大流問題5.最小費(fèi)用最大流問題最小費(fèi)用最大流問題本本章章內(nèi)內(nèi)容容例：七橋問題AB CD問題：一個散步者能否走過七座橋，且每座橋只走問題：一個散步者能否走過七座橋，且每座橋只走 過一次，最后回到出發(fā)點(diǎn)。過一次，最后回到出發(fā)點(diǎn)。問題：能否從某一點(diǎn)開始一筆畫出這個圖形，最后問題：能否從某一點(diǎn)開始一筆畫出這個圖形，最后回到原點(diǎn)，而不重復(fù)?；氐皆c(diǎn)，而不重復(fù)。例：中國郵路問題例：中國郵路問題 一個郵遞員送信，要走完他所負(fù)責(zé)的全部街道分送一個郵遞員送信，要走完他所負(fù)責(zé)的全部街道

2、分送信件，最后返回郵局。郵遞員都會本能地以盡可能少的信件，最后返回郵局。郵遞員都會本能地以盡可能少的行程完成送信任務(wù)。行程完成送信任務(wù)。問題：問題：他如何走？他如何走？點(diǎn)：路口；點(diǎn)：路口；邊：兩路口之間道路，第邊：兩路口之間道路，第i條道路長條道路長ei。問題：求一個圈，過每邊至少一次，并使圈的長度最問題：求一個圈，過每邊至少一次，并使圈的長度最 短。短。例：四色猜想例：四色猜想 能否用四種顏色給地圖染色，使相鄰的國家有能否用四種顏色給地圖染色，使相鄰的國家有不同的顏色。不同的顏色。點(diǎn)：國家；點(diǎn)：國家；邊：兩個國家有公共邊界。邊：兩個國家有公共邊界。問題：問題：能否用四種顏色給平面圖的點(diǎn)染色，

3、使有公共能否用四種顏色給平面圖的點(diǎn)染色，使有公共 邊的點(diǎn)有不同的顏色。邊的點(diǎn)有不同的顏色。 有二十個頂點(diǎn)標(biāo)以二十個城市的名字，要求有二十個頂點(diǎn)標(biāo)以二十個城市的名字，要求游戲者找一條從某一城市出發(fā)的路線，它經(jīng)過每游戲者找一條從某一城市出發(fā)的路線，它經(jīng)過每一個城市恰好一次，并且最后回到出發(fā)點(diǎn)。一個城市恰好一次，并且最后回到出發(fā)點(diǎn)。 點(diǎn)：城市點(diǎn)：城市 邊：城市之間的道路邊：城市之間的道路問題：問題：游戲者怎么走才能恰好每個城市走一次，而游戲者怎么走才能恰好每個城市走一次，而 且不重復(fù)？如圖：且不重復(fù)？如圖：例：例： HamiltonHamilton 第一節(jié)第一節(jié) 圖的基本概念圖的基本概念點(diǎn)：研究對象

4、（陸地、路口、國家、球隊）；點(diǎn)：研究對象（陸地、路口、國家、球隊）；點(diǎn)間連線：對象之間的特定關(guān)系（陸地間有橋、路口點(diǎn)間連線：對象之間的特定關(guān)系（陸地間有橋、路口 之間道路、兩國邊界、兩球隊比賽及結(jié)果之間道路、兩國邊界、兩球隊比賽及結(jié)果)。對稱關(guān)系：橋、道路、邊界；對稱關(guān)系：橋、道路、邊界；用不帶箭頭的連線表示，稱為邊。用不帶箭頭的連線表示，稱為邊。非對稱關(guān)系：甲隊勝乙隊，用帶箭頭的連線表示，非對稱關(guān)系：甲隊勝乙隊，用帶箭頭的連線表示， 稱為弧。稱為弧。圖：點(diǎn)及邊（或?。┙M成。圖：點(diǎn)及邊（或?。┙M成。例：例：有甲、乙、丙、丁、戊五個球隊，各隊之間比賽有甲、乙、丙、丁、戊五個球隊，各隊之間比賽 情

5、況如表：情況如表： 甲甲 乙乙 丙丙 丁丁 戊戊 甲甲 勝勝 負(fù)負(fù) 勝勝 勝勝 乙乙 負(fù)負(fù) 勝勝 丙丙 勝勝 負(fù)負(fù) 勝勝 丁丁 負(fù)負(fù) 負(fù)負(fù) 負(fù)負(fù) 戊戊 負(fù)負(fù) 勝勝 點(diǎn)：球隊；點(diǎn)：球隊；連線：兩個球隊之間比賽過，如甲勝乙，用連線：兩個球隊之間比賽過，如甲勝乙，用 v1 v2表示。表示。v1v2v3v4v5一、圖的定義一、圖的定義定義定義1：一個圖，是由非空集合：一個圖，是由非空集合V(G)=vi 和和V(G)中中 元素的有序?qū)Γɑ驘o序?qū)Γ┑募显氐挠行驅(qū)Γɑ驘o序?qū)Γ┑募螮(G)=ek 所組成的二元組（所組成的二元組（ V(G)， E(G) ）所構(gòu)成。）所構(gòu)成。記為記為 G= （ V(G)，

6、E(G) ） 簡記簡記 G=（V，E）其中其中 V= vi 稱為點(diǎn)集，稱為點(diǎn)集，vi為點(diǎn)為點(diǎn) 。 E=ek稱為邊集，稱為邊集， ek為邊（或?。檫叄ɑ蚧。?當(dāng)當(dāng)V，E為有限集時，稱為有限集時，稱G為有限圖。否則稱為為有限圖。否則稱為 無無限圖。限圖。無向圖：由點(diǎn)及邊構(gòu)成無向圖：由點(diǎn)及邊構(gòu)成 ，邊，邊vi，vj有向圖：由點(diǎn)及弧構(gòu)成，?。ㄓ邢驁D：由點(diǎn)及弧構(gòu)成，?。?vi，vj） 圖圖G中點(diǎn)集中點(diǎn)集V的頂點(diǎn)個數(shù)，記為的頂點(diǎn)個數(shù)，記為p (G) ，邊數(shù)記為，邊數(shù)記為q(G),簡記簡記p，q。1. 簡單圖與多重圖簡單圖與多重圖 某條邊兩個端點(diǎn)相同，稱這條邊為環(huán)。某條邊兩個端點(diǎn)相同，稱這條邊為環(huán)。

7、若兩點(diǎn)之間有多于一條的邊，稱這些邊為多重邊。若兩點(diǎn)之間有多于一條的邊，稱這些邊為多重邊。 無環(huán)、無多重邊的無環(huán)、無多重邊的圖稱為簡單圖。圖稱為簡單圖。多重圖：無環(huán)、但多重圖：無環(huán)、但允許有多重邊。允許有多重邊。v1e1e2e3v2v3e5e4v4二、圖論中常用術(shù)語二、圖論中常用術(shù)語2. 相鄰與關(guān)聯(lián)相鄰與關(guān)聯(lián) 若邊若邊e=u，vE，稱，稱u，v是是e的端點(diǎn)，也稱的端點(diǎn)，也稱u，v是是相鄰的。稱相鄰的。稱e是點(diǎn)是點(diǎn)u（及點(diǎn)（及點(diǎn)v）的關(guān)聯(lián)邊。）的關(guān)聯(lián)邊。 若兩條邊有一個公共的端點(diǎn)，則稱這兩條邊相鄰接。若兩條邊有一個公共的端點(diǎn)，則稱這兩條邊相鄰接。 vivjevi，vj相鄰相鄰 e 與與vi，vj關(guān)

8、聯(lián)關(guān)聯(lián)vie1vjvke2 點(diǎn)與邊關(guān)聯(lián)點(diǎn)與邊關(guān)聯(lián)點(diǎn)與點(diǎn)點(diǎn)與點(diǎn)相鄰相鄰邊與邊相鄰接邊與邊相鄰接定理定理1 圖圖G=（V，E）中，所有點(diǎn)的次之和為邊數(shù)）中，所有點(diǎn)的次之和為邊數(shù)的兩倍，的兩倍， 即即3. 奇點(diǎn)與偶點(diǎn)奇點(diǎn)與偶點(diǎn)次為奇數(shù)的點(diǎn)稱為奇點(diǎn)，否則稱為偶點(diǎn)。次為奇數(shù)的點(diǎn)稱為奇點(diǎn)，否則稱為偶點(diǎn)。定理定理2 任一圖中奇點(diǎn)的個數(shù)為偶數(shù)。任一圖中奇點(diǎn)的個數(shù)為偶數(shù)。Vv2md(v)證明：證明：設(shè)設(shè)v0和和v e分別是分別是G中的奇點(diǎn)和偶點(diǎn)的集合，由中的奇點(diǎn)和偶點(diǎn)的集合，由 定理定理1，有，有因因 是偶數(shù)，是偶數(shù)， 也是偶數(shù)，故也是偶數(shù)，故必為偶數(shù)。即在一個圖中奇點(diǎn)的個數(shù)必為偶數(shù)。必為偶數(shù)。即在一個圖中奇點(diǎn)

9、的個數(shù)必為偶數(shù)。Vvd(v)0Vvi)d(vm2d(v)d(v)d(vVvVevVvi0 eVvd(v)4. 次與懸掛點(diǎn)、孤立點(diǎn)次與懸掛點(diǎn)、孤立點(diǎn)圖圖G中以點(diǎn)中以點(diǎn)v為端點(diǎn)的邊的數(shù)目，稱為為端點(diǎn)的邊的數(shù)目，稱為v在在G中的次，中的次， 記為記為d（v）。）。d(v1)=2 d(v2)=3 d(v3)=4 d(v4)=1 次為次為1 的點(diǎn)為的點(diǎn)為懸掛點(diǎn)懸掛點(diǎn)，懸掛點(diǎn)的關(guān)聯(lián)邊稱為，懸掛點(diǎn)的關(guān)聯(lián)邊稱為懸懸掛邊掛邊，次為零的點(diǎn)稱為，次為零的點(diǎn)稱為孤立點(diǎn)孤立點(diǎn)。v1e1e2e3v2v3e5e4v45. 鏈與圈鏈與圈 給定一個圖給定一個圖G=（V，E），），G中的一個中的一個點(diǎn)、邊交錯點(diǎn)、邊交錯序列序列（

10、vi1，ei1，vi2，ei2，vik-1，eik-1，vik），如果滿），如果滿足足eit=vit，vit+1（t=1，2，k-1），則稱為一條聯(lián)接），則稱為一條聯(lián)接vi1和和vik的的鏈鏈，記為，記為 =（vi1，vi2，vik）。）。 鏈（鏈（vi1，vi2，vik）中，若）中，若vi1=vik ，稱之為一，稱之為一個個圈圈，記為，記為C= （vi1，vi2，vik-1， vi1 ） 。初等鏈：鏈中點(diǎn)都不同。初等鏈：鏈中點(diǎn)都不同。簡單鏈：鏈中邊都不同。簡單鏈：鏈中邊都不同。（邊能否相同？）邊能否相同？）（點(diǎn)能否相同？）點(diǎn)能否相同？）v1v3v5e1e2v7v8e7v2v4v6e3e4e5

11、e6e8e9簡單鏈簡單鏈： 1=（v2，v1，v3，v6，v4，v3，v5）初等鏈初等鏈： 2=（v2，v1，v3，v5）簡單圈簡單圈：C1=（v1，v2，v4，v3，v5，v6，v3 ，v1 ）初等圈：初等圈：C2=（v1，v2，v4，v6，v5，v3 ，v1 ） 有向圖中，不考慮弧的方向，有類似鏈（圈）有向圖中，不考慮弧的方向，有類似鏈（圈）的定義。當(dāng)鏈（圈）上弧的方向一致時，稱為路的定義。當(dāng)鏈（圈）上弧的方向一致時，稱為路（回路）。（回路）。3. 連通圖連通圖 給定圖G=（V，E），任何兩點(diǎn)間至少有一條鏈，則稱G是連通圖，否則為不連通圖。 若G是不連通的，它的每個連通部分稱為G的連通分圖

12、。 三三 、一些特殊圖類、一些特殊圖類 1.1.平凡圖平凡圖 節(jié)點(diǎn)數(shù)n=1,邊數(shù)m=0的圖。2.2.零圖零圖 邊數(shù)m=0的圖。5. 完備圖完備圖無向圖的完備圖：任何兩點(diǎn)之間有一條邊；有向圖的完備圖：任何兩點(diǎn)u與v之間有兩條有向邊（u，v）及（v，u）。基本圖：把有向圖的每條邊除去方向得到的無向圖。 若V(G)=X Y,X Y= ，X 、Y中的任兩頂點(diǎn)不相鄰，則G稱為二分圖，記為（S,X,Y）。4.4.樹樹 無圈連通圖。6.6.二分圖二分圖9.網(wǎng)絡(luò)網(wǎng)絡(luò) 若對圖G=（V，E）中每條邊vi，vj賦予一個數(shù)wij，則稱wij為邊vi，vj的權(quán)，并稱圖G為網(wǎng)絡(luò)（或賦權(quán)圖）。網(wǎng)絡(luò)：無向網(wǎng)絡(luò)、有向網(wǎng)絡(luò)。7.

13、完全二分圖完全二分圖 若V(G)=(S,X,Y),如果任意X、Y、，都有，E，則稱G是完全的二分圖。8.正則圖正則圖 如果G中每個點(diǎn)的次數(shù)都相同，則G叫做正則圖。1. 子圖與支撐子圖子圖與支撐子圖定義定義2 給定圖給定圖G=（V，E），若圖），若圖G1=（V1，E1），其），其 中中V1 V，E1=uv|uvE，u，v v，則稱，則稱G1是是G的子圖。的子圖。定義定義3 給定圖給定圖G=（V，E），若圖），若圖G1=（V，E1），其），其 中中E1 E，則稱，則稱G1是是G的一個支撐子圖。的一個支撐子圖。點(diǎn)全部保留點(diǎn)全部保留（a）（b）子圖子圖（c）支撐子圖支撐子圖四四 、圖的運(yùn)算、圖的運(yùn)算

14、2.2.圖的收縮運(yùn)算圖的收縮運(yùn)算 設(shè)圖設(shè)圖G=(V,E)，V1 V,在在G中收縮中收縮V1是指在圖是指在圖G中，中，在在V1中的點(diǎn)重為一個點(diǎn)，中的點(diǎn)重為一個點(diǎn)，G與與V1中的點(diǎn)相關(guān)聯(lián)的邊變中的點(diǎn)相關(guān)聯(lián)的邊變?yōu)榕c這個新點(diǎn)相關(guān)聯(lián)的邊，稱這樣的圖為關(guān)于為與這個新點(diǎn)相關(guān)聯(lián)的邊，稱這樣的圖為關(guān)于V1收縮，收縮，記為記為GoV1。3. 割集割集 給定圖給定圖G=（V，E），點(diǎn)的子集），點(diǎn)的子集S V，T V，定，定義義G中中邊的集合邊的集合S，TG=uv|u s，v T為一個割集。為一個割集。若若X=v1,)(314121vvvvvvX 若若X V是是V的真子集，的真子集， X XXX,V )( X GX

15、,X常記為常記為v6v2v3v4v5v1v1v2v3v4v5v6若若X=v1，v2，,)(314121vvvvvvX 4.圖的同構(gòu)圖的同構(gòu)定義定義4 設(shè)圖設(shè)圖G=（V，E）與）與G1=（V1，E1），若它們），若它們的點(diǎn)之間存在一一對應(yīng)，并且保持同樣的相的點(diǎn)之間存在一一對應(yīng)，并且保持同樣的相 鄰關(guān)系，則稱鄰關(guān)系，則稱G與與G1同構(gòu)。記為同構(gòu)。記為G G1。v1v2v3v4abcdv1v2v3v4abcd?(a)(b)圖圖(a)和和(b)就為同構(gòu)就為同構(gòu)五、圖的矩陣表示五、圖的矩陣表示 圖的矩陣表示方法有：鄰接矩陣、關(guān)聯(lián)矩陣、可圖的矩陣表示方法有：鄰接矩陣、關(guān)聯(lián)矩陣、可達(dá)矩陣、權(quán)矩陣等。達(dá)矩陣、

16、權(quán)矩陣等。 1.1.鄰接矩陣鄰接矩陣 鄰接矩陣用于描述兩個頂點(diǎn)之間是否有邊（弧）相連。鄰接矩陣用于描述兩個頂點(diǎn)之間是否有邊（?。┫噙B。對于有n個頂點(diǎn)的無向圖G=(V,E) ，定義鄰接矩陣(B=bij)nn 。其中， Ev,v 0 Ev,v 1bjijiij對于有幾個頂點(diǎn)的有向圖G=(V,A) ，定義鄰接矩陣(B=bij)nn 。其中，A v,v 0A v,v 1b jijiij例題例題1 已知無向圖所示，求其鄰接矩陣。已知無向圖所示，求其鄰接矩陣。v5v3v1v2v4v6則 123456126 63456 0 1 1 0 0 01 0 1 1 1 0() 1 1 0 1 1 00 1 1 0

17、1 10 1 1 1 0 10 0 0 1 1 0ijvvvvvvvvRbvvvv顯然，無向圖的鄰接矩陣是關(guān)于對角線的對稱矩陣。 例例 2 已知：圖所示，求其鄰接矩陣。已知：圖所示，求其鄰接矩陣。v2v5v3v1v4v6則： v1 v2 v3 v4 v5 v6 v1 0 1 1 0 0 0 v2 0 0 1 1 1 0 v3 0 0 0 1 0 0 v4 0 0 0 0 1 1 v5 0 0 1 0 0 1 v6 0 0 0 0 0 066)(ijbB66)(ijbB其鄰接矩陣為：其鄰接矩陣為： 0100000100100010110011010A v4v5v2v1v3當(dāng)當(dāng)G為為無向圖無向圖時

18、，時，鄰接矩陣鄰接矩陣為為對稱對稱矩陣。矩陣。在有向圖中可達(dá)矩陣用于描述兩點(diǎn)之間是否有路相連,即R=(rij)nn , 其中， 2. 2.可達(dá)矩陣可達(dá)矩陣jijiijvv 0 vv 1 r 向）無法到達(dá)經(jīng)過一定的（弧箭頭方當(dāng)向）可到達(dá)經(jīng)過一定的（弧箭頭方當(dāng) 例題例題3 求例題求例題2的可達(dá)矩陣的可達(dá)矩陣則66)(ijrR v1 v2 v3 v4 v5 v6 v1 1 1 1 1 1 1 v2 0 1 1 1 1 1 v3 0 0 1 1 1 1 v4 0 0 0 1 1 1 v5 0 0 0 0 1 1 v6 0 0 0 0 0 13. 關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣有向圖的關(guān)聯(lián)矩陣也稱頂點(diǎn)邊關(guān)聯(lián)矩陣。設(shè)有向圖 G=(V,A)，其中rij=V=v1,v2,v3vn， ，則關(guān)聯(lián)矩陣可定義為 M=(mij)nm其中：無關(guān)是弧當(dāng)頂點(diǎn)的終點(diǎn)是弧當(dāng)頂點(diǎn)的起點(diǎn)是弧當(dāng)頂點(diǎn)jijijiij v 0 v 1 v 1m aaa例題例題4 4 求下圖的關(guān)聯(lián)矩陣求下圖的關(guān)聯(lián)矩陣v4v2v1v3a4a3a1a2a6a5則其關(guān)聯(lián)矩陣為： a1 a2 a3 a4 a5 a6 v1 0 1 -1 0 0 -1 v2 1 0 1 1 0 0 v3 -1 -1 0 0 1 0 v4 0 0 0 -1 -1 1 64)(ijmM 權(quán)矩陣是最流行的一種網(wǎng)絡(luò)矩陣表示法。對于有n個頂點(diǎn)的無向網(wǎng)絡(luò)G=(V,E,W) ,邊 vi,vj的