離散數(shù)學(xué)圖的基本概論ppt課件

1、計(jì)算機(jī)科學(xué)廣泛應(yīng)用于運(yùn)籌學(xué)，信息計(jì)算機(jī)科學(xué)廣泛應(yīng)用于運(yùn)籌學(xué)，信息論，控制論，網(wǎng)絡(luò)理論，化學(xué)生物學(xué)，物理論，控制論，網(wǎng)絡(luò)理論，化學(xué)生物學(xué)，物理學(xué)。原因在于這些學(xué)科的許多實(shí)際問題和理學(xué)。原因在于這些學(xué)科的許多實(shí)際問題和理論問題可以概括為圖論。第八、九章介紹與論問題可以概括為圖論。第八、九章介紹與計(jì)算機(jī)科學(xué)關(guān)系密切的圖論內(nèi)容及其在實(shí)際計(jì)算機(jī)科學(xué)關(guān)系密切的圖論內(nèi)容及其在實(shí)際中的應(yīng)用。中的應(yīng)用。稱稱a,b | aAbB 為為A與與B的無序積，記作：的無序積，記作：A&B。習(xí)慣上，無序?qū)α?xí)慣上，無序?qū),b改記成改記成(a, b)有序組有序組(a,b)均用均用無序積：設(shè)無序積：設(shè)A，B為二集合，為

2、二集合，一、基本圖類及相關(guān)概念1. 無向圖無向圖：無向圖G是一個二元組，其中(1) V是一個非空集 頂點(diǎn)集V(G)，每個元素為頂點(diǎn)或結(jié)點(diǎn)；(2) E是無序積V & V的可重子集(元素可重復(fù)出現(xiàn))，E 邊集E(G)，E中元素稱為無向邊。v4 實(shí)際中，圖是畫出來的，畫法：用小圓圈表示V中的每一個元素，假如(a,b)E，則在頂點(diǎn)a與b之間連線段。如：adcbe1e1e2e3e4e5e6e1e2e3e4e5e6v1v2v3v5有向圖：有向圖有向圖：有向圖D是一個二元組是一個二元組，其中，其中(1) V是非空集是非空集 頂點(diǎn)集頂點(diǎn)集 V(D)(2) E是笛卡爾積是笛卡爾積VV的可重子集，的可重子

