離散數(shù)學(xué)圖的基本概論第1頁，共78頁，2023年，2月20日，星期一計(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)用。第2頁，共78頁，2023年，2月20日，星期一8.1無向圖及有向圖稱{{a,b}|aAbB}為A與B的無序積，記作：A&B。習(xí)慣上，無序?qū)a,b}改記成(a,b)有序組(a,b)均用<a,b>無序積：設(shè)A，B為二集合，一、基本圖類及相關(guān)概念1.無向圖第3頁，共78頁，2023年，2月20日，星期一無向圖：無向圖G是一個(gè)二元組<V,E>，其中(1)V是一個(gè)非空集–––頂點(diǎn)集V(G)，每個(gè)元素為頂點(diǎn)或結(jié)點(diǎn)；(2)E是無序積V&V的可重子集(元素可重復(fù)出現(xiàn))，E–––邊集E(G)，E中元素稱為無向邊。第4頁，共78頁，2023年，2月20日，星期一v4實(shí)際中，圖是畫出來的，畫法：用小圓圈表示V中的每一個(gè)元素，如果(a,b)E，則在頂點(diǎn)a與b之間連線段。如：adcbe1e1e2e3e4e5e6e1e2e3e4e5e6v1v2v3v5第5頁，共78頁，2023年，2月20日，星期一有向圖：有向圖D是一個(gè)二元組<V,E>，其中(1)V是非空集–––頂點(diǎn)集V(D)(2)E是笛卡爾積VV的可重子集，其元素為有向邊實(shí)際中，畫法同無向圖，只是要根據(jù)E中元素的次序，由第一元素用方向線段指向第二元素。2.有向圖第6頁，共78頁，2023年，2月20日，星期一有限圖：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)概念第7頁，共78頁，2023年，2月20日，星期一頂與頂相鄰：如果ek=(vi,vj)E，稱vi與vj相鄰；環(huán)：ek=<vi,vj>中，若vi=vj，則ek稱為環(huán)。邊與邊相鄰：如果ek和ei至少有一個(gè)公共頂點(diǎn)關(guān)聯(lián)，則稱ek與ei相鄰。若ek為有向邊，則稱vi鄰接到vj,vj鄰接于vi

。第8頁，共78頁，2023年，2月20日，星期一孤立點(diǎn)：無邊關(guān)聯(lián)的頂點(diǎn)。平行邊：無向圖中，關(guān)聯(lián)一對(duì)結(jié)點(diǎn)的無向邊多于一條，平行邊的條數(shù)為重?cái)?shù)；多重圖：包含平行邊的圖。有向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的無向邊多于一條，且始、終點(diǎn)相同。簡單圖：既不包含平行邊又不包含環(huán)的圖。第9頁，共78頁，2023年，2月20日，星期一度：(1)在無向圖G=<V,E>中，與頂點(diǎn)v(vV)關(guān)聯(lián)的邊的數(shù)目(每個(gè)環(huán)計(jì)算兩次)，記作：d(v)。二、度第10頁，共78頁，2023年，2月20日，星期一(2)在有向圖D=<V,E>中，以頂點(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)。第11頁，共78頁，2023年，2月20日，星期一最大度：

(G)=max{d(v)|vV}最小度：(G)=min{d(v)|vV}度與邊數(shù)的關(guān)系：在任何圖中，頂點(diǎn)度數(shù)的總和等于邊數(shù)之和的兩倍。握手定理的推論：任何圖中，度為奇數(shù)的頂點(diǎn)個(gè)數(shù)一定為偶數(shù)。(握手定理)第12頁，共78頁，2023年，2月20日，星期一出度與入度的關(guān)系：在有向圖中，各頂點(diǎn)的出度之和等于各頂點(diǎn)的入度之和。度數(shù)序列：設(shè)V={v1,v2,…,vn}為圖G的頂點(diǎn)集，稱(d(v1),d(v2),…,d(vn))為G的度數(shù)序列。度數(shù)序列之和必為偶數(shù)(?)。第13頁，共78頁，2023年，2月20日，星期一例8.1(3,3,2,3)，(5,2,3,1,4)能成為圖的度數(shù)序列嗎？為什么？解：由于這兩個(gè)序列中，奇數(shù)個(gè)數(shù)均為奇數(shù)，由握手定理知，它們不能成為圖的度數(shù)序列。第14頁，共78頁，2023年，2月20日，星期一例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)。第15頁，共78頁，2023年，2月20日，星期一正則圖：各頂點(diǎn)的度都相同的圖為正則圖；各頂點(diǎn)的度均為k的圖為k次正則圖。完全圖：(1)設(shè)G=<V,E>是n階的無向簡單圖，如果G中任何一個(gè)頂點(diǎn)都與其余n–1個(gè)頂點(diǎn)相鄰，則G為無向完全圖，記作：Kn。三、正則圖與完全圖第16頁，共78頁，2023年，2月20日，星期一(2)設(shè)D=<V,E>是n階的有向簡單圖，如果D中任意頂點(diǎn)u，vV(uv)，即有有向邊<u,v>，又有有向邊<v,u>，則稱D為n階有向完全圖。如：第17頁，共78頁，2023年，2月20日，星期一四、子圖與母圖：(1)G=<V,E>，G'=<V',E'>若V'V，E'E，則G是G'的母圖，

