圖論課件--有向圖

1、1,,圖論及其應(yīng)用,應(yīng)用數(shù)學(xué)學(xué)院,,,2,本次課主要內(nèi)容,(一)、有向圖的概念與性質(zhì),(二)、有向圖的連通性,有向圖,(三)、圖的定向問題,(四)、有向路與有向圈,3,1、概念,,定義1 一個(gè)有向圖D是指一個(gè)三元組(V(D) , E(D), фD)。其中，V(D)是非空的頂點(diǎn)集合，E(D)是不與V(D)相交的邊集合，而фD是關(guān)聯(lián)函數(shù)，它使D的每條邊對(duì)應(yīng)D的有序頂點(diǎn)對(duì)(不必相異)。,如果e是D的一條邊，而u與v是使得фD(u,v)=e的頂

2、點(diǎn)，那么稱e是由u連接到v，記為e=。同時(shí)，稱u為e的弧尾(起點(diǎn)), v為e的弧頭(終點(diǎn))。,(一)、有向圖的概念與性質(zhì),注：有向圖可以簡(jiǎn)單地理解為“邊有方向的圖”。,4,,例如：,v3與v2分別是e1 的起點(diǎn)與終點(diǎn)。,定義2 在一個(gè)有向圖D中，具有相同起點(diǎn)和終點(diǎn)的邊稱為平行邊。兩點(diǎn)間平行邊的條數(shù)稱為該兩點(diǎn)間的重?cái)?shù)。,例如，在上圖中，e6與e7是平行邊。,5,,定義3 在一個(gè)有向圖D中，如果沒有有向環(huán)和平行邊，則稱該圖為簡(jiǎn)單有向圖。

3、,定義4 設(shè)D是有向圖，去掉D中邊的方向后得到的無(wú)向圖G，稱為D的基礎(chǔ)圖。又若G是無(wú)向圖，給G的每條邊加上方向后得到的有向圖D稱為G的一個(gè)定向圖。,e3,6,,定義5 設(shè)D是有向圖，v是D中頂點(diǎn)。以v為始點(diǎn)的邊的條數(shù)稱為點(diǎn)v的出度，以v為端點(diǎn)的一個(gè)自環(huán)算1度。點(diǎn)v的出度記為d+(v);以v為終點(diǎn)的邊的條數(shù)稱為點(diǎn)v的入度，以v為端點(diǎn)的一個(gè)自環(huán)算1度。點(diǎn)v的入度記為d-(v);,點(diǎn)v的出度與入度之和稱為點(diǎn)v的度，記為d(v)。,7,,例1

4、 一個(gè)簡(jiǎn)單圖有多少個(gè)定向圖？,答：因?yàn)槊織l邊有2種定向方式，所以共有2 m(G)種定向。,例2 求證：G存在一個(gè)定向圖D，使得對(duì) ，有,證明：不失一般性，設(shè)G是連通圖。G中奇度頂點(diǎn)個(gè)數(shù)必然為偶數(shù)個(gè)，將偶數(shù)個(gè)奇數(shù)度頂點(diǎn)配對(duì)，然后在每一對(duì)配對(duì)頂點(diǎn)間連一條邊得到歐拉圖G1。在G1中用Fluery算法求出G的一歐拉環(huán)游C,然后順次地在C上標(biāo)上方向，由此得到C的定向圖C1。,在C1中，去掉添加的邊后，得到G的定向圖

5、D.顯然：,8,,對(duì) ，有,2、性質(zhì),定理1 設(shè)D=(V, E)是有向圖，則：,證明：由出度與入度的定義立即可得上面等式。,3、有向圖的矩陣表示,9,,E=｛e1,e2,…,em｝,(1) 稱A(D)=(aij) n×n是D的鄰接矩陣，其中aij是vi為始點(diǎn)，vj為終點(diǎn)的邊的條數(shù)，1≦i≦n,1≦j≦n。,定義6 設(shè)D=(V,E)是有向圖，其中V=｛v1,v2,…,vn｝,(2) 若D無(wú)環(huán)。稱矩

