離散數(shù)學(xué)圖的基本概念

1第1頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月通路與回路

定義

給定圖G=<V,E>（無向或有向的），設(shè)G中頂點(diǎn)與邊的交替序列

=v0e1v1e2…elvl：若

i(1

i

l),vi

1和vi是ei的端點(diǎn)(對(duì)于有向圖,要求vi

1是始點(diǎn),vi是終點(diǎn)),則稱

為通路,v0是通路的起點(diǎn),vl是通路的終點(diǎn),l為通路的長(zhǎng)度.又若v0=vl，則稱

為回路.理解：通路或回路是點(diǎn)與邊的交替序列，邊的端點(diǎn)恰好是前后的兩個(gè)點(diǎn)長(zhǎng)度＝邊數(shù)2第2頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月若通路(回路)中所有頂點(diǎn)(對(duì)于回路,除v0=vl)各異，則稱為初級(jí)通路(初級(jí)回路).初級(jí)通路又稱作路徑,初級(jí)回路又稱作圈.路上各點(diǎn)不重復(fù)若通路(回路)中所有邊各異,則稱為簡(jiǎn)單通路(簡(jiǎn)單回路),否則稱為復(fù)雜通路(復(fù)雜回路).路上各邊不重復(fù)3第3頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月通路與回路(續(xù))說明:在無向圖中，環(huán)是長(zhǎng)度為1的圈,兩條平行邊構(gòu)成長(zhǎng)度為2的圈.無向簡(jiǎn)單圖中,所有圈的長(zhǎng)度

3在有向圖中，環(huán)是長(zhǎng)度為1的圈,兩條方向相反邊構(gòu)成長(zhǎng)度為2的圈.在有向簡(jiǎn)單圖中,所有圈的長(zhǎng)度

2.4第4頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月通路與回路(續(xù))定理

在n階圖G中，若從頂點(diǎn)vi到vj（vi

vj）存在通路，則從vi到vj存在長(zhǎng)度小于等于n

1的通路.推論

在n階圖G中，若從頂點(diǎn)vi到vj（vi

vj）存在通路，則從vi到vj存在長(zhǎng)度小于等于n

1的初級(jí)通路.定理

在一個(gè)n階圖G中，若存在vi到自身的回路，則一定存在vi到自身長(zhǎng)度小于等于n的回路.推論

在一個(gè)n階圖G中，若存在vi到自身的簡(jiǎn)單回路，則一定存在長(zhǎng)度小于等于n的初級(jí)回路.5第5頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月無向圖的連通性設(shè)無向圖G=<V,E>,u與v連通:u與v之間有通路.規(guī)定u與自身總連通.連通關(guān)系：R={<u,v>|u,v

V且u

v}是V上的等價(jià)關(guān)系連通圖:平凡圖,或者任意兩點(diǎn)都連通的圖連通分支:V關(guān)于R的等價(jià)類的導(dǎo)出子圖設(shè)V/R={V1,V2,…,Vk},G[V1],G[V2],…,G[Vk]是G的連通分支,連通分支個(gè)數(shù)記作p(G)=k.G是連通圖

p(G)=16第6頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月短程線與距離u與v之間的短程線:u與v之間長(zhǎng)度最短的通路u與v之間的距離d(u,v):u與v之間短程線的長(zhǎng)度若u與v不連通,規(guī)定d(u,v)=∞.性質(zhì)：d(u,v)

0,且d(u,v)=0

u=vd(u,v)=d(v,u)（對(duì)稱性）d(u,v)+d(v,w)

d(u,w)（三角不等式)7第7頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月點(diǎn)割集（v－點(diǎn)；V’－點(diǎn)集；e－邊；E’－變集）

記G

v:從G中刪除v及關(guān)聯(lián)的邊

G

V

:從G中刪除V

中所有的頂點(diǎn)及關(guān)聯(lián)的邊G

e:從G中刪除eG

E

:從G中刪除E

中所有邊定義

設(shè)無向圖G=<V,E>,如果存在頂點(diǎn)子集V

V,使p(G

V

)>p(G)，而且刪除V

的任何真子集V

后（

V

V

），p(G

V

)=p(G),則稱V

為G的點(diǎn)割集.若{v}為點(diǎn)割集,則稱v為割點(diǎn).理解：刪除點(diǎn)后連通分支數(shù)可能增加，會(huì)減少嗎？8第8頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月點(diǎn)割集(續(xù))例{v1,v4},{v6}是點(diǎn)割集,v6是割點(diǎn).{v2,v5}是點(diǎn)割集嗎？9第9頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月邊割集定義

設(shè)無向圖G=<V,E>,E

E,若p(G

E

)>p(G)且

E

E

,p(G

E

)=p(G),則稱E

