離散數學圖的基本概念

1、1第1頁，共48頁，2022年，5月20日，11點10分，星期五通路與回路 定義 給定圖G=（無向或有向的），設G中頂點與邊的交替序列=v0e1v1e2elvl： 若i(1il), vi1 和 vi是ei的端點(對于有向圖, 要求vi1是始點, vi是終點), 則稱為通路, v0是通路的起點, vl是通路的終點, l為通路的長度. 又若v0=vl，則稱為回路.理解：通路或回路是點與邊的交替序列，邊的端點恰好是前后的兩個點長度邊數2第2頁，共48頁，2022年，5月20日，11點10分，星期五若通路(回路)中所有頂點(對于回路, 除v0=vl)各異，則稱為初級通路(初級回路).初級通路又稱作路徑

2、, 初級回路又稱作圈.路上各點不重復若通路(回路)中所有邊各異, 則稱為簡單通路(簡單回路), 否則稱為復雜通路(復雜回路).路上各邊不重復3第3頁，共48頁，2022年，5月20日，11點10分，星期五通路與回路(續(xù))說明:在無向圖中，環(huán)是長度為1的圈, 兩條平行邊構成長度為2的圈.無向簡單圖中, 所有圈的長度3在有向圖中，環(huán)是長度為1的圈, 兩條方向相反邊構成長度為2的圈.在有向簡單圖中, 所有圈的長度2. 4第4頁，共48頁，2022年，5月20日，11點10分，星期五通路與回路(續(xù)) 定理 在n階圖G中，若從頂點vi到vj（vivj）存在通路，則從vi到vj存在長度小于等于n1的通路.

3、推論 在n階圖G中，若從頂點vi到vj（vivj）存在通路，則從vi到vj存在長度小于等于n1的初級通路.定理 在一個n階圖G中，若存在vi到自身的回路，則一定存在vi到自身長度小于等于n的回路.推論 在一個n階圖G中，若存在vi到自身的簡單回路，則一定存在長度小于等于n的初級回路. 5第5頁，共48頁，2022年，5月20日，11點10分，星期五無向圖的連通性 設無向圖G=,u與v連通: u與v之間有通路.規(guī)定u與自身總連通.連通關系：R=| u,v V且uv是V上的等價關系連通圖: 平凡圖, 或者任意兩點都連通的圖連通分支: V關于R的等價類的導出子圖設V/R=V1,V2,Vk, GV1,

4、 GV2, ,GVk是G的連通分支, 連通分支個數記作p(G)=k.G是連通圖 p(G)=16第6頁，共48頁，2022年，5月20日，11點10分，星期五短程線與距離u與v之間的短程線: u與v之間長度最短的通路u與v之間的距離d(u,v): u與v之間短程線的長度若u與v不連通, 規(guī)定d(u,v)=.性質： d(u,v)0, 且d(u,v)=0 u=v d(u,v)=d(v,u)（對稱性） d(u,v)+d(v,w)d(u,w) （三角不等式)7第7頁，共48頁，2022年，5月20日，11點10分，星期五點割集（v點；V點集；e邊；E變集） 記 Gv: 從G中刪除v及關聯(lián)的邊 GV: 從

5、G中刪除V中所有的頂點及關聯(lián)的邊Ge : 從G中刪除eGE: 從G中刪除E中所有邊定義 設無向圖G=, 如果存在頂點子集VV, 使p(GV)p(G)，而且刪除V的任何真子集V后（ VV），p(GV)=p(G), 則稱V為G的點割集. 若v為點割集, 則稱v為割點.理解：刪除點后連通分支數可能增加，會減少嗎？8第8頁，共48頁，2022年，5月20日，11點10分，星期五點割集(續(xù))例 v1,v4, v6是點割集, v6是割點. v2,v5是點割集嗎？ 9第9頁，共48頁，2022年，5月20日，11點10分，星期五邊割集定義 設無向圖G=, EE, 若p(GE)p(G)且EE, p(GE)=p

6、(G), 則稱E為G的邊割集. 若e為邊割集, 則稱e為割邊或橋.下圖中，e1,e2，e1,e3,e5,e6，e8等是邊割集，e8是橋，e7,e9,e5,e6是邊割集嗎？10第10頁，共48頁，2022年，5月20日，11點10分，星期五幾點說明：Kn無點割集（完全圖）n階零圖既無點割集，也無邊割集.若G連通，E為邊割集，則p(GE)=2若G連通，V為點割集，則p(GV)211第11頁，共48頁，2022年，5月20日，11點10分，星期五有向圖的連通性 設有向圖D=u可達v: u到v有通路. 規(guī)定u到自身總是可達的.可達具有自反性和傳遞性D弱連通(也稱連通): 基圖為無向連通圖有向邊改為無向

