1、第四部分圖論 School of Information Science and Engineering圖 論實(shí)例1： 多用戶操作系統(tǒng)中的進(jìn)程狀態(tài)變換 School of Information Science and Engineering實(shí)例2： “七橋問題” 哥尼斯堡城的普雷格爾河圖 論ABCDABCDe1e5e7e6e3e4e2V=A, B, C, D E=e1, e2, e3, e4, e5 , e6, e7后來歐拉證明這樣的路徑根本不存在。 School of Information Science and Engineering圖 論實(shí)例3：在機(jī)械加工中，經(jīng)常需要在一塊金屬薄板上

2、鉆若干孔 （或者是機(jī)械手在印刷電路板上安裝電子元件） 問如何確定鉆孔的次序,使之加工的時間最短？ 類似的問題： 旅行最優(yōu)問題, 工程最優(yōu)問題, 成本最低. School of Information Science and Engineering第十四章 圖的基本概念主要內(nèi)容圖通路與回路圖的連通性圖的矩陣表示 School of Information Science and Engineering14-1 圖定義一個圖表示為 G=, 其中 V(G): G的結(jié)點(diǎn)的非空集合，簡記成V。 E(G): 是G的邊的集合， 有時簡記成E。結(jié)點(diǎn)(Vertices)：用 表示, 旁邊標(biāo)上該結(jié)點(diǎn)的名稱。邊(E

3、dges) 有向邊: 帶箭頭的弧線。 從u到v的邊表示成 無向邊:不帶箭頭的弧線。 u和v間的邊表示成 (u,v) School of Information Science and Engineering14-1 圖實(shí)例 1. 設(shè) V1= v1, v2, ,v5, E1 = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 則 G1 = 為一無向圖2. 設(shè) V2 = a, b, c, d, E2 = , , , 則 G2 = 為一有向圖 School of Information Science and Enginee

4、ring14-1 圖相關(guān)概念：1. 圖 可用G泛指圖（無向的G或有向的D ） V(G), E(G), V(D), E(D) n階圖2. n 階零圖與平凡圖（ n 為頂點(diǎn)個數(shù)）3. 用 ek 表示無向邊或有向邊4. 頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系 關(guān)聯(lián)、關(guān)聯(lián)次數(shù) 環(huán) 孤立點(diǎn)5. 頂點(diǎn)之間的相鄰與鄰接關(guān)系 School of Information Science and Engineering14-1 圖6. 鄰域與關(guān)聯(lián)集 vV(G) (G為無向圖) v 的關(guān)聯(lián)集 vV(D) (D為有向圖)7. 標(biāo)定圖與非標(biāo)定圖8. 基圖 School of Information Science and Engineer

5、ing14-1 圖多重圖與簡單圖 簡單圖：不含有環(huán)和平行邊的圖。 多重圖：含有平行邊的圖。 School of Information Science and Engineering14-1 圖定義 (1) 設(shè)G=為無向圖, vV, d(v)v的度數(shù), 簡稱度 (2) 設(shè)D=為有向圖, vV, d+(v)v的入度 d(v)v的出度 d(v)v的度或度數(shù) (3) (G), (G) (4) +(D), +(D), (D), (D), (D), (D) (5) 奇度頂點(diǎn)與偶度頂點(diǎn) School of Information Science and Engineering14-1 圖握手定理 定理14

6、-1.1 設(shè)G=為任意無向圖，V=v1,v2,vn, |E|=m, 則證明： G中每條邊 (包括環(huán)) 均有兩個端點(diǎn)，所以在計算G中各頂點(diǎn)度數(shù)之和時，每條邊均提供2度，m 條邊共提供 2m 度.定理14-1.2 設(shè)D=為任意有向圖，V=v1,v2,vn, |E|=m, 則推論 任何圖 (無向或有向) 中，奇度頂點(diǎn)的個數(shù)是偶數(shù). School of Information Science and Engineering14-1 圖無向圖的結(jié)點(diǎn)度序列 V=v1, v2, , vn為無向圖G的頂點(diǎn)集，稱d(v1), d(v2), , d(vn)為G的度數(shù)序列 。非負(fù)整數(shù)列d=(d1, d2, , dn

7、)是可圖化的，是可簡單圖化的.n階k正則圖 一個無向簡單圖G中,如果(G)=(G)=k，則稱G為k-正則圖。Kn是 n1正則圖 School of Information Science and Engineering14-1 圖練習(xí):1.下面哪些數(shù)的序列,可能是一個圖度數(shù)序列? 如果是，試畫出它的圖。哪些是可簡單圖化的? a) (1, 2, 3, 4, 5) b) (2, 2, 2, 2, 2) c) (1, 2, 3, 2, 4)2.已知無向簡單圖G中,有10條邊，4個3度結(jié)點(diǎn),其余結(jié)點(diǎn)的度均小于或等于2，問G中至少有多少個結(jié)點(diǎn)？為什么？ School of Information Sci