3、集，其元素為有向邊其元素為有向邊 實(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. 相關(guān)概念頂與頂相鄰：如果頂與頂相鄰：如果ek = (vi,vj) E，稱，稱vi與與vj相相鄰；鄰；環(huán)：環(huán)： ek = 中，假設(shè)中，假設(shè) vi = vj，則，則ek稱為環(huán)。稱為環(huán)。 邊與邊相鄰：如果邊與邊相鄰：如果ek和和ei至少有一個公共頂點(diǎn)關(guān)至少有一個公共頂點(diǎn)關(guān)

4、聯(lián)，則稱聯(lián)，則稱ek與與ei相鄰。相鄰。若若ek為有向邊，則稱為有向邊，則稱vi鄰接到鄰接到vj, vj鄰接于鄰接于vi 。孤立點(diǎn)：無邊關(guān)聯(lián)的頂點(diǎn)。孤立點(diǎn)：無邊關(guān)聯(lián)的頂點(diǎn)。平行邊：無向圖中，關(guān)聯(lián)一對結(jié)點(diǎn)的無向邊平行邊：無向圖中，關(guān)聯(lián)一對結(jié)點(diǎn)的無向邊多于一條，平行邊的條數(shù)為重數(shù)；多于一條，平行邊的條數(shù)為重數(shù)；多重圖：包含平行邊的圖。多重圖：包含平行邊的圖。有向圖中，關(guān)聯(lián)一對頂點(diǎn)的無向邊有向圖中，關(guān)聯(lián)一對頂點(diǎn)的無向邊多于一條，且始、終點(diǎn)相同。多于一條，且始、終點(diǎn)相同。簡單圖：既不包含平行邊又不包含環(huán)的圖。簡單圖：既不包含平行邊又不包含環(huán)的圖。度：(1) 在無向圖G = 中，與頂點(diǎn)v(vV)關(guān)聯(lián)的邊

5、的數(shù)目(每個環(huán)計(jì)算兩次)，記作：d(v)。二、度(2) 在有向圖D = 中，以頂點(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ù)的關(guān)系：在任何圖中，頂點(diǎn)度數(shù)的總和等于邊數(shù)之和的兩倍?？偤偷扔谶厰?shù)之和的兩倍。Vv|2)(Evd即握手定理的推論：任何圖中，度為奇數(shù)的

6、頂握手定理的推論：任何圖中，度為奇數(shù)的頂點(diǎn)個數(shù)一定為偶數(shù)。點(diǎn)個數(shù)一定為偶數(shù)。(握手定理握手定理)出度與入度的關(guān)系：在有向圖中，各頂點(diǎn)的出度與入度的關(guān)系：在有向圖中，各頂點(diǎn)的出度之和等于各頂點(diǎn)的入度之和。出度之和等于各頂點(diǎn)的入度之和。度數(shù)序列：設(shè)度數(shù)序列：設(shè)V = v1,v2,vn為圖為圖G的頂點(diǎn)集，的頂點(diǎn)集，稱稱(d(v1), d(v2), d(vn)為為G的度的度數(shù)序列。數(shù)序列。度數(shù)序列之和必為偶數(shù)度數(shù)序列之和必為偶數(shù)(?)。mvdvdniinii11)()(例例8.1 (3,3,2,3)，(5,2,3,1,4)能成為圖的度能成為圖的度數(shù)序列嗎？為什么？數(shù)序列嗎？為什么？解：由于這兩個序列中

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

8、相同的圖為正則圖；各頂點(diǎn)的度均為各頂點(diǎn)的度均為k的圖為的圖為k次正則圖。次正則圖。完全圖：完全圖：(1) 設(shè)設(shè)G = 是是n階的無向簡單圖，如果階的無向簡單圖，如果G中任何一個頂點(diǎn)都與其余中任何一個頂點(diǎn)都與其余n1個頂點(diǎn)相個頂點(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è)

9、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)出的導(dǎo)出子圖。例例8.3 列舉下圖的一些子圖、列舉下圖的一些子圖、真子圖、生成子圖、真子圖、生成子圖、導(dǎo)出子圖。導(dǎo)出子圖。e3e1e2e4e5v3v4v1v2解：自己對照定義做一做！解：自己對照定義做一做！(1) 子圖：子圖的定義？舉例(2) 真子圖：舉例(3) 生成子圖：定義？舉例(4) 導(dǎo)出子圖：定義？舉例補(bǔ)圖：給定一個圖補(bǔ)圖：給定一個圖G = ，以，以V為頂點(diǎn)集，為頂點(diǎn)集，以所有能使以所有能使

10、G成為完全圖的添加邊組成邊成為完全圖的添加邊組成邊集的圖。記作：集的圖。記作：G五、補(bǔ)圖如:(1)(2)相對補(bǔ)圖：設(shè)相對補(bǔ)圖：設(shè)GG, 如果另一個圖如果另一個圖G = ，滿足，滿足 (1) E = E E(2) V中僅包含中僅包含E中的邊所關(guān)聯(lián)的結(jié)點(diǎn)。中的邊所關(guān)聯(lián)的結(jié)點(diǎn)。則則G是子圖是子圖G相對于相對于G的補(bǔ)圖。的補(bǔ)圖。如：圖為的子圖，則圖(1)(2)(3)為(1)相對于(2)的補(bǔ)圖。圖同構(gòu)：對于圖同構(gòu)：對于G = ，G = ，如果，如果存在存在 g:VV 滿足：滿足： (1) 任意邊任意邊e = (vi,vj)E，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)e = (g(vi),g(vj)E(2) e與與e的重數(shù)相同

11、的重數(shù)相同則說則說G G 由于同構(gòu)圖頂點(diǎn)之間一一對應(yīng)，邊之間一一對應(yīng)，關(guān)聯(lián)關(guān)系對應(yīng)相同，所以可以看成同一個圖。六、同構(gòu)圖例例8.4 畫出畫出4個頂點(diǎn)個頂點(diǎn)3條邊的所有可能非條邊的所有可能非同構(gòu)的無向簡單圖。同構(gòu)的無向簡單圖。解：直觀上容易看出，下面三個圖是解：直觀上容易看出，下面三個圖是4個頂個頂點(diǎn)點(diǎn)3條邊的所有非同構(gòu)的無向簡單圖。條邊的所有非同構(gòu)的無向簡單圖。例例8.5 畫出畫出3個頂點(diǎn)個頂點(diǎn)2條邊的所有可能非同構(gòu)的有條邊的所有可能非同構(gòu)的有向簡單圖。向簡單圖。解：解： 3個頂點(diǎn)個頂點(diǎn)2條邊的無向簡單圖只有一個：條邊的無向簡單圖只有一個：由這個圖可派生出下列4個非同構(gòu)的有向簡單圖：課堂練習(xí)：

12、畫出4個頂點(diǎn)4條邊的無向簡單圖。通路與回路：給定圖G = ，設(shè)G中頂點(diǎn)與邊的交替序列 = v0 e1 v1 e2 el vl 滿足：vi1vi是ei的端點(diǎn)，(G為有向圖時, 要求vi1, vi分別為ei的始點(diǎn)、終點(diǎn))，i = 1,2, l，那么為頂點(diǎn)v0到vl的通路。中邊的數(shù)目l稱為的長度。v0 = vl時，稱為回路。一、通路與回路的概念簡單通路： = 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

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

14、簡單回路；v1e1v2e4v3e5v4e6v2e2v5 為v1到v5的一條簡單通路。e1e4v2v3v4v5e3e5e2e7e6(1)(2)中 v1e2v2e5v3e7v4 v1到v4的長度為 了的基本通路；v1e2v2e3v5e1v1 是v1到v1的長度為了的基本回路。(2)v5v1e2e5v2v3v4e1e7e3e8e6e4二、通路與回路的性質(zhì)：(1) 在一個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è)證明：設(shè)vi v

