計(jì)算機(jī)科學(xué)廣泛應(yīng)用于運(yùn)籌學(xué)信息論控制論網(wǎng)絡(luò)理論課件

1、圖的基本概念計(jì)算機(jī)科學(xué)廣泛應(yīng)用于運(yùn)籌學(xué)，信息論，控制論，網(wǎng)絡(luò)理論，化學(xué)生物學(xué)，物理學(xué)。原因在于這些學(xué)科的許多實(shí)際問題和理論問題可以概括為圖論。第八、九章介紹與計(jì)算機(jī)科學(xué)關(guān)系密切的圖論內(nèi)容及其在實(shí)際中的應(yīng)用。8.1 無向圖及有向圖稱a,b | aAbB 為A與B的無序積，記作：A&B。習(xí)慣上，無序?qū),b改記成(a, b)有序組(a,b)均用無序積：設(shè)A，B為二集合，一、基本圖類及相關(guān)概念1. 無向圖無向圖：無向圖G是一個(gè)二元組，其中(1) V是一個(gè)非空集 頂點(diǎn)集V(G)，每個(gè)元素為頂點(diǎn)或結(jié)點(diǎn)；(2) E是無序積V & V的可重子集(元素可重復(fù)出現(xiàn))，E 邊集E(G)，E中元素稱為無向邊。v4

2、實(shí)際中，圖是畫出來的，畫法：用小圓圈表示V中的每一個(gè)元素，如果(a,b)E，則在頂點(diǎn)a與b之間連線段。如：adcbe1e1e2e3e4e5e6e1e2e3e4e5e6v1v2v3v5有向圖：有向圖D是一個(gè)二元組，其中(1) V是非空集 頂點(diǎn)集 V(D)(2) E是笛卡爾積VV的可重子集，其元素為有向邊 實(shí)際中，畫法同無向圖，只是要根據(jù)E中元素的次序，由第一元素用方向線段指向第二元素。2. 有向圖有限圖：V，E均為有窮集合零 圖：E 平凡圖：E 且 |V| = 1(n, m)圖：|V| = n 且 |E| = m頂與邊關(guān)聯(lián)：如果ek = (vi,vj) E，稱ek與vi關(guān)聯(lián)，或ek與vj關(guān)聯(lián)。3

3、. 相關(guān)概念頂與頂相鄰：如果ek = (vi,vj) E，稱vi與vj相鄰；環(huán)： ek = 中，若 vi = vj，則ek稱為環(huán)。 邊與邊相鄰：如果ek和ei至少有一個(gè)公共頂點(diǎn)關(guān)聯(lián)，則稱ek與ei相鄰。若ek為有向邊，則稱vi鄰接到vj, vj鄰接于vi 。孤立點(diǎn)：無邊關(guān)聯(lián)的頂點(diǎn)。平行邊：無向圖中，關(guān)聯(lián)一對結(jié)點(diǎn)的無向邊多于一條，平行邊的條數(shù)為重?cái)?shù)；多重圖：包含平行邊的圖。有向圖中，關(guān)聯(lián)一對頂點(diǎn)的無向邊多于一條，且始、終點(diǎn)相同。簡單圖：既不包含平行邊又不包含環(huán)的圖。度：(1) 在無向圖G = 中，與頂點(diǎn)v(vV)關(guān)聯(lián)的邊的數(shù)目(每個(gè)環(huán)計(jì)算兩次)，記作：d(v)。二、度(2) 在有向圖D = 中，