G'是G的子圖，記作：G'

G。(2)若G'G且

V'=V，則G'是G的生成子圖。第18頁，共78頁，2023年，2月20日，星期一(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)出的導(dǎo)出子圖。第19頁，共78頁，2023年，2月20日，星期一例8.3

列舉下圖的一些子圖、真子圖、生成子圖、導(dǎo)出子圖。e3e1e2e4e5v3v4v1v2解：自己對(duì)照定義做一做！(1)子圖：子圖的定義？舉例(2)真子圖：舉例(3)生成子圖：定義？舉例(4)導(dǎo)出子圖：定義？舉例第20頁，共78頁，2023年，2月20日，星期一補(bǔ)圖：給定一個(gè)圖G=<V,E>，以V為頂點(diǎn)集，以所有能使G成為完全圖的添加邊組成邊集的圖。記作：～G五、補(bǔ)圖如:(1)(2)第21頁，共78頁，2023年，2月20日，星期一相對(duì)補(bǔ)圖：設(shè)G'G,如果另一個(gè)圖G''=<V'',E''>，滿足(1)E''=E–E'(2)V''中僅包含E''中的邊所關(guān)聯(lián)的結(jié)點(diǎn)。則G''是子圖G'相對(duì)于G的補(bǔ)圖。如：圖為的子圖，則圖(1)(2)(3)為(1)相對(duì)于(2)的補(bǔ)圖。第22頁，共78頁，2023年，2月20日，星期一圖同構(gòu)：對(duì)于G=<V,E>，G'=<V',E'>，如果存在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)之間一一對(duì)應(yīng)，邊之間一一對(duì)應(yīng)，關(guān)聯(lián)關(guān)系對(duì)應(yīng)相同，所以可以看成同一個(gè)圖。六、同構(gòu)圖第23頁，共78頁，2023年，2月20日，星期一例8.4

畫出4個(gè)頂點(diǎn)3條邊的所有可能非同構(gòu)的無向簡單圖。解：直觀上容易看出，下面三個(gè)圖是4個(gè)頂點(diǎn)3條邊的所有非同構(gòu)的無向簡單圖。第24頁，共78頁，2023年，2月20日，星期一例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條邊的無向簡單圖。第25頁，共78頁，2023年，2月20日，星期一

8.2通路、回路、圖的連通性通路與回路：給定圖G=<V,E>，設(shè)G中頂點(diǎn)與邊的交替序列

=v0

e1

v1

e2…el

vl

滿足：vi–1vi是ei的端點(diǎn)，(G為有向圖時(shí),要求vi–1,vi分別為ei的始點(diǎn)、終點(diǎn))，i=1,2,…,l，則為頂點(diǎn)v0到vl的通路。中邊的數(shù)目l稱為的長度。v0=vl時(shí)，稱為回路。一、通路與回路的概念第26頁，共78頁，2023年，2月20日，星期一簡單通路：

=v0

e1

v1

e2…ek

vk為通路且邊e1

e2…ek互不相同，又稱之為跡，可簡用v0

v1…vk來表示。簡單回路(v0=vk)又稱為閉跡。初級(jí)通路或基本通路：

=v0

e1

v1

e2…ek

vk為通路且頂點(diǎn)v0

v1…vk互不相同。初級(jí)通路一定是簡單通路，但簡單通路不一定是一條初級(jí)通路。基本回路：v0

=vk。第27頁，共78頁，2023年，2月20日，星期一例8.6