15、k vj為為vi到到vj的長度為的長度為L的一條通的一條通路，則序列中必有路，則序列中必有L+1個頂點(diǎn)。個頂點(diǎn)。在路中去掉vs到vs的這些邊，至少去掉一條邊后仍是vi到vj的一條通路。此通路比原來如此重復(fù)下去，必可得到一條從vi到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為無向圖

16、G的兩個頂點(diǎn)，u到v存在一條通路。連 通 圖：G 中任何兩個頂點(diǎn)是連通的；否則是分離圖。三、圖的連通性連通性的性質(zhì)：無向圖中頂點(diǎn)之間的連通關(guān)系是頂點(diǎn)集V上的等價關(guān)系。(1) 自反性：由于規(guī)定任何頂點(diǎn)到自身總是連通的；證明：證明：(2) 對稱性：無向圖中頂點(diǎn)之間的連通是相互的；(3) 傳遞性：由連通性的定義可知。連通分支：無向圖G中每個劃分塊稱為G的一個連通分支，p(G)表示連通分支的個數(shù)。p(G) = 1為連通圖。點(diǎn)割集：無向圖G = 為連通圖，如果VV，且在G中刪除V中所有頂點(diǎn)(包括與該頂點(diǎn)關(guān)聯(lián)的邊)后所得子圖是不連通的或是平凡圖，而刪除V中任何真子集中的頂點(diǎn)時，所得子圖仍連通，則V是G的點(diǎn)