8、ence and Engineering14-1 圖圖的同構(gòu) 設(shè)G1=, G2=為兩個無向圖(兩個有向圖)，若存在雙射函數(shù)f:V1V2, 對于vi,vjV1, (vi,vj)E1 當(dāng)且僅當(dāng) (f(vi),f(vj)E2 （E1 當(dāng)且僅當(dāng) E2 )并且, (vi,vj)（）與 (f(vi),f(vj)（）的重數(shù)相同，則稱G1與G2是同構(gòu)的，記作G1G2. 圖之間的同構(gòu)關(guān)系具有自反性、對稱性和傳遞性.能找到同構(gòu)的必要條件，但它們?nèi)皇浅浞謼l件： 邊數(shù)相同，頂點(diǎn)數(shù)相同; 度數(shù)序列相同; 對應(yīng)頂點(diǎn)的關(guān)聯(lián)集及鄰域的元素個數(shù)相同，等等若破壞必要條件，則兩圖不同構(gòu)判斷兩個圖同構(gòu)是個難題 School of

9、Information Science and Engineering14-1 圖圖同構(gòu)實(shí)例 (1) (2) (3) (4) 圖中，(1)與(2)不同構(gòu)（度數(shù)列不同），(3)與(4)也不同構(gòu). (1) (2) 問：圖中(1)與(2)的度數(shù)序列相同，它們同構(gòu)嗎？為什么？ School of Information Science and Engineering14-1 圖完全圖無向完全圖G是個無向簡單圖，如果每對不同頂點(diǎn)都相鄰，則稱G是個無向完全圖。如果G有n個結(jié)點(diǎn), 則記作Kn。簡單性質(zhì)：邊數(shù)有向完全圖G是個有向簡單圖，如果任意兩個不同頂點(diǎn)之間都有方向相反的邊,則稱它是有向完全圖。簡單性質(zhì)：邊

10、數(shù)競賽圖基圖為Kn的有向簡單圖. School of Information Science and Engineering14-1 圖子圖定義：G=, G=(1) GG G為G的子圖，G為G的母圖(2) 若GG且V=V，則稱G為G的生成子圖(3) 若VV或EE，稱G為G的真子圖(4) V（VV且V）的導(dǎo)出子圖，記作GV(5) E（EE且E）的導(dǎo)出子圖，記作GE School of Information Science and Engineering14-1 圖例 畫出K4的所有非同構(gòu)的生成子圖。 School of Information Science and Engineering定義

11、：設(shè)G=為n階無向簡單圖，以V為頂點(diǎn)集，以所有使G成為完全圖Kn的添加邊組成的集合為邊集的圖，稱為G的補(bǔ)圖，記作 。若G , 則稱G是自補(bǔ)圖。相對于K4, 求上面圖中所有圖的補(bǔ)圖，并指出哪些是自補(bǔ)圖. 問：互為自補(bǔ)圖的兩個圖的邊數(shù)有何關(guān)系？14-1 圖補(bǔ)圖 School of Information Science and Engineering14-2 通路與回路定義 給定圖G=（無向或有向的），G中頂點(diǎn)與邊的交替序列 = v0e1v1e2elvl，vi1, vi 是 ei 的端點(diǎn)。(1) 通路與回路： 為通路；若 v0=vl， 為回路，l 為回路長 度.(2) 簡單通路與回路：所有邊各異，

12、 為簡單通路，又若v0=vl， 為簡單回路(3) 初級通路(路徑)與初級回路(圈)： 中所有頂點(diǎn)各異，則稱 為初級通路(路徑)，又若除v0=vl，所有的頂點(diǎn)各不相同且所有的邊各異，則稱 為初級回路(圈)(4) 復(fù)雜通路與回路：有邊重復(fù)出現(xiàn)。 School of Information Science and Engineering14-2 通路與回路表示法 定義表示法 只用邊表示法 只用頂點(diǎn)表示法（在簡單圖中） 混合表示法環(huán)（長為1的圈）的長度為1，兩條平行邊構(gòu)成的圈長度為 2，無向簡單圖中，圈長3，有向簡單圖中圈的長度2. 不同的圈（以長度3的為例） 定義意義下 無向圖：圖中長度為l（l3）