4、以頂點(diǎn)v(vV)作為始點(diǎn)的邊的數(shù)目，稱為該頂點(diǎn)的出度，記作： d+(v)；出度與入度之和，稱為頂點(diǎn)v的度：度是圖的性質(zhì)的重要判斷依據(jù)。d(v) = d+(v)+ d(v)以頂點(diǎn)v作為終點(diǎn)的邊的數(shù)目，稱為該頂點(diǎn)的入度，記作：d(v)。最大度： (G) = max d(v) | vV最小度： (G) = min d(v) | vV度與邊數(shù)的關(guān)系：在任何圖中，頂點(diǎn)度數(shù)的總和等于邊數(shù)之和的兩倍。握手定理的推論：任何圖中，度為奇數(shù)的頂點(diǎn)個(gè)數(shù)一定為偶數(shù)。(握手定理)出度與入度的關(guān)系：在有向圖中，各頂點(diǎn)的出度之和等于各頂點(diǎn)的入度之和。度數(shù)序列：設(shè)V = v1,v2,vn為圖G的頂點(diǎn)集，稱(d(v1), d(

5、v2), d(vn)為G的度數(shù)序列。度數(shù)序列之和必為偶數(shù)(?)。例8.1 (3,3,2,3)，(5,2,3,1,4)能成為圖的度數(shù)序列嗎？為什么？解：由于這兩個(gè)序列中，奇數(shù)個(gè)數(shù)均為奇數(shù)，由握手定理知，它們不能成為圖的度數(shù)序列。例8.2 已知圖G中有10條邊，4個(gè)3度頂點(diǎn)，其余頂點(diǎn)的度數(shù)均小于等于2，問G中至少有多少個(gè)頂點(diǎn)？為什么？解：圖中邊數(shù) m=10，由握手定理知，G中各頂點(diǎn)度數(shù)之和為20，4個(gè)3度頂點(diǎn)占去12度，還剩8度，若其余全是2度頂點(diǎn), 則需要4個(gè)頂點(diǎn)來占用8度，所以G至少有8個(gè)頂點(diǎn)。正則圖：各頂點(diǎn)的度都相同的圖為正則圖；各頂點(diǎn)的度均為k的圖為k次正則圖。完全圖：(1) 設(shè)G = 是

6、n階的無向簡單圖，如果G中任何一個(gè)頂點(diǎn)都與其余n1個(gè)頂點(diǎn)相鄰，則G為無向完全圖，記作：Kn。三、正則圖與完全圖(2) 設(shè)D = 是n階的有向簡單圖，如果D中任意頂點(diǎn)u，vV(uv)，即有有向邊 ，又有有向邊，則稱D為n階有向完全圖。如：四、子圖與母圖：(1) G = ， G = 若VV， EE，則G是G的母圖， G是G的子圖，記作： G G。(2) 若GG 且 V=V，則G是G的生成子圖。(3) 設(shè)V1V，且V1，以V1為頂點(diǎn)集，以2端點(diǎn)均在V1中的全體邊為邊集的G的子圖，稱為V1導(dǎo)出的導(dǎo)出子圖。(4) 設(shè)E1E，且E1，以E1為頂點(diǎn)集，以E1中邊關(guān)聯(lián)的頂點(diǎn)的全體為頂點(diǎn)集的G的子圖，稱為E1導(dǎo)

7、出的導(dǎo)出子圖。例8.3 列舉下圖的一些子圖、真子圖、生成子圖、導(dǎo)出子圖。e3e1e2e4e5v3v4v1v2解：自己對照定義做一做！(1) 子圖：子圖的定義？舉例(2) 真子圖：舉例(3) 生成子圖：定義？舉例(4) 導(dǎo)出子圖：定義？舉例補(bǔ)圖：給定一個(gè)圖G = ，以V為頂點(diǎn)集，以所有能使G成為完全圖的添加邊組成邊集的圖。記作：G五、補(bǔ)圖如:(1)(2)相對補(bǔ)圖：設(shè)GG, 如果另一個(gè)圖G = ，滿足 (1) E = E E(2) V中僅包含E中的邊所關(guān)聯(lián)的結(jié)點(diǎn)。則G是子圖G相對于G的補(bǔ)圖。如：圖為的子圖，則圖(1)(2)(3)為(1)相對于(2)的補(bǔ)圖。圖同構(gòu)：對于G = ，G = ，如果存在

8、g:VV 滿足： (1) 任意邊e = (vi,vj)E，當(dāng)且僅當(dāng)e = (g(vi),g(vj)E(2) e與e的重?cái)?shù)相同則說G G 由于同構(gòu)圖頂點(diǎn)之間一一對應(yīng)，邊之間一一對應(yīng)，關(guān)聯(lián)關(guān)系對應(yīng)相同，所以可以看成同一個(gè)圖。六、同構(gòu)圖例8.4 畫出4個(gè)頂點(diǎn)3條邊的所有可能非同構(gòu)的無向簡單圖。解：直觀上容易看出，下面三個(gè)圖是4個(gè)頂點(diǎn)3條邊的所有非同構(gòu)的無向簡單圖。例8.5 畫出3個(gè)頂點(diǎn)2條邊的所有可能非同構(gòu)的有向簡單圖。解： 3個(gè)頂點(diǎn)2條邊的無向簡單圖只有一個(gè)：由這個(gè)圖可派生出下列4個(gè)非同構(gòu)的有向簡單圖：課堂練習(xí)：畫出4個(gè)頂點(diǎn)4條邊的無向簡單圖。 8.2 通路、回路、圖的連通性通路與回路：給定圖G

