離散數(shù)學(xué)及其應(yīng)用課件：圖的基本概念

圖的基本概念5.1無(wú)向圖及有向圖5.2通路、回路、圖的連通性5.3圖的矩陣表示5.4圖的運(yùn)算5.5

圖的應(yīng)用

5.1無(wú)向圖及有向圖5.1.1無(wú)向圖

無(wú)序積設(shè)A,B為兩集合,稱{{a,b}|a∈A∧b∈B}為A與B的無(wú)序積,記作A&B。將無(wú)序?qū)a,b}記作(a,b)。

定義5.1一個(gè)無(wú)向圖G是一個(gè)二元組<V,E>,即G=<V,E>,其中:(1)V是一個(gè)非空的集合,稱為G的頂點(diǎn)集,V中元素稱為頂點(diǎn)或結(jié)點(diǎn);(2)E是無(wú)序積E&E的一個(gè)多重子集,稱E為G的邊集,E中元素稱為無(wú)向邊或簡(jiǎn)稱邊。

5.1.2有向圖

定義5.2一個(gè)有向圖D是一個(gè)二元組<V,E>,即D=<V,E>,其中:

(1)V同無(wú)向圖中的頂點(diǎn)集;

(2)E是笛卡爾積的多重子集,其元素稱為有向邊,簡(jiǎn)稱邊。

例5.1給定無(wú)向圖和有向圖的圖形如圖5-1(a)和(b)所示,試寫(xiě)出各圖的頂點(diǎn)集和邊集。圖5-1無(wú)向圖和有向圖

5.1.3相關(guān)概念

1.幾種特殊的圖

設(shè)G=<V,E>為一無(wú)向圖或有向圖:

(1)若V,E都是有窮集合,則稱G是有限圖。

(2)若|V|=n,則稱G為n階圖。

(3)若E=?,則稱G為零圖。特別地,若此時(shí)又有|V|=1,則稱G為平凡圖。

(4)若V=?,則稱圖G為空?qǐng)D。

2.關(guān)聯(lián)

定義5.3設(shè)ek=(vi,vj)為無(wú)向圖G=<V,E>中的一條邊,稱vi和vj為ek的端點(diǎn),ek與vi(或vj)是彼此關(guān)聯(lián)的。

(1)無(wú)邊關(guān)聯(lián)的頂點(diǎn)稱為孤立點(diǎn);

(2)若一條邊所關(guān)聯(lián)的兩條邊重合,則稱此邊為環(huán);

(3)ek

與vi(或vj)的關(guān)聯(lián)次數(shù)可用于表達(dá)關(guān)聯(lián)矩陣。

3.相鄰和鄰接

定義5.4設(shè)無(wú)向圖G=<V,E>,vi,vj∈V,ek,el∈E。

(1)若存在一條邊e以vi,vj為端點(diǎn),即e=(vi,vj),則稱vi,vj是彼此相鄰的,簡(jiǎn)稱相鄰的。

(2)若ek,el至少有一個(gè)公共端點(diǎn),則稱ek,el是彼此相鄰的,簡(jiǎn)稱相鄰的。

類似可對(duì)有向圖進(jìn)行定義,只是這時(shí)若ek=(vi,vj),除稱vi,vj是ek的端點(diǎn)外,還稱vi是ek的始點(diǎn),vj是ek的終點(diǎn),vi鄰接到vj,vj鄰接于vi。

例5.2給定圖5-2,試分別寫(xiě)出圖(a)、(b)的最大度和最小度。圖5-2最大度和最小度

5.1.4平行邊、重?cái)?shù)、多重圖、簡(jiǎn)單圖

定義5.6在無(wú)向圖中,關(guān)聯(lián)一對(duì)頂點(diǎn)的無(wú)向邊如果多于1條,稱這些邊為平行邊。平行邊的條數(shù)稱為重?cái)?shù)。在有向圖中,關(guān)聯(lián)一對(duì)頂點(diǎn)的有向邊如果多于1條,且它們的始點(diǎn)與終點(diǎn)相同,則稱這些邊為有向平行邊,簡(jiǎn)稱平行邊。含平行邊的圖稱為多重圖。既不含平行邊,也不含環(huán)的圖稱為簡(jiǎn)單圖。