13、的圈，定義意義下為2l個 有向圖：圖中長度為l（l3）的圈，定義意義下為l個 同構(gòu)意義下：長度相同的圈均為1個 School of Information Science and Engineering14-2 通路與回路定理14-2.1 在n 階圖G中，若從頂點(diǎn)vi 到vj（vivj）存在通路，則從vi 到 vj 存在長度小于或等于n1 的通路.推論 在 n 階圖G中，若從頂點(diǎn)vi 到 vj（vivj）存在通路，則從vi 到vj 存在長度小于或等于n1的初級通路（路徑）.定理14-2.2 在一個n 階圖G中，若存在 vi 到自身的回路，則一定存在vi 到自身長度小于或等于 n 的回路.推論

14、在一個n 階圖G中，若存在 vi 到自身的簡單回路，則一定存在長度小于或等于n 的初級回路. vs-1 vi+1 vt+1 vs = vt vs+1vi vt-1 vj vj-1. . School of Information Science and Engineering14-3 圖的連通性1. 無向圖的連通性兩個結(jié)點(diǎn)連通在無向圖中，結(jié)點(diǎn)u和v之間如果存在一條通路，則稱u與v是連通的。記作 uv 規(guī)定: 對任何結(jié)點(diǎn)u，uu。結(jié)點(diǎn)之間的連通關(guān)系是個等價關(guān)系 令G=是無向圖，R是V上連通關(guān)系，即 R=| u,v V且uv 顯然R具有自反、對稱和傳遞性。 于是可以求商集V/R。例： 給定右圖所示

15、 V/R= a,b,g，c,d,e,f，h School of Information Science and Engineering14-3 圖的連通性G的連通性與連通分支 若u, vV，uv，則稱G是連通的 V/R=V1,V2,Vk，稱等價類構(gòu)成的子圖GV1, GV2, ,GVk為G的連通分支，其個數(shù) p(G)=k (k1)； k=1，G是連通的。 下面實(shí)例中 p(G1)=3 p(G2)=2 p(G3)=1 School of Information Science and Engineering14-3 圖的連通性距離 u與v之間的距離：d(u,v)u與v之間長度最短的通路。 d(u,v

16、)的性質(zhì)： d(u,v)0, uv時d(u,v)= d(u,v)=d(v,u) d(u,v)+d(v,w)d(u,w)刪除頂點(diǎn)及刪除邊 Gv 從G中將v及關(guān)聯(lián)的邊去掉 GV從G中刪除V中所有的頂點(diǎn) Ge 將e從G中去掉 GE刪除E中所有邊 School of Information Science and Engineering14-3 圖的連通性點(diǎn)割集與邊割集定義： G=, VV V為點(diǎn)割集p(GV)p(G)且有極小性 v為割點(diǎn)v為點(diǎn)割集定義： G=, EE E是邊割集p(GE)p(G)且有極小性 e是割邊（橋）e為邊割集上例中v2,v5是點(diǎn)割集嗎？e7,e9,e5,e6 是邊割集嗎？例：v

17、1,v4，v6是點(diǎn)割集，v6是割點(diǎn)。e1,e2，e1,e3,e5,e6，e8等是邊割集，e8是橋。 School of Information Science and Engineering14-3 圖的連通性說明Kn中無點(diǎn)割集，Nn中既無點(diǎn)割集，也無邊割集，其中Nn為 n 階零圖. 若G 連通，E為邊割集，則 p(GE)=2，V為點(diǎn)割集，則 p(GV)2 點(diǎn)連通度 G為連通非完全圖，(G) = min |V |V 為點(diǎn)割集 規(guī)定 (Kn) = n1 若G非連通，(G) = 0; 若 (G)k，則稱G為 k-連通圖 邊連通度G為連通圖，(G) = min|E|E為邊割集 若G非連通，則(G)

18、= 0 若(G)r，則稱G是 r -邊連通圖問題：求上例中的點(diǎn)連通度和邊連通度。 School of Information Science and Engineering14-3 圖的連通性說明(Kn)=(Kn)=n1G非連通，則 =0若G中有割點(diǎn)，則=1，若有橋，則=1若(G)=k, 則G是1-連通圖，2-連通圖，k-連通圖，但不是(k+s)-連通圖，s1若(G)=r, 則G是1-邊連通圖，2-邊連通圖，r-邊連通圖，但不是(r+s)-邊連通圖，s1, , 之間的關(guān)系.定理14-3.1 (G)(G)(G)問題：請畫出一個的無向簡單圖。 School of Information Scien

