圖論課件--有向圖

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

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

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

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

5、D.顯然：,8,,對 ，有,2、性質(zhì),定理1 設(shè)D=(V, E)是有向圖，則：,證明：由出度與入度的定義立即可得上面等式。,3、有向圖的矩陣表示,9,,E=｛e1,e2,…,em｝,(1) 稱A(D)=(aij) n×n是D的鄰接矩陣，其中aij是vi為始點，vj為終點的邊的條數(shù)，1≦i≦n,1≦j≦n。,定義6 設(shè)D=(V,E)是有向圖，其中V=｛v1,v2,…,vn｝,(2) 若D無環(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) 有向途徑(閉途徑)、跡(閉跡)和路(圈),上面概念與無向圖中相關(guān)概念類似。,(2) 有向圖中頂點間的連通性,定義7 設(shè)D=(V, E)是有向圖，u與v是D中兩個頂點。,1) 若D中存在一條(u，v)路，則稱u可達v,記為u→v。規(guī)定u →u。,2) 若D中存在一條(u，v)

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

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

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

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

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

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

13、在性問題,定理3( 羅賓斯，1939) 非平凡連通圖G具有強連通定向當(dāng)且僅當(dāng)G是2邊連通的。,羅賓斯(1915---2001), 美國拓撲學(xué)家，數(shù)理統(tǒng)計學(xué)家。,2、強連通定向算法,20,2、強連通定向算法,該算法采用頂點標(biāo)號方法給邊標(biāo)上方向。設(shè)G=(V, E)是2邊連通圖。,(1) 在G中任取頂點w, 令l (w)=1, L=｛w｝,U=V-｛w｝,A=Φ;,(2) 在L中求點v, 使得l (v)最大且滿足在U中存在其鄰點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) 對剩下的未賦予方向的邊，按由標(biāo)號值大的頂點指向標(biāo)號值小的頂點賦予方向。,21,,例4 求下圖G的強連通定向。,解: (1) 取點v1, 令l (v1)=1, L=｛v1｝, U=｛v2,v3,…,v7｝,A=Φ;,(2) 在U中取點v7 , 作邊。令l (v7)=l (v1)+1=2,,L

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

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

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

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

19、：D中任一有向邊的端點著了不同顏色。,事實上：設(shè)e=uv是D的任意一條邊。若e是D1中邊，則因e是路。由前面證明，e的端點著了不同色；,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使得對任意的v ∈V(H)均有d+(

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