例5.3觀察圖5-3,指出哪些圖是簡(jiǎn)單圖?哪些圖是多重圖?為什么?圖5-3簡(jiǎn)單圖和多重圖

解據(jù)簡(jiǎn)單圖和多重圖的定義知:(a)、(c)是簡(jiǎn)單圖,因?yàn)樗鼈儫o(wú)環(huán)且不含平行邊;(b)、(d)是多重圖,因?yàn)?b)既有環(huán)又有平行邊,(d)上邊存在一對(duì)有向平行邊。

5.1.5-基本定理(握手定理)

例5.4判斷下列各度數(shù)列哪些是可圖畫(huà)的,哪些是可簡(jiǎn)單圖畫(huà)的。

(1)(3,3,3,3)(2)(3,3,3,2,2)

(3)(5,4,3,2,2)(4)(5,5,5,5,5,1)

解由可圖畫(huà)的充分必要條件知,除(2)的度數(shù)列和為奇數(shù)不可圖畫(huà)外,其余皆可圖畫(huà)。(3)不可簡(jiǎn)單圖畫(huà),因?yàn)棣?G)=5>4,與Δ(G)≤n-1矛盾;(4)不可簡(jiǎn)單圖畫(huà),因?yàn)榍拔妩c(diǎn)的度數(shù)是5,意味著它們要與不相鄰的每個(gè)頂點(diǎn)有關(guān)聯(lián),但最后一個(gè)頂點(diǎn)的度數(shù)為1,不能為前五點(diǎn)提供5度;(1)可簡(jiǎn)單圖畫(huà),只需四點(diǎn)互連即可。

5.1.6無(wú)向完全圖、有向完全圖

定義5.7設(shè)G=<V,E>是n階無(wú)向簡(jiǎn)單圖,若G中任何頂點(diǎn)都與其余的n-1個(gè)頂點(diǎn)相鄰,則稱G為n階無(wú)向完全圖,記作Kn。

設(shè)D=<V,E>為n階有向簡(jiǎn)單圖,若對(duì)于任意的頂點(diǎn)u,v∈V(u≠v),既有有向邊<u,v>,又有<v,u>,則稱D是n階有向完全圖。

設(shè)D=<V,E>為n階有向簡(jiǎn)單圖,若D的基圖為n階無(wú)向完全圖Kn,則稱D為n階競(jìng)賽圖。

注意后文中Kn均指無(wú)向完全圖。

例5.5-在圖5-4中(a)為K4,(b)所示為K5,(c)所示為3階有向完全圖,(d)為4階競(jìng)賽圖。圖5-4完全圖、競(jìng)賽圖

5.1.7子圖

例5.6在圖5-5中,若將(a)視作母圖,則(b)是生成子圖,(c)是由頂點(diǎn)集V1={v1,v2,v3,v5}導(dǎo)出的子圖,(d)是由邊集E1={e1,e4,e5}導(dǎo)出的子圖。同時(shí)(b)也是由邊集E1={e1,e4,e5,e6}導(dǎo)出的子圖,但不是由頂點(diǎn)導(dǎo)出的子圖,因?yàn)閂2={v1,v2,v3,v5}不是V的真子集。圖5-5-母圖、生成子圖、導(dǎo)出子圖

圖5-6補(bǔ)圖

5.1.9圖的同構(gòu)

例5.7試說(shuō)明圖5-7中(a)和(b)是同構(gòu)的。圖5-7圖的同構(gòu)

5.2通路、回路、圖的連通性

5.2.1通路和回路定義5.9給定圖G=<V,E>,設(shè)G中頂點(diǎn)和邊的交替序列為

若Γ滿足如下條件:

(1)vi-1和vi