就下面兩圖列舉長度為5的通路，簡單通路，回路，簡單回路，再列舉長度為3的基本通路和回路。v1e1e4v2v3v4v5e3e5e2e7e6(1)(2)v5v1e2e5v2v3v4e1e7e3e8e6e4解：試對(duì)照定義，自己做一做！如：第28頁，共78頁，2023年，2月20日，星期一v1(1)中v1e1v2e2v5e3v1e1v2e4v3為v1到v3的通路；v1e1v2e4v3e5v4e7v5e3v1為v1到v1的一條簡單回路；v1e1v2e4v3e5v4e6v2e2v5為v1到v5的一條簡單通路。e1e4v2v3v4v5e3e5e2e7e6(1)第29頁，共78頁，2023年，2月20日，星期一(2)中v1e2v2e5v3e7v4v1到v4的長度為了的基本通路；v1e2v2e3v5e1v1是v1到v1的長度為了的基本回路。(2)v5v1e2e5v2v3v4e1e7e3e8e6e4第30頁，共78頁，2023年，2月20日，星期一二、通路與回路的性質(zhì)：(1)在一個(gè)n階圖中，如果從頂點(diǎn)vi到vj(vivj)存在通路，則從vi到vj存在長度小于或等于n–1的通路。如果L>n–1，則此通路的頂點(diǎn)數(shù)L+1>n，從而必有頂點(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ù)下去，必可得到一條從vi到vj的不多于n–1條邊的通路。通路的長度至少少1。第31頁，共78頁，2023年，2月20日，星期一(2)在n階圖中，如果從vi到vj(vivj)存在通路，則必存在從vi到vj的長度小于等于