6、陣M=(mij)n×m是D的關(guān)聯(lián)矩陣，其中,10,,例1 寫出下面有向圖D1的鄰接陣和D2的關(guān)聯(lián)陣。,11,,1、相關(guān)概念,(二)、有向圖的連通性,(1) 有向途徑(閉途徑)、跡(閉跡)和路(圈),上面概念與無(wú)向圖中相關(guān)概念類似。,(2) 有向圖中頂點(diǎn)間的連通性,定義7 設(shè)D=(V, E)是有向圖，u與v是D中兩個(gè)頂點(diǎn)。,1) 若D中存在一條(u，v)路，則稱u可達(dá)v,記為u→v。規(guī)定u →u。,2) 若D中存在一條(u，v)

7、路或(v, u)路，則稱u與v是單向連通的。,12,,3) 若D中存在一條(u，v)路和一條(v, u)路，則稱u與v是雙向連通的或強(qiáng)連通的。,定義8 設(shè)D=(V, E)是有向圖。,1) 若D的基礎(chǔ)圖是連通的，稱D是弱連通圖；,2) 若D的中任意兩點(diǎn)是單向連通的，稱D是單向連通圖；,3) 若D的中任意兩點(diǎn)是雙向連通的，稱D是強(qiáng)連通圖；,13,在上面三圖中，D1是強(qiáng)連通的，D2是單向連通的，而D3僅為弱連通圖。,關(guān)于強(qiáng)連通圖，我們有如下結(jié)

8、論：,定理1： 有向圖D=(V,E)是強(qiáng)連通的，當(dāng)且僅當(dāng)D中存在包含D中所有頂點(diǎn)的回路。,證明：“必要性”,設(shè)V(D)=｛v1,v2,…,vn｝。由于D是強(qiáng)連通圖，所以，對(duì)任意兩點(diǎn)vi與vj, 都存在(vi, vj)路，同時(shí)也存在(vj ,vi)路。所以存在如下閉途徑：v1→v2→…→vn→v1。這是一條包含D的所有頂點(diǎn)的回路。,14,“充分性”,不失一般性，設(shè)C= v1→v2→…→vn→v1是包含D的所有頂點(diǎn)的一條回路。對(duì)于D的任意兩

9、點(diǎn)vi與vj(i<j) ,一方面，由C可得到vi到vj的途徑vi →vi+1 →… →vj。另一方面，由C又可得到vj到vi的途徑vj →vj+1 →…vi-1 →vi。所以D中任意兩點(diǎn)是強(qiáng)連通的，即D是強(qiáng)連通圖。,例2 說(shuō)明下圖D是強(qiáng)連通圖。,解：v1v5v6v2v4v3v2v4v5v6v2v1是含D所有頂點(diǎn)的一條回路。,15,例3 求下圖D的強(qiáng)連通分支、單向連通分支。,定義9 設(shè)D`是有向圖D=(V, E)的一個(gè)子圖。如果D`

10、是強(qiáng)連通的(單向連通的、弱連通的),且D中不存在真包含D`的子圖是強(qiáng)連通的(單向連通的、弱連通的),則稱D`是D的一個(gè)強(qiáng)連通分支(單向連通分支、弱連通分支)。,16,(1) D的強(qiáng)連通分支,｛1｝,｛2, 3, 9, 8, 4, 7｝,｛5｝,｛6｝,上面點(diǎn)集導(dǎo)出的子圖是 D的強(qiáng)連通分支。,17,(2) D的單向連通分支,D的單向連通分支就是D本身。,注：求D的強(qiáng)、弱連通分支比較容易，求單向分支比較困難。,定理2： 有向圖D=(V,E)