為G的邊割集.若{e}為邊割集,則稱e為割邊或橋.下圖中，{e1,e2}，{e1,e3,e5,e6}，{e8}等是邊割集，e8是橋，{e7,e9,e5,e6}是邊割集嗎？10第10頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月幾點(diǎn)說明：Kn無點(diǎn)割集（完全圖）n階零圖既無點(diǎn)割集，也無邊割集.若G連通，E

為邊割集，則p(G

E

)=2若G連通，V

為點(diǎn)割集，則p(G

V

)

211第11頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月有向圖的連通性

設(shè)有向圖D=<V,E>u可達(dá)v:u到v有通路.規(guī)定u到自身總是可達(dá)的.可達(dá)具有自反性和傳遞性D弱連通(也稱連通):基圖為無向連通圖有向邊改為無向邊后是連通圖D單向連通:

u,v

V，u可達(dá)v

或v可達(dá)u

D強(qiáng)連通:

u,v

V，u與v相互可達(dá)強(qiáng)連通

單向連通

弱連通12第12頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月有向圖的連通性(續(xù))

(1)(2)(3)例下圖(1)強(qiáng)連通,(2)單連通,(3)弱連通每個(gè)頂點(diǎn)有進(jìn)有出部分頂點(diǎn)有進(jìn)有出13第13頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月有向圖的短程線與距離u到v的短程線:u到v長(zhǎng)度最短的通路(u可達(dá)v)u與v之間的距離d<u,v>:u到v的短程線的長(zhǎng)度若u不可達(dá)v,規(guī)定d<u,v>=∞.性質(zhì)：d<u,v>

0,且d<u,v>=0

u=vd<u,v>+d<v,w>

d<u,w>

注意:沒有對(duì)稱性14第14頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月7.3圖的矩陣表示無向圖的關(guān)聯(lián)矩陣有向圖的關(guān)聯(lián)矩陣有向圖的鄰接矩陣有向圖的可達(dá)矩陣15第15頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月無向圖的關(guān)聯(lián)矩陣定義設(shè)無向圖G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},

令mij為vi與ej的關(guān)聯(lián)次數(shù)，稱(mij)n

m為G的關(guān)聯(lián)矩陣，記為M(G).性質(zhì)16第16頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月v1v2v4v3e1e2e3e4e5關(guān)聯(lián)次數(shù)為可能取值為0，1，217第17頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月無向圖的相鄰矩陣v1v2v4v3e1e2e3e4e5(1)相鄰矩陣是對(duì)稱矩陣。(2)對(duì)角元素aii≠0,表示結(jié)點(diǎn)vi處有環(huán)。(3)如aij＞1,表示vi與vj間有平行邊。aij+2

18第18頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月V1V2V3V4V5V1V2V3V4V519第19頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月有向圖的關(guān)聯(lián)矩陣定義設(shè)無環(huán)有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令

則稱(mij)n

m為D的關(guān)聯(lián)矩陣，記為M(D).20第20頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月v4v1v2v3e1e2e3e4e5性質(zhì):

(4)平行邊對(duì)應(yīng)的列相同21第21頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月定義設(shè)有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令為頂點(diǎn)vi鄰接到頂點(diǎn)vj邊的條數(shù)，稱()n

n為D的鄰接矩陣,記作A(D),簡(jiǎn)記為A.性質(zhì)有向圖的鄰接矩陣

22第22頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月v2v1v4v323第23頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月D中的通路及回路數(shù)定理設(shè)A為n階有向圖D的鄰接矩陣,則Al(l

1)中元素為D中vi到vj長(zhǎng)度為l的通路數(shù)，為vi到自身長(zhǎng)度為l的回路數(shù)，為D中長(zhǎng)度為l的通路總數(shù)，為D中長(zhǎng)度為l的回路總數(shù).24第24頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月D中的通路及回路數(shù)(續(xù))例有向圖D如圖所示,求A,A2,A3,A4,

并回答問題：(1)D中長(zhǎng)度為1,2,3,4的通路各有多少條？其中回路分別為多少條？(2)D中長(zhǎng)度小于或等于4的通路為多少條？其中有多少條回路？推論設(shè)Bl=A+A2+…+Al(l

1),則Bl中元素為D中長(zhǎng)度小于或等于l的通路數(shù)，為D中長(zhǎng)度小于或等于l的回路數(shù).25第25頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月例(續(xù))

長(zhǎng)度通路回路

合計(jì)50818121133141417326第26頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月有向圖的可達(dá)矩陣

定義設(shè)D=<V,E>為有向圖,V={v1,v2,…,vn},令

稱(pij)n

n為D的可達(dá)矩陣,記作P(D),簡(jiǎn)記為P.性質(zhì):