n–1的基本通路。(3)在n階圖中，如果存在從vi到自身的回路，則從vi到自身存在長度等于n的回路。(4)在n階圖中，如果從vi到自身存在一條簡單回路，則從vi到自身存在長度等于n的初級(jí)回路。第32頁，共78頁，2023年，2月20日，星期一兩頂點(diǎn)連通：u,v為無向圖G的兩個(gè)頂點(diǎn)，u到v存在一條通路。連通圖：G中任何兩個(gè)頂點(diǎn)是連通的；否則是分離圖。三、圖的連通性第33頁，共78頁，2023年，2月20日，星期一連通性的性質(zhì)：無向圖中頂點(diǎn)之間的連通關(guān)系是頂點(diǎn)集V上的等價(jià)關(guān)系。(1)自反性：由于規(guī)定任何頂點(diǎn)到自身總是連通的；證明：(2)對(duì)稱性：無向圖中頂點(diǎn)之間的連通是相互的；(3)傳遞性：由連通性的定義可知。第34頁，共78頁，2023年，2月20日，星期一連通分支：無向圖G中每個(gè)劃分塊稱為G的一個(gè)連通分支，p(G)表示連通分支的個(gè)數(shù)。p(G)=1為連通圖。第35頁，共78頁，2023年，2月20日，星期一點(diǎn)割集：無向圖G=<V,E>為連通圖，如果V'V，且在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)。四、連通圖的連通度第36頁，共78頁，2023年，2月20日，星期一點(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)=n–1。存在割點(diǎn)的連通圖連通度為1，分離圖的連通度為0；第37頁，共78頁，2023年，2月20日，星期一邊割集：設(shè)無向圖G=<V,E>連通，邊集E'E，在G中刪除E'中所有邊后所得子圖不連通，而刪除E'中的任何子集中的邊后，所得子圖仍連通，則E'為G的邊割集。如果邊割集中只有一邊時(shí)，該邊為割邊(或橋)第38頁，共78頁，2023年，2月20日，星期一邊連通度：設(shè)G為無向連通圖，記(G)=min{|E'|E'是G的邊割集}，(G)為G的邊連通度。連通度的性質(zhì)：k(G)(G)(G)第39頁，共78頁，2023年，2月20日，星期一五、有向圖的連通性：(1)如果有向圖D=<V,E>中所有有向邊的方向去掉后所得圖為無向連通圖，則說D為弱連通圖。(2)u,vV，如果存在u到v的一條通路，則說u可達(dá)v。(3)弱連通圖<V,E>中，任何一對(duì)頂點(diǎn)之間，至少有一頂點(diǎn)可達(dá)另一個(gè)頂點(diǎn)，則<V,E>是單向連通的；任何兩個(gè)頂點(diǎn)之間互相可達(dá)，稱<V,E>強(qiáng)連通。第40頁，共78頁，2023年，2月20日，星期一有向連通圖的性質(zhì)：(1)強(qiáng)連通一定單向連通，單向連通一定弱連通。反過來都不成立。第41頁，共78頁，2023年，2月20日，星期一(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)連通的。證明：第42頁，共78頁，2023年，2月20日，星期一因?yàn)関i可達(dá)vi+1,i=1,2,…，n–1，讓這些通路首尾相連，(2)有向圖D強(qiáng)連通，當(dāng)且僅當(dāng)D中存在一條回路，它至少經(jīng)過每個(gè)頂點(diǎn)一次。(必要性)D是強(qiáng)連通的，則D中任何兩個(gè)頂點(diǎn)都是可達(dá)的。則得一回路。顯然每個(gè)頂點(diǎn)在回路中至少出現(xiàn)一次。證明：所以vi到vi+1存在通路，不妨設(shè)D中的頂點(diǎn)為v1,v2,…,vn，且vn到v1也存在通路，第43頁，共78頁，2023年，2月20日，星期一8.3圖的矩陣表示鄰接矩陣：設(shè)G=<V,E>是一個(gè)簡單圖，它有n個(gè)頂點(diǎn)，V={v1,v2,…,vn}，令aij=1<vi,vj>E(或(vi,vj)E)0<vi,vj>E(或(vi,vj)E)稱A(G)=(aij)為G的鄰接矩陣。一、鄰接矩陣及其性質(zhì)第44頁，共78頁，2023年，2月20日，星期一鄰接矩陣的特性：在無向圖中：(1)鄰接陣是對(duì)稱陣；(2)同一行或者同一列的元素和為對(duì)應(yīng)頂點(diǎn)的度數(shù)(3)矩陣中所有元素的和為邊數(shù)的2倍第45頁，共78頁，2023年，2月20日，星期一在有向圖中：(1)同一行的元素和為對(duì)應(yīng)頂點(diǎn)的出度(2)同一列的元素和為對(duì)應(yīng)頂點(diǎn)的入度(3)aij=2m(邊的數(shù)目)第46頁，共78頁，2023年，2月20日，星期一鄰接矩陣可推廣到多重圖或帶權(quán)圖，這時(shí)令aij為vi到vj的邊的重?cái)?shù)或邊上的權(quán)值W(vi,vj)。鄰接陣多用于有向圖。第47頁，共78頁，2023年，2月20日，星期一關(guān)聯(lián)矩陣：(1)設(shè)G=<V,E>為(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ì)第48頁，共78頁，2023年，2月20日，星期一(2)設(shè)D=<V,E>是有向圖且無環(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)第49頁，共78頁，2023年，2月20日，星期一無向圖的關(guān)聯(lián)矩陣的性質(zhì)：(握手定理)第50頁，共78頁，2023年，2月20日，星期一有向圖的關(guān)聯(lián)矩陣的性質(zhì)：由mij的定義知第51頁，共78頁，2023年，2月20日，星期一通路數(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ù)第52頁，共78頁，2023年，2月20日，星期一(2)設(shè)A是有向圖D的鄰接矩陣，B1=A，B2=A+A2,……，Br=A+A2+…+Ar，則Br中元素bij(r)

為D中vi到vj長度小于等于r的通路數(shù)，2.求可達(dá)矩陣第53頁，共78頁，2023年，2月20日，星期一可達(dá)矩陣：設(shè)D=<V,E>為一有向圖，V={v1,v2,…,vn}，令pij=10ijpii=1i=1,2,…,n

稱(pij)nxn

為D的可達(dá)矩陣。vi

可達(dá)vj否則第54頁，共78頁，2023年，2月20日，星期一例.求下圖的可達(dá)矩陣，判斷它是否為強(qiáng)連通圖？V1V4V2V3V5解：1.寫出鄰接矩陣第55頁，共78頁，2023年，2月20日，星期一2.計(jì)算A2,A3,A4,A5.第56頁，共78頁，2023年，2月20日，星期一3.計(jì)算B=A+A2+A3+A4+A5,并求出第57頁，共78頁，2023年，2月20日，星期一可達(dá)矩陣的求法：由鄰接矩陣A計(jì)算A2,A+A2,……A+A2+…+A(n–1)=B=(bij(n–1))nn

pij=1bij(n–1)

00bij(n–1)

=0則i

jpii=1即得可達(dá)矩陣P(D)=(pij)nxn

