圖論最短路算法圖的代數(shù)表示

圖論課件最短路算法圖的代數(shù)表示1第1頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月第一章圖的基本概念本次課主要內(nèi)容最短路算法、圖的代數(shù)表示(一)、最短路算法(二)、圖的代數(shù)表示1、圖的鄰接矩陣2、圖的關(guān)聯(lián)矩陣2第2頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月1、相關(guān)概念(1)賦權(quán)圖(一)、最短路算法在圖G的每條邊上標(biāo)上一個(gè)實(shí)數(shù)w(e)后,稱G為邊賦權(quán)圖。被標(biāo)上的實(shí)數(shù)稱為邊的權(quán)值。若H是賦權(quán)圖G的一個(gè)子圖，稱為子圖H的權(quán)值。權(quán)值的意義是廣泛的。可以表示距離，可以表示交通運(yùn)費(fèi)，可以表示網(wǎng)絡(luò)流量，在朋友關(guān)系圖甚至可以表示友誼深度。但都可以抽象為距離。3第3頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月(2)賦權(quán)圖中的最短路設(shè)G為邊賦權(quán)圖。u與v是G中兩點(diǎn)，在連接u與v的所有路中，路中各邊權(quán)值之和最小的路，稱為u與v間的最短路。解決某類問題的一組有窮規(guī)則，稱為算法。(3)算法1)好算法算法總運(yùn)算量是問題規(guī)模的多項(xiàng)式函數(shù)時(shí)，稱該算法為好算法。(問題規(guī)模：描述或表示問題需要的信息量)算法中的運(yùn)算包括算術(shù)運(yùn)算、比較運(yùn)算等。運(yùn)算量用運(yùn)算次數(shù)表示。2)算法分析4第4頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月對(duì)算法進(jìn)行分析，主要對(duì)時(shí)間復(fù)雜性進(jìn)行分析。分析運(yùn)算量和問題規(guī)模之間的關(guān)系。2)算法分析2、最短路算法