7、邊后是連通圖D單向連通: u,vV，u可達v 或v可達u D強連通: u,vV，u與v相互可達強連通單向連通弱連通 12第12頁，共48頁，2022年，5月20日，11點10分，星期五有向圖的連通性(續(xù)) (1)(2)(3)例 下圖(1)強連通, (2)單連通, (3) 弱連通每個頂點有進有出部分頂點有進有出13第13頁，共48頁，2022年，5月20日，11點10分，星期五有向圖的短程線與距離u到v的短程線: u到v長度最短的通路 (u可達v)u與v之間的距離d: u到v的短程線的長度若u不可達v, 規(guī)定d=.性質： d0, 且d=0 u=v d+d d 注意: 沒有對稱性14第14頁，共4

8、8頁，2022年，5月20日，11點10分，星期五7.3 圖的矩陣表示 無向圖的關聯(lián)矩陣有向圖的關聯(lián)矩陣有向圖的鄰接矩陣有向圖的可達矩陣 15第15頁，共48頁，2022年，5月20日，11點10分，星期五無向圖的關聯(lián)矩陣定義 設無向圖G=, V=v1, v2, , vn, E=e1, e2, , em, 令mij為vi與ej的關聯(lián)次數，稱(mij)nm為G的關聯(lián)矩陣，記為M(G). 性質16第16頁，共48頁，2022年，5月20日，11點10分，星期五v1v2v4v3e1e2e3e4e5關聯(lián)次數為可能取值為0，1，217第17頁，共48頁，2022年，5月20日，11點10分，星期五無向圖

9、的相鄰矩陣v1v2v4v3e1e2e3e4e5(1)相鄰矩陣是對稱矩陣。(2)對角元素aii0,表示結點vi處有環(huán)。(3)如aij 1,表示vi與vj間有平行邊。aij +2 18第18頁，共48頁，2022年，5月20日，11點10分，星期五V1V2V3V4V5 V1 V2 V3 V4 V519第19頁，共48頁，2022年，5月20日，11點10分，星期五有向圖的關聯(lián)矩陣定義 設無環(huán)有向圖D=, V=v1, v2, , vn, E=e1, e2, , em, 令 則稱(mij)nm為D的關聯(lián)矩陣，記為M(D).20第20頁，共48頁，2022年，5月20日，11點10分，星期五v4v1v2

10、v3e1e2e3e4e5性質: (4) 平行邊對應的列相同21第21頁，共48頁，2022年，5月20日，11點10分，星期五定義 設有向圖D=, V=v1, v2, , vn, E=e1, e2, , em, 令 為頂點vi鄰接到頂點vj邊的條數，稱( )nn為D的鄰接矩陣, 記作A(D), 簡記為A. 性質有向圖的鄰接矩陣 22第22頁，共48頁，2022年，5月20日，11點10分，星期五v2v1v4v323第23頁，共48頁，2022年，5月20日，11點10分，星期五D中的通路及回路數定理 設A為n階有向圖D的鄰接矩陣, 則Al(l1)中元素 為D中vi到vj長度為 l 的通路數，

11、為vi到自身長度為 l 的回路數， 為D中長度為 l 的通路總數， 為D中長度為 l 的回路總數. 24第24頁，共48頁，2022年，5月20日，11點10分，星期五D中的通路及回路數(續(xù))例 有向圖D如圖所示, 求A, A2, A3, A4, 并回答問題：(1) D中長度為1, 2, 3, 4的通路各有多 少條？其中回路分別為多少條？(2) D中長度小于或等于4的通路為多 少條？其中有多少條回路？ 推論 設Bl=A+A2+Al(l1), 則Bl中元素 為D中長度小于或等于l 的通路數， 為D中長度小于或等于l 的回路數.25第25頁，共48頁，2022年，5月20日，11點10分，星期五例

12、(續(xù)) 長度 通路 回路 合計 50 818 1211 3314 1417 326第26頁，共48頁，2022年，5月20日，11點10分，星期五有向圖的可達矩陣 定義 設D=為有向圖, V=v1, v2, , vn, 令 稱(pij)nn為D的可達矩陣, 記作P(D), 簡記為P. 性質: P(D)主對角線上的元素全為1. D強連通當且僅當P(D)的元素全為1.27第27頁，共48頁，2022年，5月20日，11點10分，星期五有向圖的可達矩陣(續(xù))例 右圖所示的有向圖D的可達矩陣為28第28頁，共48頁，2022年，5月20日，11點10分，星期五如何求有向圖的可達矩陣設D=為有向圖，|V