P(D)主對(duì)角線上的元素全為1.D強(qiáng)連通當(dāng)且僅當(dāng)P(D)的元素全為1.27第27頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月有向圖的可達(dá)矩陣(續(xù))例右圖所示的有向圖D的可達(dá)矩陣為28第28頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月如何求有向圖的可達(dá)矩陣設(shè)D=<V,E>為有向圖，|V|=n,A為D的鄰接矩陣；先求R＝（rij）＝A+A2+...+An再求可達(dá)矩陣P＝（pij）29第29頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月7.4最短路徑及關(guān)鍵路徑對(duì)于有向圖或無向圖G的每條邊，附加一個(gè)實(shí)數(shù)w(e)，則稱w(e)為邊e上的權(quán).G連同附加在各邊上的實(shí)數(shù)，稱為帶權(quán)圖.設(shè)帶權(quán)圖G=<V,E,W>,G中每條邊的權(quán)都大于等于0.u,v為G中任意兩個(gè)頂點(diǎn)，從u到v的所有通路中帶權(quán)最小的通路稱為u到v的最短路徑.求給定兩個(gè)頂點(diǎn)之間的最短路徑，稱為最短路徑問題.30第30頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月算法：Dijkstra(標(biāo)號(hào)法)31第31頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月v2v0v1v3v4v5141762253例：求圖中v0與v5的最短路徑32第32頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月vikv0v1v2v3v4v50

01411386238437

41047959013749v0v1v2v4v333第33頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月2.關(guān)鍵路徑問題PERT圖設(shè)D=<V,E,W>是n階有向帶權(quán)圖D是簡(jiǎn)單圖D中無環(huán)路有一個(gè)頂點(diǎn)出度為0，稱為發(fā)點(diǎn)；有一個(gè)頂點(diǎn)入度為0，稱為收點(diǎn)記邊<vi,vj>的權(quán)為wij,它常常表示時(shí)間34第34頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月Pert圖的應(yīng)用用Pert中有向邊→表示工序，邊上權(quán)表示完成工序的時(shí)間；用pert圖中結(jié)點(diǎn)vi表示某個(gè)事項(xiàng)，表示某些工序的完工，同時(shí)表示某些工序可以開工。習(xí)慣上所有的有向邊均從左向右。Pert－ProgramEvaluationandReviewTechnic，計(jì)劃評(píng)審技術(shù)35第35頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月關(guān)鍵路徑從始點(diǎn)到終點(diǎn)的一條最長(zhǎng)路徑（發(fā)點(diǎn)到收點(diǎn)的一條最長(zhǎng)路徑）通過求各點(diǎn)的最早完成時(shí)間來求關(guān)鍵路徑最早完成時(shí)間：自發(fā)點(diǎn)v1開始，沿最長(zhǎng)路徑（按權(quán)計(jì)算）到達(dá)vi所需時(shí)間，稱為vi的最早完成時(shí)間，記為TE（vi），i=1,2,…,n。TE(vi)表示在前面所有工序均沒有耽誤的情況下，該事項(xiàng)最早可能完成的時(shí)間，此時(shí)前面的工序均必須完成。也是后續(xù)工程最早開始的時(shí)間。36第36頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月這樣從始點(diǎn)出發(fā)，TE(v0)＝0，一直計(jì)算到收點(diǎn)vn，TE(vn)就是工程的最早完工時(shí)間。37第37頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月1234657824423326324026671315節(jié)點(diǎn)的最早完工時(shí)間38第38頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月2．事項(xiàng)的最晚完成時(shí)間

TL(vi)：在保證收點(diǎn)vn的最早完成時(shí)間不增加的條件下，該事項(xiàng)vi最晚必須完成的時(shí)間，稱為該點(diǎn)vi最晚完成時(shí)間，記為TL(vi)。因?yàn)橛行┕ば虿辉陉P(guān)鍵路上,這些工序有個(gè)緩沖時(shí)間,稍遲一些時(shí)間動(dòng)工，不會(huì)導(dǎo)致整個(gè)工程的完工時(shí)間，但這也有個(gè)限度，TL(vi)就是不耽誤整個(gè)工程的最早完工條件下，該工序最遲的開工時(shí)間，過了這時(shí)間開工將影響整個(gè)工程。39第39頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月其算法是從收點(diǎn)開始向后計(jì)算：因v0和vn均在關(guān)鍵路上,TE（vn）=TL（vn），TE（v0）=TL（v0）=040第40頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月12346578244233263240510971315節(jié)點(diǎn)的最遲完工時(shí)間41第41頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月緩沖時(shí)間該事項(xiàng)在不影響整個(gè)工程的前提下，可以延滯的時(shí)間。TS(vi)＝TL(vi)－TE(vi)42第42頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月關(guān)鍵