是ei的端點(diǎn)(在G是有向圖時(shí),要求vi-1是ei

的始點(diǎn),vi

是ei的終點(diǎn)),i=1,2,3,…,n,則稱Γ為頂點(diǎn)v0到vn的通路。

(2)v0和vn分別稱為此通路的起點(diǎn)和終點(diǎn),Γ中邊的數(shù)目n稱為Γ的長(zhǎng)度。

(3)當(dāng)v0=vn時(shí),此通路稱為回路。

若Γ中的所有邊e1,e2,…,en

互不相同,則稱Γ為簡(jiǎn)單通路或一條跡。

若回路中的所有邊互不相同,則稱此回路為簡(jiǎn)單回路或一條閉跡。

若通路的所有頂點(diǎn)v0,v1,v2,…,vn

互不相同(從而所有邊互不相同),則稱此通路為初級(jí)通路或一條路徑。

若回路中,除v0=vn外,其余頂點(diǎn)各不相同,所有邊也各不相同,則稱此回路為初級(jí)回路或圈。

有邊重復(fù)出現(xiàn)的通路稱為復(fù)雜通路,有邊重復(fù)出現(xiàn)的回路稱為復(fù)雜回路。

注意初級(jí)通路(回路)是簡(jiǎn)單通路(回路),但反之不真

由于上文的定義繁多,表5-1中總結(jié)了通路、跡、路徑、回路和圈的一些重要特征,以幫助讀者理解。

例5.8考慮圖5-8中v1到v6的通路有哪些?舉出三個(gè)即可,并說(shuō)明它們的長(zhǎng)度以及是哪種通路。圖5-8無(wú)向圖的通路

例5.9考慮圖5-9中v2到v2的回路有哪些?舉出三個(gè)即可,并說(shuō)明它們是哪種回路。圖5-9有向圖的通路

5.2.2圖的連通性

1.連通

定義5.10在無(wú)向圖G中,若從頂點(diǎn)vi

到vj

存在通路(當(dāng)然從vj

到vi也存在通路),則稱vi

到vj

是連通的。規(guī)定vi

到自身總是連通的。

在有向圖D中,若從頂點(diǎn)vi到vj

存在通路,則稱vi可達(dá)vj。規(guī)定vi到自身總是可達(dá)的。

2.短程線

設(shè)vi,vj為無(wú)向圖G中的任意兩點(diǎn),若vi

與vj是連通的,則稱vi與vj之間長(zhǎng)度最短的通路為vi與vj之間的短程線;短程線的長(zhǎng)度稱為vi與vj之間的距離,記作d(vi,vj)。

設(shè)vi,vj為有向圖D中任意兩點(diǎn),若vi可達(dá)vj,則稱從vi

到vj

長(zhǎng)度最短的通路為vi到vj的短程線;短程線的長(zhǎng)度稱為vi到vj的距離,記作d<vi,vj>。

3.圖的連通性

定義5.11若無(wú)向圖G是平凡圖,或G中任意兩頂點(diǎn)都是連通的,則稱G是連通圖;否則,稱G是非連通圖。

定義5.12設(shè)D是一個(gè)有向圖,如果略去D中各有向邊的方向后所得無(wú)向圖G是連通圖,則稱D是連通圖,或稱D是弱連通圖。

若D中任意兩頂點(diǎn)至少一個(gè)可達(dá)另一個(gè),則稱D是單向連通圖。

若D中任何一對(duì)頂點(diǎn)都是相互可達(dá)的,則稱D是強(qiáng)連通圖。

例5.10在圖5-10中,據(jù)連通圖的相關(guān)定義可知三圖去掉有向邊后的無(wú)向圖都是連通的,所以(a)、(b)、(c)至少都是弱連通的;(a)中a到d是不可達(dá)的且d到a也是不可達(dá)的,所以(a)只是弱連通的;(b)中有通路afedbc,但是c到其余各點(diǎn)皆不可達(dá),所以(b)是單向連通的;(c)中存在回路afedcba,各點(diǎn)都是可達(dá)的,所以(c)是強(qiáng)連通的。圖5-10圖的連通性