13、|=n, A為D的鄰接矩陣；先求R（rij）A+A2+.+An再求可達矩陣P（pij）29第29頁，共48頁，2022年，5月20日，11點10分，星期五7.4 最短路徑及關鍵路徑對于有向圖或無向圖G的每條邊，附加一個實數w(e)，則稱w(e)為邊e上的權.G連同附加在各邊上的實數，稱為帶權圖.設帶權圖G=,G中每條邊的權都大于等于0.u,v為G中任意兩個頂點，從u到v的所有通路中帶權最小的通路稱為u到v的最短路徑.求給定兩個頂點之間的最短路徑，稱為最短路徑問題.30第30頁，共48頁，2022年，5月20日，11點10分，星期五算法：Dijkstra(標號法)31第31頁，共48頁，2022

14、年，5月20日，11點10分，星期五v2v0v1v3v4v5141762253例：求圖中v0與v5的最短路徑32第32頁，共48頁，2022年，5月20日，11點10分，星期五 vikv0v1v2v3v4v50 0 141 138623 8437 4104 7959013749v0v1v2v4v333第33頁，共48頁，2022年，5月20日，11點10分，星期五2.關鍵路徑問題PERT圖 設D=是n階有向帶權圖D是簡單圖D中無環(huán)路有一個頂點出度為0，稱為發(fā)點；有一個頂點入度為0，稱為收點記邊的權為wij,它常常表示時間34第34頁，共48頁，2022年，5月20日，11點10分，星期五Per

15、t圖的應用用Pert中有向邊表示工序，邊上權表示完成工序的時間；用pert圖中結點vi表示某個事項，表示某些工序的完工，同時表示某些工序可以開工。習慣上所有的有向邊均從左向右。PertProgram Evaluation and Review Technic，計劃評審技術35第35頁，共48頁，2022年，5月20日，11點10分，星期五關鍵路徑從始點到終點的一條最長路徑（發(fā)點到收點的一條最長路徑 ）通過求各點的最早完成時間來求關鍵路徑最早完成時間：自發(fā)點v1開始，沿最長路徑（按權計算）到達vi所需時間，稱為vi的最早完成時間，記為TE（vi） ，i=1,2,n。TE(vi)表示在前面所有工序

16、均沒有耽誤的情況下，該事項最早可能完成的時間，此時前面的工序均必須完成。也是后續(xù)工程最早開始的時間。36第36頁，共48頁，2022年，5月20日，11點10分，星期五這樣從始點出發(fā)，TE(v0)0，一直計算到收點 vn，TE(vn)就是工程的最早完工時間。37第37頁，共48頁，2022年，5月20日，11點10分，星期五1234657824423326324026671315節(jié)點的最早完工時間38第38頁，共48頁，2022年，5月20日，11點10分，星期五2事項的最晚完成時間 TL(vi)：在保證收點vn的最早完成時間不增加的條件下，該事項vi最晚必須完成的時間，稱為該點vi最晚完成時

17、間，記為TL(vi)。因為有些工序不在關鍵路上,這些工序有個緩沖時間,稍遲一些時間動工，不會導致整個工程的完工時間，但這也有個限度，TL(vi)就是不耽誤整個工程的最早完工條件下，該工序最遲的開工時間，過了這時間開工將影響整個工程。39第39頁，共48頁，2022年，5月20日，11點10分，星期五其算法是從收點開始向后計算：因v0和vn均在關鍵路上,TE（vn）=TL（vn），TE（v0）=TL（v0）= 040第40頁，共48頁，2022年，5月20日，11點10分，星期五12346578244233263240510971315節(jié)點的最遲完工時間41第41頁，共48頁，2022年，5月2

18、0日，11點10分，星期五緩沖時間該事項在不影響整個工程的前提下，可以延滯的時間。TS(vi)TL(vi)TE(vi)42第42頁，共48頁，2022年，5月20日，11點10分，星期五關鍵路徑從發(fā)點v0出發(fā)到收點vn的一條路徑，這條路上任何工序的延滯必導致整個工程的延滯。關鍵路是整個工程計劃的主要矛盾。關鍵路至少一條，也能是不止一條 ，在關鍵路上TS（vi）=043第43頁，共48頁，2022年，5月20日，11點10分，星期五節(jié)點12345678TE(vi)0426671315TL(vi)04410971315TS(vi)00243000其關鍵路徑是v1, v2, v5, v7, v844第44頁，共48頁，2022年，5月20日，11點10分，星期五v2v7v1v8v5v4v3v612023441344161. 最早完成時間：45第45頁，共48頁，2022年，5月20日，11點10分，星期五v2v7v1v8v5v4v3v612023441