1959年，但切西(Dantjig）發(fā)現(xiàn)了在賦權(quán)圖中求由點(diǎn)a到點(diǎn)b的最短路好算法，稱為頂點(diǎn)標(biāo)號(hào)法。

t(an):點(diǎn)an的標(biāo)號(hào)值，表示點(diǎn)a1=a到an的最短路長(zhǎng)度

Ai={a1,a2,...,ai}:已經(jīng)標(biāo)號(hào)的頂點(diǎn)集合。

Ti:a1到ai的最短路上的邊集合算法敘述如下：5第5頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月(1)記a=a1,t(a1)=0,A1={a1},T1=?;(2)若已經(jīng)得到Ai={a1,a2,…,ai},且對(duì)于1≤n≤i,已知t(an),對(duì)每一個(gè)an∈Ai,求一點(diǎn)：使得：(3)設(shè)有mi

，1≤mi≤i,而bmi(i)是使取最小值，令：(4)若ai+1=b,停止，否則，記,轉(zhuǎn)(2).6第6頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月該算法的通俗說法為：(1)找出已標(biāo)號(hào)頂點(diǎn)的未標(biāo)號(hào)最近鄰點(diǎn)：bn(i)(2)把已標(biāo)號(hào)頂點(diǎn)標(biāo)號(hào)值與它到最近鄰點(diǎn)的距離相加，和值最小者對(duì)應(yīng)的最近鄰點(diǎn)作為標(biāo)號(hào)點(diǎn)，標(biāo)號(hào)值為該和值。7第7頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月時(shí)間復(fù)雜性分析：對(duì)第i次循環(huán)：步驟(2)要進(jìn)行i次比較運(yùn)算，步驟(3)要進(jìn)行i次加法與i次比較運(yùn)算。所以，該次循環(huán)運(yùn)算量為3i.所以，在最壞的情況下，運(yùn)算量為n2級(jí)，是好算法。算法證明：定理1：算法中的函數(shù)t(ai)給出了a與ai的距離。證明：對(duì)i作數(shù)學(xué)歸納法。(1)i=1時(shí)結(jié)論顯然成立。(2)設(shè)對(duì)所有的j，1≤j<i時(shí)，t(aj)=d(a,aj).(3)考慮j=i令P=v0v1…vd,v0=a,vd=ai是連接a與ai的一條最短路，8第8頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月于是d(P)

=d(a,ai),令vn是P中第一個(gè)不在Ai-1中的點(diǎn)。由于

,故這樣的點(diǎn)vn存在。又因v0∈Ai-1知n≥1,設(shè)vn-1=ak,則有k≤i-1.記P中由a到vn的一段的長(zhǎng)度為l，a到vn-1的一段長(zhǎng)度為l1.由歸納假設(shè)，有l(wèi)1≥t(ak),且其中ami-1由算法的第(3)步得到，1≤mi-1≤i-1.又由于存在一條長(zhǎng)度為t(ai)聯(lián)結(jié)的a與ai的路，可知9第9頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月聯(lián)合此兩個(gè)不等式，即得：由歸納法知定理成立。例1如圖所示，求點(diǎn)a到點(diǎn)b的距離。812614227924693av1v2v3v4v5v6b解1.A1={a}，t(a)=0，T1=Φ2.b1(1)=v3;3.m1=1,a2=v3,t(v3)=t(a)+l(av3)=1(最小)，T2={av3};10第10頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月2.A2={a,v3},b1(2)=v1,b2

(2)=v2;3.m2=1,a3=v1,t(v1)=t(a)+l(av1)=2(最小)，T3={av3,av1};2.A3={a,v3,v1},b1

(3)=v2,b2

(3)=v2,b3

(3)=v4;

3.m3=3,a4=v4,t(v4)=t(v1)+l(v1v4)=3(最小)，T4={av3,av1,v1v4}2.A4={a,v3,v1,v4}，b1(4)=v2，b2(4)=v2，b3(4)=v2,

b4(4)=v5;3.m4=4,a5=v5,t(v5)=t(v4)+l(v4v5)=6(最小)，T5={av3,av1,v1v4,v4v5};11第11頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月2.A5={a,v3,v1,v4,v5}，b1(5)=v2，b2(5)=v2，

b3(5)=v2

,b4(5)=v2,b5(5)=v2;3.m5=4,t(v2)=t(v4)+l(v4v2)=7(最小)，T6={av3,av1,v1v4,v4v5,v4v2};2.A6={a,v3,v1,v4,v5,v2},b2(6)=v6,b4(6)=b，

b5(6)=v6，b6(6)=v6;3.m6=6,a7=v6,t(v6)=t(v2)+l(v2v6)=9(最小)，T7={av3,av1,v1v4,v4v5,v4v2,v2v6};2.A7={a,v3,v1,v4,v5,v2,v6},b4(7)=b，b5(7)=b，

b7(7)=b;3.m7=7,a8=b,t(b)=t(v6)+l(v6b)=11(最小)，12第12頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月T8={av3,av1,v1v4,v4v5,v4v2,v2v6,v6b};于是知a與b的距離

d(a,b)=t(b)=11由T8導(dǎo)出的a到b的最短路為：課外作業(yè)某公司在六個(gè)城市C1,C2,C3,C4,C5,C6中有分公司，從Ci到Cj的直接航程票價(jià)記在下述矩陣的(i,j)位置上，∞表示沒有直接航程。13第13頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月例2某兩人有一只8升的酒壺裝滿了酒，還有兩只空壺，分別為5升和3升。求最少的操作次數(shù)。解：設(shè)x1,x2,x3分別表示8,5,3升酒壺中的酒量。則容易算出(x1,x2,x3)的組合形式共24種。每種組合用一個(gè)點(diǎn)表示，兩點(diǎn)連線，當(dāng)且僅當(dāng)可通過倒酒的方式相互變換。若各邊賦權(quán)為1，則問題轉(zhuǎn)化為在該圖中求(8,0,0)到(4,4,0)的一條最短路。結(jié)果如下：14第14頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月例3在一河岸有狼，羊和卷心菜。擺渡人要將它們渡過河去，由于船太小，每次只能載一樣?xùn)|西。由于狼羊，羊卷心菜不能單獨(dú)相處。問擺渡人至少要多少次才能將其渡過河？分析：人，狼，羊，菜所有組合形式為：但是以下組合不能允許出現(xiàn)：狼羊菜，羊菜，狼羊，人，人狼，人菜，共6種。岸上只能允許出現(xiàn)10種組合：人狼羊菜，人狼羊，人狼菜，人羊，空，菜，羊，狼，狼菜，人羊菜。每種情況用點(diǎn)表示；15第15頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月兩點(diǎn)連線，當(dāng)且僅當(dāng)兩種情況可用載人(或加一物)的渡船相互轉(zhuǎn)變。于是，問題轉(zhuǎn)化為求由頂點(diǎn)“人狼羊菜”到頂點(diǎn)“空”的一條最短路。每條邊賦權(quán)為1結(jié)果為：人狼羊菜→狼菜→人狼菜→狼→人狼羊→羊→人羊→空；(2)人狼羊菜→狼菜→人狼菜→菜→人羊菜→羊→人羊→空。16第16頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月(二)、圖的代數(shù)表示用鄰接矩陣或關(guān)聯(lián)矩陣表示圖，稱為圖的代數(shù)表示。用矩陣表示圖，主要有兩個(gè)優(yōu)點(diǎn)：(1)能夠把圖輸入到計(jì)算機(jī)中；(2)可以用代數(shù)方法研究圖論。1、圖的鄰接矩陣定義1設(shè)G為n階圖，V={v1,v2,…,vn},鄰接矩陣A(G)=(aij),其中：17第17頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月例如：寫出下圖G的鄰接矩陣：解：鄰接矩陣為：1234圖G18第18頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月圖G的鄰接矩陣的性質(zhì)(1)非負(fù)性與對(duì)稱性由鄰接矩陣定義知aij是非負(fù)整數(shù)，即鄰接矩陣是非負(fù)整數(shù)矩陣；在圖中點(diǎn)vi與vj鄰接，有vj與vi鄰接，即aij=aji.所以，鄰接矩陣是對(duì)稱矩陣。(2)同一圖的不同形式的鄰接矩陣是相似矩陣。這是因?yàn)椋瑘D的兩種不同形式矩陣可以通過交換行和相應(yīng)的列變成一致。(3)如果G為簡(jiǎn)單圖，則A(G)為布爾矩陣;行和(列和)等于對(duì)應(yīng)頂點(diǎn)的度數(shù)；矩陣元素總和為圖的總度數(shù)，也就是G的邊數(shù)的2倍。19第19頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月(4)G連通的充分必要條件是：A(G)不能與如下矩陣相似證明：1)充分性若不然：設(shè)A11對(duì)應(yīng)的頂點(diǎn)是v1,v2,…,vk,A22對(duì)應(yīng)的頂點(diǎn)為vk+1,vk+2,…,vn顯然，vi(1≤i≤k)與vj(k+1≤i≤n)不鄰接，即G是非連通圖。矛盾！2)必要性若不然：設(shè)G1與G2是G的兩個(gè)不連通的部分，并且設(shè)V(G1)={v1,v2,…,vk},V(G2)={vk+1,vk+2,…,vn},如果在寫20第20頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月G的鄰接矩陣時(shí)，先排V(G1)中點(diǎn)，再排V(G2)中點(diǎn)，則G的鄰接矩陣形式必為：(5)定理：設(shè)，則aij(k)表示頂點(diǎn)vi到頂點(diǎn)vj的途徑長(zhǎng)度為k的途徑條數(shù)。證明：對(duì)k作數(shù)學(xué)歸納法證明。當(dāng)k=1時(shí)，由鄰接矩陣的定義，結(jié)論成立；設(shè)結(jié)論對(duì)k-1時(shí)成立。當(dāng)為k時(shí)：一方面：先計(jì)算Ak;21第21頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月另一方面：考慮vi到vj的長(zhǎng)度為k的途徑設(shè)vm是vi到vj的途徑中點(diǎn)，且該點(diǎn)和vj鄰接。則vi到vj的經(jīng)過vm且長(zhǎng)度為k的途徑數(shù)目應(yīng)該為：所以，vi到vj的長(zhǎng)度為k的途徑數(shù)目為：即為例4求下圖中v1到v3的途徑長(zhǎng)度為2和3的條數(shù)。22第22頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月解：由于：v4v1v2v3所以，v1到v3的途徑長(zhǎng)度為2和3的條數(shù)分別為：3和4。推論:(1)A2的元素aii(2)是vi的度數(shù)，A3的元素aii(3)是含vi的三角形個(gè)數(shù)的2倍；23第23頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月(2)若G是連通的，對(duì)于i≠j,vi和vj間距離是使An的aij(n)≠0的最小整數(shù)。2、圖的關(guān)聯(lián)矩陣(1)若G是(n,m)圖。定義G的關(guān)聯(lián)矩陣：其中：例如：e1v4v3v2v1e7e5e4e3e2e624第24頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月(2)關(guān)聯(lián)矩陣的性質(zhì)1)關(guān)聯(lián)矩陣的元素為0，1或2；