5.2.3割集

1.點(diǎn)割集

定義5.13設(shè)無(wú)向圖G=<V,E>,若存在頂點(diǎn)子集V'?V,使G刪除V'(將V'中頂點(diǎn)及其關(guān)聯(lián)的邊都刪除)后,所得子圖G-V'的連通分支數(shù)與G的連通分支數(shù)滿足p(G-V')>p(G),而刪除V'的任何真子集V″后,p(G-V″)=p(G),則稱V'為G的一個(gè)點(diǎn)割集。

若點(diǎn)割集中只有一個(gè)頂點(diǎn)v,則稱v為割點(diǎn)。

2.邊割集

定義5.13(續(xù))若存在邊集子集E'?E,使G刪除E'(將E'中的邊從G中全刪除)后,所得子圖的連通分支數(shù)與G的連通分支數(shù)滿足p(G-E')>p(G),而刪除E'的任何真子集E″后,p(G-E″)=p(G),則稱E'是G的一個(gè)邊割集。

若邊割集中只有一條邊e,則稱e為割邊或橋。

例5.11考慮圖5-11,找出圖中所有的邊割集和點(diǎn)割集。圖5-11邊割集和點(diǎn)割集

5.3圖的矩陣表示

5.3.1無(wú)向圖的關(guān)聯(lián)矩陣

5.3.2有向圖的關(guān)聯(lián)矩陣

試觀察關(guān)聯(lián)矩陣中元素mij,不難發(fā)現(xiàn)有以下性質(zhì):圖5-13有向圖

5.3.3有向圖的鄰接矩陣

1.表示法

設(shè)有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}。令ai(j1)為vi

鄰接到vj

的邊數(shù),稱(ai(j1))n×n為D的鄰接矩陣,記作A(D)。圖5-14有向圖

5.3.4有向圖的可達(dá)矩陣

5.4圖的運(yùn)算

例5.16G1、G2分別如圖5-15(a)、(b)所示,G1+G2如圖5-15(c)所示。圖5-15-兩個(gè)圖的和圖5-16兩個(gè)圖的笛卡爾積

5.5

圖的應(yīng)用

5.5.1無(wú)向圖的加權(quán)矩陣圖論有諸多應(yīng)用,如顯示中國(guó)的各省市之間的高速公路、縱向和橫向的高鐵主動(dòng)脈、航空路線、春節(jié)客流流向、化學(xué)里不同化合物的相關(guān)性等。連接兩個(gè)頂點(diǎn)的邊通?？梢躁P(guān)聯(lián)一個(gè)非負(fù)實(shí)數(shù),稱之為權(quán)(weight)。若圖5-17表示中國(guó)某地市周圍的公路結(jié)構(gòu),則權(quán)可以表示兩地之間的距離,抑或表示時(shí)間或花銷,我們稱這樣的圖為加權(quán)圖(weightedgraph)。圖5-17加權(quán)圖

5.5.2最短路徑算法

設(shè)G是加權(quán)圖,a,z為圖中頂點(diǎn),P為G中從a到z的路徑,L(P)為該路徑上所有邊權(quán)之和。在圖G中,從a到z的路徑有很多種,我們的目標(biāo)是尋找L(P)的最小值,即最短路徑。一種方法是尋找a到z的所有可能路徑,然后選擇距離最短的路徑,隨著頂點(diǎn)數(shù)的增加,這種方法極其耗費(fèi)時(shí)間,所以本節(jié)考慮Dijkstra最短路徑算法,也稱貪婪算法。此外,本節(jié)只考慮正實(shí)數(shù)的權(quán)。

Dijkstra最短路徑算法基本思想:如果avi1vi2…vikz是a到z的最短路徑,則對(duì)每個(gè)t(1≤t≤k),avi1vi2…vit是a到vit的最短路徑。于是可設(shè)置并逐步擴(kuò)充一個(gè)集合S,存放已求出最短路徑的頂點(diǎn),設(shè)尚未確定最短路徑的頂點(diǎn)集合