11、的每個(gè)點(diǎn)位于且僅位于D的某個(gè)強(qiáng)(弱)連通分支中。,證明：對(duì)于弱連通分支情形，命題結(jié)論是顯然的。,對(duì)于強(qiáng)連通分支情形，因?yàn)椴浑y證明：D中頂點(diǎn)間的強(qiáng)連通關(guān)系是等價(jià)關(guān)系。該等價(jià)關(guān)系對(duì)應(yīng)的等價(jià)類在D中的導(dǎo)出子圖必然是D的一個(gè)強(qiáng)分支。而D的一個(gè)強(qiáng)分支包含的頂點(diǎn)也必然是該等價(jià)關(guān)系的一個(gè)等價(jià)類。,18,但是，對(duì)于單向連通分支來(lái)說(shuō)，D的某個(gè)頂點(diǎn)，可能會(huì)分屬于D的若干個(gè)單向連通分支。原因是單向連通關(guān)系不是等價(jià)關(guān)系。,(三)、圖的定向問題,圖的定向問題是有

12、向圖中的一個(gè)典型問題之一，具有廣泛的應(yīng)用背景。,城市交通網(wǎng)設(shè)計(jì)問題: 一座城市為某種需要，要把所有街道改為單行道，使得人們?cè)谌我鈨蓚€(gè)位置都可以相互到達(dá)。如何設(shè)計(jì)單行道方向？,圖論建模：街道交叉口模型為圖的頂點(diǎn)，兩點(diǎn)連線當(dāng)且僅當(dāng)該兩點(diǎn)是某街道的端點(diǎn)。,19,問題等價(jià)于在模型圖中給出其強(qiáng)連通定向。,對(duì)于任意一個(gè)無(wú)環(huán)圖G，要對(duì)其作強(qiáng)連通定向，需要解決兩個(gè)問題：一是強(qiáng)連通定向的存在性問題，二是如何定向問題。,上面兩個(gè)問題都已經(jīng)得到解決。,1、存

13、在性問題,定理3( 羅賓斯，1939) 非平凡連通圖G具有強(qiáng)連通定向當(dāng)且僅當(dāng)G是2邊連通的。,羅賓斯(1915---2001), 美國(guó)拓?fù)鋵W(xué)家，數(shù)理統(tǒng)計(jì)學(xué)家。,2、強(qiáng)連通定向算法,20,2、強(qiáng)連通定向算法,該算法采用頂點(diǎn)標(biāo)號(hào)方法給邊標(biāo)上方向。設(shè)G=(V, E)是2邊連通圖。,(1) 在G中任取頂點(diǎn)w, 令l (w)=1, L=｛w｝,U=V-｛w｝,A=Φ;,(2) 在L中求點(diǎn)v, 使得l (v)最大且滿足在U中存在其鄰點(diǎn)u。然后作有向

14、邊。令l (u)=l (v)+1 , L = L∪｛u｝,U=U-｛u｝且A=A∪｛ ｝;,(3) 若L≠V,轉(zhuǎn)(2); 否則轉(zhuǎn)(4);,(4) 對(duì)剩下的未賦予方向的邊，按由標(biāo)號(hào)值大的頂點(diǎn)指向標(biāo)號(hào)值小的頂點(diǎn)賦予方向。,21,,例4 求下圖G的強(qiáng)連通定向。,解: (1) 取點(diǎn)v1, 令l (v1)=1, L=｛v1｝, U=｛v2,v3,…,v7｝,A=Φ;,(2) 在U中取點(diǎn)v7 , 作邊。令l (v7)=l (v1)+1=2,,L

15、=｛v1,v7｝, U=｛v2,v3,…,v6｝, A=｛ ｝,22,,(2) 在L中取v7, U中取點(diǎn)v6 , 作邊。令l (v6)=l (v7)+1=3,,L =｛v1,v7,v6｝, U=｛v2,v3,…,v5｝, A=｛ , ｝,(2) 在L中取v6, U中取點(diǎn)v5 , 作邊。令l (v5)=l (v6)+1=4,,L =｛v1,v7,v6,v5｝, U=｛v2,v3, v4｝, A=｛ , , ｝,23,,(2) 在L