9、= ，設(shè)G中頂點(diǎn)與邊的交替序列 = v0 e1 v1 e2 el vl 滿足：vi1vi是ei的端點(diǎn)，(G為有向圖時(shí), 要求vi1, vi分別為ei的始點(diǎn)、終點(diǎn))，i = 1,2, l，則為頂點(diǎn)v0到vl的通路。中邊的數(shù)目l稱為的長度。v0 = vl時(shí)，稱為回路。一、通路與回路的概念簡單通路： = v0 e1 v1 e2 ek vk為通路且邊e1 e2 ek 互不相同，又稱之為跡，可簡用v0 v1 vk 來表示。簡單回路 (v0 = vk)又稱為閉跡。初級通路或基本通路： = v0 e1 v1 e2 ek vk為通路且頂點(diǎn)v0 v1 vk 互不相同。初級通路一定是簡單通路，但簡單通路不一定是一

10、條初級通路?；净芈罚?v0 = vk。例8.6 就下面兩圖列舉長度為5的通路，簡單通路，回路，簡單回路，再列舉長度為3的基本通路和回路。v1e1e4v2v3v4v5e3e5e2e7e6(1)(2)v5v1e2e5v2v3v4e1e7e3e8e6e4解：試對照定義，自己做一做！如：v1(1)中 v1e1v2e2v5e3v1e1v2e4v3 為v1到v3的通路；v1e1v2e4v3e5v4e7v5e3v1 為v1到v1的一條簡單回路；v1e1v2e4v3e5v4e6v2e2v5 為v1到v5的一條簡單通路。e1e4v2v3v4v5e3e5e2e7e6(1)(2)中 v1e2v2e5v3e7v4

11、v1到v4的長度為 了的基本通路；v1e2v2e3v5e1v1 是v1到v1的長度為了的基本回路。(2)v5v1e2e5v2v3v4e1e7e3e8e6e4二、通路與回路的性質(zhì)：(1) 在一個(gè)n階圖中，如果從頂點(diǎn)vi到vj(vivj)存在通路，則從vi到vj存在長度小于或等于n1的通路。如果Ln1，則此通路的頂點(diǎn)數(shù)L+1n，從而必有頂點(diǎn)vs，它在序列中不止出現(xiàn)一次，即有序列vi vs vs vj 。證明：設(shè)vi vk vj為vi到vj的長度為L的一條通路，則序列中必有L+1個(gè)頂點(diǎn)。在路中去掉vs到vs的這些邊，至少去掉一條邊后仍是vi到vj的一條通路。此通路比原來如此重復(fù)下去，必可得到一條從v