第58頁，共78頁，2023年，2月20日，星期一8.4最短路徑問題帶權(quán)圖：對(duì)于有向圖或無向圖的每條邊附加一個(gè)實(shí)數(shù)w(e)，則得帶權(quán)圖。如果G1是帶權(quán)圖G的子圖，稱w(e)為邊e上的權(quán)(當(dāng)e=<vi,vj>時(shí)，權(quán)記作wij)，記作：G=<V,E,W>一、帶權(quán)圖及其最短路徑問題第59頁，共78頁，2023年，2月20日，星期一G=<V,E,W>為帶權(quán)圖，且G中各邊帶的權(quán)均大于等于0，從頂點(diǎn)u到頂點(diǎn)v的所有通路中求帶權(quán)最小的通路問題，稱為最短路徑問題。最短路徑問題：如果v1v2…vn–1vn是v1到vn的最短路徑，則v1v2…vn–1也必然是v1從到vn–1的最短路徑。求最短路徑的標(biāo)號(hào)法的基本思想：第60頁，共78頁，2023年，2月20日，星期一標(biāo)號(hào)法：(1)符號(hào)說明(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)號(hào)lj(r)(r0)如果頂點(diǎn)vi獲得了標(biāo)號(hào)li(r)*，稱vi在第r步獲得p標(biāo)號(hào)li(r)*(iii)Pr={v|v已獲得p標(biāo)號(hào)}，稱之為第r步通過集(r0)(iv)Tr=V–Pr

稱之為第r步未通過集(r0)二、求最短路徑問題的標(biāo)號(hào)法第61頁，共78頁，2023年，2月20日，星期一(2)算法：開始，r0，v1獲p標(biāo)號(hào)：l1(0)*=0，P0={v1}，T0=V–{v1}，vj(j1)的t標(biāo)號(hào)：lj(0)=w1j=w1j

0v1與vj相鄰v1與vj不相鄰第62頁，共78頁，2023年，2月20日，星期一修改通過集和未通過集：Pr=Pr–1∪{vi}，

Tr=Tr–1∪{vi}，step1.求下一個(gè)p標(biāo)號(hào)頂點(diǎn)設(shè)lj(r)*=min{lj(r–1)}，r1。vjTr–1頂點(diǎn)vi處，表明vi獲得p標(biāo)號(hào)。查Tr：若Tr=，則算法結(jié)束，否則轉(zhuǎn)step2將lj(r)*標(biāo)在相應(yīng)第63頁，共78頁，2023年，2月20日，星期一step2.修改Tr中各頂點(diǎn)的t標(biāo)號(hào)lj(r)=min{lj(r–1),li(r)*+wij}，li(r)*是剛剛獲得p標(biāo)號(hào)頂點(diǎn)的p標(biāo)號(hào)。令r

r+1，轉(zhuǎn)step1。第64頁，共78頁，2023年，2月20日，星期一例8.7

求下圖中頂點(diǎn)v0與v5之間的最短路徑v0v2v1v4v3v5121475326第65頁，共78頁，2023年，2月20日，星期一解：利用標(biāo)號(hào)法算法解此題開始，r0，v0獲p標(biāo)號(hà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)號(hào)：v0v2v1v4v3v5121475326第66頁，共78頁，2023年，2月20日，星期一第一步：r=1，計(jì)算=l1(1)*=1，所以i=1，P1={v0,v1}，T1={v2,v3,v4,v5}修改未通過集的t標(biāo)號(hào)：l2(1)=min{l2(0),l1(1)*+w12}=min{4,3}=3l3(1)=min{l3(0),l1(1)*+w13}=min{,8}=8l4(1)=min{l4(0),l1(1)*+w14}=6l5(1)=min{l5(0),l1(1)*+w15}=vi獲p標(biāo)號(hào)l1(1)*，修改通過集與未通過集:第67頁，共78頁，2023年，2月20日，星期一修改通過集與未通過集

P2={v0,v1,

v2}，T2={v3,v4,v5}修改未通過集的t標(biāo)號(hào)：l3(2)=min{l3(1),l2(2)*+w23}=min{8,3+}=8l4(2)=min{l4(1),l2(2)*+w24}=min{6,3+1}=4l5(2)=min{l5(0),l2(2)*+w25}=min{,3+}=第68頁，共78頁，2023年，2月20日，星期一修改通過集與未通過集

P3={v0,v1,

v2,v4},T3={v5,v3}修改未通過集的t標(biāo)號(hào)：l3(3)=min{l3(2),l4(3)*+w43}=min{8,4+3}=7l5(3)=min{l5(2),l4(3)*+w45}=min{,4+6