16、中取v4, U中取點(diǎn)v2 , 作邊。令l (v2)=l (v4)+1=5,,L =｛v1,v7,v6,v5,v2｝, U=｛v3, v4｝, A=｛ , , , ｝,(2) 在L中取v2, U中取點(diǎn)v3 , 作邊。令l (v3)=l (v2)+1=6,,L =｛v1,v7,v6,v5,v2,v3｝, U=｛v4｝, A=｛ , , , , ｝,24,,(2) 在L中取v3, U中取點(diǎn)v4 , 作邊。令l (v4)=l (v3

17、)+1=7,,L =｛v1,v7,v6,v5,v2,v3,v4｝, U=Φ, A=｛ , , , , , ｝,(3) U=Φ, 所以，由(4) ,對(duì)剩下的邊賦予方向。,25,,1、有向路的性質(zhì),(四)、有向路與有向圈,定理4 (加萊)有向圖D中最長(zhǎng)有向路長(zhǎng)度下界是,證明：設(shè)A是D中使得D1=D-A不包含有向圈的極小邊集合。又假定D1中最長(zhǎng)有向路的長(zhǎng)度為k。,設(shè)C=｛1,2,…,k+1｝是顏色集合。按如下方法給D1中頂點(diǎn)著色：,當(dāng)D

18、1中以v為起點(diǎn)的最長(zhǎng)有向路的長(zhǎng)度為i-1時(shí)，則給頂點(diǎn)v著上i色。,如此得到D1的k+1個(gè)頂點(diǎn)子集：｛V1,V2,…,Vk+1｝,26,,下面證明：｛V1,V2,…,Vk+1｝構(gòu)成D的色劃分。,首先證明：D1中任意一條有向路的兩個(gè)端點(diǎn)一定著了不同顏色。,設(shè)P是D1中的任意一條(u, v)路。設(shè)v著了i色，則以v為起點(diǎn)的最長(zhǎng)路Q的長(zhǎng)度為i-1。因?yàn)镈1中沒有有向圈，所以，u不可能在Q上，于是P的長(zhǎng)度至少為i, 這表明u沒有著i色。,其次證明

19、：D中任一有向邊的端點(diǎn)著了不同顏色。,事實(shí)上：設(shè)e=uv是D的任意一條邊。若e是D1中邊，則因e是路。由前面證明，e的端點(diǎn)著了不同色；,27,,設(shè)e=uv是D的任意一條邊。若e不是D1中邊，則因A的極小性，D+uv必然有唯一圈C， 顯然，C-uv是D1中的一條(u, v)路，所以，u與v著了不同色。,由此，證明了定理。,2、有向圈的性質(zhì),定理5 設(shè)D=(V,E) 是有向圖。,(1) 若D中存在子圖H使得對(duì)任意的v ∈V(H)均有d+(

20、v)>0(或d-(v)>0),則D中存在有向圈。,(2) 若D連通，且對(duì)任意的v ∈V(D)均有d+(v)=1(或d-(v)=1),則D中存在唯一有向圈。,28,,定理6 設(shè)D=(V,E) 是有向圖。D中存在有向歐拉環(huán)游，當(dāng)且僅當(dāng)D連通且每個(gè)點(diǎn)的出度和入度相等；,D中存在有向歐拉跡，當(dāng)且僅當(dāng)D連通且除了兩個(gè)點(diǎn)外，每個(gè)點(diǎn)的出度和入度相等。而這兩個(gè)點(diǎn)中，一個(gè)點(diǎn)的入度比出度大1，另一個(gè)點(diǎn)出度比入度大1.,在各種比賽中，循環(huán)比賽