12、i到vj的不多于n1條邊的通路。通路的長度至少少1。(2) 在n階圖中，如果從vi到vj (vivj)存在通路，則必存在從vi到vj 的長度小于等于 n1的基本通路。(3) 在n階圖中，如果存在從vi到自身的回路，則從vi 到自身存在長度等于n的回路。(4) 在n階圖中，如果從vi到自身存在一條簡單回路，則從vi 到自身存在長度等于n的初級回路。兩頂點(diǎn)連通：u,v為無向圖G的兩個(gè)頂點(diǎn)，u到v存在一條通路。連 通 圖：G 中任何兩個(gè)頂點(diǎn)是連通的；否則是分離圖。三、圖的連通性連通性的性質(zhì)：無向圖中頂點(diǎn)之間的連通關(guān)系是頂點(diǎn)集V上的等價(jià)關(guān)系。(1) 自反性：由于規(guī)定任何頂點(diǎn)到自身總是連通的；證明：(2

13、) 對稱性：無向圖中頂點(diǎn)之間的連通是相互的；(3) 傳遞性：由連通性的定義可知。連通分支：無向圖G中每個(gè)劃分塊稱為G的一個(gè)連通分支，p(G)表示連通分支的個(gè)數(shù)。p(G) = 1為連通圖。點(diǎn)割集：無向圖G = 為連通圖，如果VV，且在G中刪除V中所有頂點(diǎn)(包括與該頂點(diǎn)關(guān)聯(lián)的邊)后所得子圖是不連通的或是平凡圖，而刪除V中任何真子集中的頂點(diǎn)時(shí)，所得子圖仍連通，則V是G的點(diǎn)割集。 如果點(diǎn)割集中只有一個(gè)頂點(diǎn)，該點(diǎn)為割點(diǎn)。四、連通圖的連通度點(diǎn)連通度：G為無向連通圖，記k(G) = min|V| V是G的點(diǎn)割集，稱k(G)為G的點(diǎn)連通度。 由定義知，點(diǎn)連通度即使G不連通的需刪除頂點(diǎn)的最少數(shù)目。完全圖Kn的連

14、通度k(G) = n1。存在割點(diǎn)的連通圖連通度為1，分離圖的連通度為0；邊割集：設(shè)無向圖G = 連通，邊集EE，在G中刪除E中所有邊后所得子圖不連通，而刪除E中的任何子集中的邊后，所得子圖仍連通，則E為G的邊割集。如果邊割集中只有一邊時(shí)，該邊為割邊(或橋)邊連通度：設(shè)G為無向連通圖，記(G) = min| E | E是G的邊割集， (G)為G的邊連通度。連通度的性質(zhì)：k(G) (G) (G)五、有向圖的連通性：(1) 如果有向圖 D = 中所有有向邊的方向去掉后所得圖為無向連通圖，則說D為弱連通圖。(2) u,vV，如果存在u到v的一條通路，則說u可達(dá)v。(3) 弱連通圖中， 任何一對頂點(diǎn)之間

15、，至少有一頂點(diǎn)可達(dá)另一個(gè)頂點(diǎn)，則 是單向連通的；任何兩個(gè)頂點(diǎn)之間互相可達(dá)，稱強(qiáng)連通。有向連通圖的性質(zhì)：(1) 強(qiáng)連通一定單向連通，單向連通一定弱連通。反過來都不成立。(2) 有向圖D強(qiáng)連通，當(dāng)且僅當(dāng)D中存在一條回路，它至少經(jīng)過每個(gè)頂點(diǎn)一次。(充分性) 如果D中存在回路C，它經(jīng)過D中的每個(gè)頂點(diǎn)至少一次，則D中的任意兩個(gè)頂點(diǎn)都在回路中，所以，D中任意兩個(gè)頂點(diǎn)都是可達(dá)的，因而D是強(qiáng)連通的。證明：因?yàn)関i可達(dá)vi+1, i=1,2,，n1，讓這些通路首尾相連，(2) 有向圖D強(qiáng)連通，當(dāng)且僅當(dāng)D中存在一條回路，它至少經(jīng)過每個(gè)頂點(diǎn)一次。(必要性) D是強(qiáng)連通的，則D中任何兩個(gè)頂點(diǎn)都是可達(dá)的。則得一回路。顯