19、ce and Engineering14-3 圖的連通性2. 有向圖的連通性定義 D=為有向圖 vi vj（vi 可達(dá) vj）vi 到vj 有通路 vi vj（vi 與vj 相互可達(dá)）性質(zhì) 具有自反性(vi vi)、傳遞性 具有自反性、對稱性、傳遞性 vi 到vj 的距離類似于無向圖中，只需注意距離表示法的不同(無向圖中d(vi,vj)，有向圖中d) 及 d無對稱性 School of Information Science and Engineering14-3 圖的連通性定義 D=為有向圖 D弱連通(連通)基圖為無向連通圖 D單向連通vi,vjV，vivj 或 vjvi D強(qiáng)連通vi,vj

20、V，vivj易知，強(qiáng)連通單向連通弱連通定理14-3.1 D強(qiáng)連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個頂點(diǎn)至少一次的回路。例 判斷下面圖的連通性。 School of Information Science and Engineering14-4 圖的矩陣表示 1. 鄰接矩陣 以結(jié)點(diǎn)與結(jié)點(diǎn)之間的鄰接關(guān)系確定的矩陣。定義設(shè)G=是個簡單圖，V=v1,v2,v3,vn , 一個nn階矩陣A=(aij)稱為G的鄰接矩陣。 其中：vi與vj鄰接, 即(vi,vj)E 或 E否則 School of Information Science and Engineering14-4 圖的矩陣表示 例： 給定無向圖G1和有向

21、圖G2如圖所示，求鄰接矩陣。性質(zhì) School of Information Science and Engineering鄰接矩陣的乘積14-4 圖的矩陣表示 School of Information Science and Engineering在(A(G1)2 中a342 =2 表示從v3到v4有長度為2的路有2條。 在(A(G1)3中a233 =6 表示從v2到v3有長度為3的路有6條。鄰接矩陣的乘積14-4 圖的矩陣表示為D中長度為 l 的通路總數(shù)，定理14-4.1 設(shè) A為有向圖 D 的鄰接矩陣，V=v1, v2, , vn為頂點(diǎn)集，則 A 的 l 次冪 Al（l1）中元素為D中

22、vi 到vj長度為 l 的通路數(shù)，其中為vi到自身長度為 l 的回路數(shù)，而為D 中長度為 l 的回路總數(shù). School of Information Science and Engineering例： 有向圖D如圖所示，求 A, A2, A3, A4，并回答諸問題：(1) D 中長度為1, 2, 3, 4的通路各有多少條？其中回路分別為多少條？(2) D 中長度小于或等于4的通路為多少條？其中有多少條回路？實(shí)例 School of Information Science and Engineering(1) D中長度為1的通路為8條，其中有1條是回路。 D中長度為2的通路為11條，其中有3條

23、是回路。 D中長度為3和4的通路分別為14和17條，回路分別為1與3條。(2) D中長度小于等于4的通路為50條，其中有8條是回路。求解 School of Information Science and Engineering2. 可達(dá)矩陣定義設(shè)G=是個簡單圖, V=v1, v2, v3, vn , 一個nn階矩陣P=(pij)稱為G的可達(dá)性矩陣。 其中:vi到vj可達(dá)（至少有一條通路）否則求可達(dá)矩陣兩種方法求可達(dá)性矩陣P： 方法1. 按照矩陣相乘分別求出A(k) (k2), 然后再。 方法2. 用求傳遞閉包的Warshall算法。 由定義不難看出, G 強(qiáng)連通當(dāng)且僅當(dāng) P(G)為全1矩陣.

24、14-4 圖的矩陣表示 School of Information Science and Engineering例：G2如圖所示, 求它的可達(dá)矩陣P。P=AA(2)A(3)A(4)A(5)14-4 圖的矩陣表示 School of Information Science and Engineering14-4 圖的矩陣表示用可達(dá)矩陣求強(qiáng)分圖下面看怎樣用P求強(qiáng)分圖先將P轉(zhuǎn)置得PT, 如果vi與vj相互可達(dá),則pij= pTij =1以G2為例說明。1111101011111110101101011P=1010011111101001111111111PT=PPT=10100010111010001011010111100011000001110011100111初等變換得v1v3v2v4v5 對PPT進(jìn)行初等變換, 第2行與第3行交換,再第2列與第3列交換, 最后得兩個強(qiáng)分圖：v1,v3和v2,v4,v5 School of Information Scien