17、割集。 如果點(diǎn)割集中只有一個頂點(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的連通度的連通度k(G) = n1。存在割點(diǎn)的連通圖連通度為存在割點(diǎn)的連通圖連通度為1，分離圖的連通度為分離圖的連通度為0；邊割集：設(shè)無向圖G = 連通，邊集EE，在G中刪除E中所有邊后所得子圖不連通，而刪除E中的任何子集中的邊后，所得子圖仍連通，則E為G的邊割集。如果邊割集中只有一邊時，該邊為割邊(或橋)邊連通度：設(shè)G為無向連通圖，記(G) = min| E |

18、 E是G的邊割集， (G)為G的邊連通度。連通度的性質(zhì)：k(G) (G) (G)五、有向圖的連通性：(1) 如果有向圖 D = 中所有有向邊的方向去掉后所得圖為無向連通圖，則說D為弱連通圖。(2) u,vV，如果存在u到v的一條通路，則說u可達(dá)v。(3) 弱連通圖中， 任何一對頂點(diǎn)之間，至少有一頂點(diǎn)可達(dá)另一個頂點(diǎn)，那么 是單向連通的；任何兩個頂點(diǎn)之間互相可達(dá)，稱強(qiáng)連通。有向連通圖的性質(zhì)：(1) 強(qiáng)連通一定單向連通，單向連通一定弱連通。反過來都不成立。(2) 有向圖D強(qiáng)連通，當(dāng)且僅當(dāng)D中存在一條回路，它至少經(jīng)過每個頂點(diǎn)一次。(充分性) 如果D中存在回路C，它經(jīng)過D中的每個頂點(diǎn)至少一次，則D中的任

19、意兩個頂點(diǎn)都在回路中，所以，D中任意兩個頂點(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)過每個頂點(diǎn)一次。(必要性) D是強(qiáng)連通的，則D中任何兩個頂點(diǎn)都是可達(dá)的。則得一回路。顯然每個頂點(diǎn)在回路中至少出現(xiàn)一次。證明：證明：所以vi到vi+1存在通路，不妨設(shè)D中的頂點(diǎn)為v1,v2,vn，且vn到v1也存在通路，鄰接矩陣：設(shè)G = 是一個簡單圖，它有n個頂點(diǎn)，V = v1,v2,vn，令aij = 1 E (或 (vi, vj)E)0 E (或 (vi, vj)E)稱A(G) = (

20、aij) 為G的鄰接矩陣。一、鄰接矩陣及其性質(zhì)鄰接矩陣的特性：在無向圖中：鄰接矩陣的特性：在無向圖中：(1) 鄰接陣是對稱陣；(2) 同一行或者同一列的元素和為對應(yīng)頂點(diǎn)的度數(shù)；或即)()(jn1iijin1jijvdavda(3) 矩陣中所有元素的和為邊數(shù)的2倍)(2n1jn1iij握手定理即ma 在有向圖中：(1) 同一行的元素和為對應(yīng)頂點(diǎn)的出度(2) 同一列的元素和為對應(yīng)頂點(diǎn)的入度)(in1jijvda即)(jn1iijvda即(3) aij = 2 m (邊的數(shù)目) 鄰接矩陣可推廣到多重圖或帶權(quán)圖，這時令aij為vi到vj的邊的重數(shù)或邊上的權(quán)值W(vi, vj)。鄰接陣多用于有向圖。關(guān)聯(lián)

21、矩陣：(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ì)：無向圖的關(guān)聯(lián)矩陣的性質(zhì)：)(, 2 , 1(2) 1 (n1iij每條邊關(guān)聯(lián)兩個頂點(diǎn)mjm)()2(iim1jij的度數(shù)vvdm n1iiij)(2)3(vdmm是孤立點(diǎn)

22、當(dāng)且僅當(dāng)m1jiij0)4(vm為平行邊與列相同，說明列與第若第kj)5(eekj(握手定理)有向圖的關(guān)聯(lián)矩陣的性質(zhì)：有向圖的關(guān)聯(lián)矩陣的性質(zhì)：0, 2 , 10) 1 (ijn1iijmmjm，從而，)() 1()2(im1jijvdmmvdmn1iin1im1jij)() 1(從而有)() 1(im1jijvdmmvdmn1iin1im1jij)() 1(由mij的定義知通路數(shù)與回路數(shù)的矩陣算法：(1) 設(shè)A是有向圖D的鄰接矩陣，V = v1,v2,vn， Al (l1)中元素aij(l)為vi到vj長度為l的通路數(shù)的中長度為為lDn1in1j(l)ija通路總數(shù)通路總數(shù)的中長度為為lDn1

23、i)(iila回路數(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ù)，的通路總數(shù)中長度小于為rDbji,(r)ij的回路總數(shù)中長度小于為rDbn1i(r)ii2. 求可達(dá)矩陣可達(dá)矩陣：設(shè)D = 為一有向圖，V = v1,v2,vn，令pij = 10i jpii = 1 i = 1,2,n 稱(pij)nxn 為D的可達(dá)矩陣。vi 可達(dá) vj否則例. 求下圖的可達(dá)矩陣，判斷它是否為強(qiáng)連通圖？V1V4V2V3V5解：1. 寫出鄰接矩陣010110

24、0001110100010000010A2. 計(jì)算 A2, A3, A4, A5.11120001001113101112110103A00111000100111211010001002A23253011123436312332111315A12222110101233211131011124A3. 計(jì)算 B = A +A2 + A3 + A4 + A5 , 并求出1111111111111111111111111P可達(dá)矩陣的求法：由鄰接矩陣A計(jì)算A2,A+A2, A+A2+A(n1) = B = (bij(n1)nn pij = 1 bij(n1) 00 bij(n1) = 0那么 i j

25、pii = 1即得可達(dá)矩陣 P(D) = (pij)nxn 帶權(quán)圖：對于有向圖或無向圖的每條邊附加一個實(shí)數(shù)w(e)，則得帶權(quán)圖。如果G1是帶權(quán)圖G的子圖，稱)()(1)E(Ge11GwGew，記作：的權(quán)為w(e) 為邊e上的權(quán)(當(dāng)e = 時，權(quán)記作wij)，記作：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)

26、*為頂點(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已獲得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 不相鄰修改通過集和未通

27、過集：Pr = Pr1vi， Tr = Tr1vi，step1. 求下一個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. 修改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)求下圖中頂點(diǎn)v0與與v5之間的最短路徑之間的最短路徑v0v2v1v4v3v5121475326解：利用標(biāo)號法算法解此題解：利用標(biāo)號法算法解此題開場，r0，

28、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，計(jì)算，計(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)*

29、+ w13 = min,8 = 8l4(1) = minl4(0), l1(1)* + w14 = 6l5(1) = minl5(0), l1(1)* + w15 = min)0(0jvlTjvi獲 p標(biāo)號l1(1)*，修改通過集與未通過集:修改通過集與未通過集 P2 = v0, v1, v2，T2 = v3 ,v4,v5修改未通過集的t標(biāo)號：l3(2) = 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

30、+ = ，計(jì)算第二步23min2 ) 1 (2(1)jTv1jillr3 )*2(22lpv標(biāo)號獲修改通過集與未通過集 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，所以，計(jì)算第三步44min3 )2(4(2)jTv2jillr4)*3(44lpv標(biāo)號獲修改通過集與未通過集 P4 = v0, v1, v2 ,v4 ,v3,T4 = v5修改未通過集的t標(biāo)號：l5(4) = minl5(3), l3(4)* + w35 = min10,