16、然每個(gè)頂點(diǎn)在回路中至少出現(xiàn)一次。證明：所以vi到vi+1存在通路，不妨設(shè)D中的頂點(diǎn)為v1,v2,vn，且vn到v1也存在通路，8.3 圖的矩陣表示鄰接矩陣：設(shè)G = 是一個(gè)簡單圖，它有n個(gè)頂點(diǎn)，V = v1,v2,vn，令aij = 1 E (或 (vi, vj)E)0 E (或 (vi, vj)E)稱A(G) = (aij) 為G的鄰接矩陣。一、鄰接矩陣及其性質(zhì)鄰接矩陣的特性：在無向圖中：(1) 鄰接陣是對稱陣；(2) 同一行或者同一列的元素和為對應(yīng)頂點(diǎn)的度數(shù)(3) 矩陣中所有元素的和為邊數(shù)的2倍在有向圖中：(1) 同一行的元素和為對應(yīng)頂點(diǎn)的出度(2) 同一列的元素和為對應(yīng)頂點(diǎn)的入度(3)

17、aij = 2 m (邊的數(shù)目) 鄰接矩陣可推廣到多重圖或帶權(quán)圖，這時(shí)令aij為vi到vj的邊的重?cái)?shù)或邊上的權(quán)值W(vi, vj)。鄰接陣多用于有向圖。關(guān)聯(lián)矩陣：(1) 設(shè)G = 為(n,m)無向圖, V = v1,v2,vn, E = e1, e2, em, 令：mij = 10稱M(G) = (mij)nxm為G的關(guān)聯(lián)矩陣。vi 關(guān)聯(lián) ejvi 不關(guān)聯(lián) ej二、關(guān)聯(lián)矩陣及其性質(zhì)(2) 設(shè)D = 是有向圖且無環(huán)，令：mij = 10則稱M(D) = (mij)nxm為D的關(guān)聯(lián)矩陣。1D中 vi 是 ej 的始點(diǎn)vi 與 ej 不關(guān)聯(lián)vi 是 ej 的終點(diǎn)無向圖的關(guān)聯(lián)矩陣的性質(zhì)：(握手定理)有

18、向圖的關(guān)聯(lián)矩陣的性質(zhì)：由mij的定義知通路數(shù)與回路數(shù)的矩陣算法：(1) 設(shè)A是有向圖D的鄰接矩陣，V = v1,v2,vn， Al (l1)中元素aij(l)為vi到vj長度為l的通路數(shù)通路總數(shù)回路數(shù)三、應(yīng)用1. 求通路數(shù)與回路數(shù)(2) 設(shè)A是有向圖D的鄰接矩陣，B1 = A，B2 = A+A2,，Br = A+A2+Ar，則Br中元素bij(r) 為D中vi到vj長度小于等于 r 的通路數(shù)，2. 求可達(dá)矩陣可達(dá)矩陣：設(shè)D = 為一有向圖，V = v1,v2,vn，令pij = 10i jpii = 1 i = 1,2,n 稱(pij)nxn 為D的可達(dá)矩陣。vi 可達(dá) vj否則例. 求下圖的

19、可達(dá)矩陣，判斷它是否為強(qiáng)連通圖？V1V4V2V3V5解：1. 寫出鄰接矩陣2. 計(jì)算 A2, A3, A4, A5.3. 計(jì)算 B = A +A2 + A3 + A4 + A5 , 并求出可達(dá)矩陣的求法：由鄰接矩陣A計(jì)算A2,A+A2, A+A2+A(n1) = B = (bij(n1)nn pij = 1 bij(n1) 00 bij(n1) = 0則 i jpii = 1即得可達(dá)矩陣 P(D) = (pij)nxn 8.4 最短路徑問題帶權(quán)圖：對于有向圖或無向圖的每條邊附加一個(gè)實(shí)數(shù)w(e)，則得帶權(quán)圖。如果G1是帶權(quán)圖G的子圖，稱w(e) 為邊e上的權(quán)(當(dāng)e = 時(shí)，權(quán)記作wij)，記作：

20、G = 一、帶權(quán)圖及其最短路徑問題G = 為帶權(quán)圖，且G中各邊帶的權(quán)均大于等于0，從頂點(diǎn)u到頂點(diǎn)v的所有通路中求帶權(quán)最小的通路問題，稱為最短路徑問題。最短路徑問題：如果v1v2 vn1vn是v1到vn的最短路徑，則v1v2 vn1也必然是v1從到vn1的最短路徑。求最短路徑的標(biāo)號法的基本思想：標(biāo)號法：(1) 符號說明(i) li(r)*為頂點(diǎn)v1到頂點(diǎn)vi最短路徑的權(quán)(ii) lj(r)為v1到vj最短路徑權(quán)的上界，如果vj獲得lj(r) ，稱vj在第r步獲得t標(biāo)號lj(r) (r0)如果頂點(diǎn)vi獲得了標(biāo)號li(r)*，稱vi在第r步獲得p標(biāo)號li(r)*(iii) Pr = v | v已獲得

21、p標(biāo)號，稱之為第r步通過集 (r0)(iv) Tr = V Pr 稱之為第r步未通過集 (r0)二、求最短路徑問題的標(biāo)號法(2) 算法：開始，r0，v1獲p標(biāo)號： l1(0)* = 0，P0 = v1，T0 = Vv1， vj (j1)的t標(biāo)號：lj(0) = w1j = w1j 0 v1與vj相鄰 v1與vj 不相鄰修改通過集和未通過集：Pr = Pr1vi， Tr = Tr1vi，step1. 求下一個(gè)p標(biāo)號頂點(diǎn)設(shè)lj(r)* = min lj(r1)，r1。vjTr1頂點(diǎn)vi處，表明vi獲得p標(biāo)號。查Tr：若Tr = ，則算法結(jié)束，否則轉(zhuǎn)step2將lj(r)*標(biāo)在相應(yīng)step2. 修改

22、Tr中各頂點(diǎn)的t標(biāo)號lj(r) = minlj(r1) , li(r)* +wij， li(r)* 是剛剛獲得p標(biāo)號頂點(diǎn)的p標(biāo)號。令r r+1，轉(zhuǎn)step1。例8.7 求下圖中頂點(diǎn)v0與v5之間的最短路徑v0v2v1v4v3v5121475326解：利用標(biāo)號法算法解此題開始，r0，v0獲 p標(biāo)號： l0(0)* = 0l1(0) = w01 = 1通過集P0 = v0，未通過集T0 = v1， v2 ，v3， v4，v5，l2(0) = w02 = 4l4(0) = = l5(0) l3(0) = w03 = 未通過集的 t 標(biāo)號：v0v2v1v4v3v5121475326第一步：r = 1，

23、計(jì)算 = l1(1)* = 1，所以i=1，P1 = v0, v1， T1 = v2,v3 ,v4,v5修改未通過集的t標(biāo)號：l2(1) = minl2(0), l1(1)* + w12 = min4,3 = 3l3(1) = minl3(0), l1(1)* + w13 = min,8 = 8l4(1) = minl4(0), l1(1)* + w14 = 6l5(1) = minl5(0), l1(1)* + w15 = vi獲 p標(biāo)號l1(1)*，修改通過集與未通過集:修改通過集與未通過集 P2 = v0, v1, v2，T2 = v3 ,v4,v5修改未通過集的t標(biāo)號：l3(2) =

24、minl3(1), l2(2)* + w23 = min8,3+ = 8l4(2) = minl4(1), l2(2)* + w24 = min6,3+1 = 4l5(2) = minl5(0), l2(2)* + w25 = min,3+ = 修改通過集與未通過集 P3 = v0, v1, v2 ,v4,T3 = v5 ,v3修改未通過集的t標(biāo)號：l3(3) = minl3(2), l4(3)* + w43 = min8,4+3 = 7l5(3) = minl5(2), l4(3)* + w45 = min,4+6 = 10修改通過集與未通過集 P4 = v0, v1, v2 ,v4 ,v3,T4 = v5修改未通過集的t標(biāo)號：l5(4) = minl5(3), l