圖論及其應(yīng)用(27)

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

2、條邊，而的一條邊，而u與與v是使得是使得D(u,v)=e的頂點(diǎn)，的頂點(diǎn)，那么稱那么稱e是由是由u連接到連接到v，記為，記為e=。同時(shí)，稱。同時(shí)，稱u為為e的的弧尾弧尾(起點(diǎn)起點(diǎn)), v為為e的弧頭的弧頭(終點(diǎn)終點(diǎn))。(一一)、有向圖的概念與性質(zhì)、有向圖的概念與性質(zhì) 注：有向圖可以簡單地理解為注：有向圖可以簡單地理解為“邊有方向的圖邊有方向的圖”。3 例如：例如：有向圖有向圖Dv4v3v2v1e2e1e4e3e6e5e7132,ev v v3與與v2分別是分別是e1 的起點(diǎn)與終點(diǎn)。的起點(diǎn)與終點(diǎn)。 定義定義2 在一個(gè)有向圖在一個(gè)有向圖D中，具有相同起點(diǎn)和終點(diǎn)的邊中，具有相同起點(diǎn)和終點(diǎn)的邊稱為平行邊

3、。兩點(diǎn)間平行邊的條數(shù)稱為該兩點(diǎn)間的重?cái)?shù)。稱為平行邊。兩點(diǎn)間平行邊的條數(shù)稱為該兩點(diǎn)間的重?cái)?shù)。 例如，在上圖中，例如，在上圖中，e6與與e7是平行邊。是平行邊。4 定義定義3 在一個(gè)有向圖在一個(gè)有向圖D中，如果沒有有向環(huán)和平行邊，中，如果沒有有向環(huán)和平行邊，則稱該圖為簡單有向圖。則稱該圖為簡單有向圖。 定義定義4 設(shè)設(shè)D是有向圖，去掉是有向圖，去掉D中邊的方向后得到的無向中邊的方向后得到的無向圖圖G，稱為，稱為D的基礎(chǔ)圖。又若的基礎(chǔ)圖。又若G是無向圖，給是無向圖，給G的每條邊的每條邊加上方向后得到的有向圖加上方向后得到的有向圖D稱為稱為G的一個(gè)定向圖。的一個(gè)定向圖。e3非簡單有向圖非簡單有向圖Dv

4、4v3v2v1e2e1e4e6e5e7簡單有向圖簡單有向圖Dv4v3v2v1e2e1e4e6e55 定義定義5 設(shè)設(shè)D是有向圖，是有向圖，v是是D中頂點(diǎn)。以中頂點(diǎn)。以v為始點(diǎn)的邊的條為始點(diǎn)的邊的條數(shù)稱為點(diǎn)數(shù)稱為點(diǎn)v的出度，以的出度，以v為端點(diǎn)的一個(gè)自環(huán)算為端點(diǎn)的一個(gè)自環(huán)算1度。點(diǎn)度。點(diǎn)v的出度的出度記為記為d+(v);以以v為終點(diǎn)的邊的條數(shù)稱為點(diǎn)為終點(diǎn)的邊的條數(shù)稱為點(diǎn)v的入度，以的入度，以v為端點(diǎn)為端點(diǎn)的一個(gè)自環(huán)算的一個(gè)自環(huán)算1度。點(diǎn)度。點(diǎn)v的入度記為的入度記為d-(v); 點(diǎn)點(diǎn)v的出度與入度之和稱為點(diǎn)的出度與入度之和稱為點(diǎn)v的度，記為的度，記為d(v)。有向圖有向圖Dv4v3v2v1e2e1

5、e4e6e5e74()2dv4()2dv4()4d v6 例例1 一個(gè)簡單圖有多少個(gè)定向圖？一個(gè)簡單圖有多少個(gè)定向圖？ 答：因?yàn)槊織l邊有答：因?yàn)槊織l邊有2種定向方式，所以共有種定向方式，所以共有2 m(G)種定向。種定向。 例例2 求證：求證：G存在一個(gè)定向圖存在一個(gè)定向圖D，使得對(duì)，使得對(duì) ，有，有()vV D ( )( )1dvdv 證明：不失一般性，設(shè)證明：不失一般性，設(shè)G是連通圖。是連通圖。G中奇度頂點(diǎn)個(gè)數(shù)必中奇度頂點(diǎn)個(gè)數(shù)必然為偶數(shù)個(gè)，將偶數(shù)個(gè)奇數(shù)度頂點(diǎn)配對(duì)，然后在每一對(duì)配對(duì)然為偶數(shù)個(gè)，將偶數(shù)個(gè)奇數(shù)度頂點(diǎn)配對(duì)，然后在每一對(duì)配對(duì)頂點(diǎn)間連一條邊得到歐拉圖頂點(diǎn)間連一條邊得到歐拉圖G1。在。在

6、G1中用中用Fluery算法求出算法求出G的一歐拉環(huán)游的一歐拉環(huán)游C,然后順次地在然后順次地在C上標(biāo)上方向，由此得到上標(biāo)上方向，由此得到C的的定向圖定向圖C1。 在在C1中，去掉添加的邊后，得到中，去掉添加的邊后，得到G的定向圖的定向圖D.顯然：顯然：7 對(duì)對(duì) ，有，有()vV D ( )( )1dvdv 2、性質(zhì)、性質(zhì) 定理定理1 設(shè)設(shè)D=(V, E)是有向圖，則：是有向圖，則：()()( )( )()v V Dv V Ddvdvm D 證明：由出度與入度的定義立即可得上面等式。證明：由出度與入度的定義立即可得上面等式。 3、有向圖的矩陣表示、有向圖的矩陣表示8 E=e1,e2,em (1)

7、 稱稱A(D)=(aij) nn是是D的鄰接矩陣，其中的鄰接矩陣，其中aij是是vi為始點(diǎn)，為始點(diǎn)，vj為終點(diǎn)的邊的條數(shù)，為終點(diǎn)的邊的條數(shù)，1in,1jn。 定義定義6 設(shè)設(shè)D=(V,E)是有向圖，其中是有向圖，其中V=v1,v2,vn (2) 若若D無環(huán)。稱矩陣無環(huán)。稱矩陣M=(mij)nm是是D的關(guān)聯(lián)矩陣，其中的關(guān)聯(lián)矩陣，其中1,-1(1,1),0,.ijijijvemveinjm 是 的始點(diǎn)， 是邊 的終點(diǎn)，其它9 例例1 寫出下面有向圖寫出下面有向圖D1的鄰接陣和的鄰接陣和D2的關(guān)聯(lián)陣。的關(guān)聯(lián)陣。v4v3v2v1D1v4v3v2v1e1e4e3e2e5D2101000212()0000

8、0010A D21000011110()0110100011M D10 1、相關(guān)概念、相關(guān)概念(二二)、有向圖的連通性、有向圖的連通性 (1) 有向途徑有向途徑(閉途徑閉途徑)、跡、跡(閉跡閉跡)和路和路(圈圈) 上面概念與無向圖中相關(guān)概念類似。上面概念與無向圖中相關(guān)概念類似。 (2) 有向圖中頂點(diǎn)間的連通性有向圖中頂點(diǎn)間的連通性 定義定義7 設(shè)設(shè)D=(V, E)是有向圖，是有向圖，u與與v是是D中兩個(gè)頂點(diǎn)。中兩個(gè)頂點(diǎn)。 1) 若若D中存在一條中存在一條(u，v)路，則稱路，則稱u可達(dá)可達(dá)v,記為記為uv。規(guī)定規(guī)定u u。 2) 若若D中存在一條中存在一條(u，v)路或路或(v, u)路，則稱

9、路，則稱u與與v是單是單向連通的。向連通的。11 3) 若若D中存在一條中存在一條(u，v)路和一條路和一條(v, u)路，則稱路，則稱u與與v是是雙向連通的或強(qiáng)連通的。雙向連通的或強(qiáng)連通的。D1D2D3 定義定義8 設(shè)設(shè)D=(V, E)是有向圖。是有向圖。 1) 若若D的基礎(chǔ)圖是連通的，稱的基礎(chǔ)圖是連通的，稱D是弱連通圖；是弱連通圖； 2) 若若D的中任意兩點(diǎn)是單向連通的，稱的中任意兩點(diǎn)是單向連通的，稱D是單向連通圖；是單向連通圖； 3) 若若D的中任意兩點(diǎn)是雙向連通的，稱的中任意兩點(diǎn)是雙向連通的，稱D是強(qiáng)連通圖；是強(qiáng)連通圖；12 在上面三圖中，在上面三圖中，D1是強(qiáng)連通的，是強(qiáng)連通的，D2

10、是單向連通的，而是單向連通的，而D3僅為弱連通圖。僅為弱連通圖。 關(guān)于強(qiáng)連通圖，我們有如下結(jié)論：關(guān)于強(qiáng)連通圖，我們有如下結(jié)論： 定理定理1： 有向圖有向圖D=(V,E)是強(qiáng)連通的，當(dāng)且僅當(dāng)是強(qiáng)連通的，當(dāng)且僅當(dāng)D中存在中存在包含包含D中所有頂點(diǎn)的回路。中所有頂點(diǎn)的回路。 證明：證明：“必要性必要性” 設(shè)設(shè)V(D)=v1,v2,vn。由于。由于D是強(qiáng)連通圖，所以，對(duì)任是強(qiáng)連通圖，所以，對(duì)任意兩點(diǎn)意兩點(diǎn)vi與與vj, 都存在都存在(vi, vj)路，同時(shí)也存在路，同時(shí)也存在(vj ,vi)路。所以存路。所以存在如下閉途徑：在如下閉途徑：v1v2vnv1。這是一條包含。這是一條包含D的所有的所有頂點(diǎn)的

11、回路。頂點(diǎn)的回路。13 “充分性充分性” 不失一般性，設(shè)不失一般性，設(shè)C= v1v2vnv1是包含是包含D的所有頂?shù)乃许旤c(diǎn)的一條回路。對(duì)于點(diǎn)的一條回路。對(duì)于D的任意兩點(diǎn)的任意兩點(diǎn)vi與與vj(ij) ,一方面，由一方面，由C可得到可得到vi到到vj的途徑的途徑vi vi+1 vj。另一方面，由。另一方面，由C又可又可得到得到vj到到vi的途徑的途徑vj vj+1 vi-1 vi。所以。所以D中任意兩點(diǎn)是中任意兩點(diǎn)是強(qiáng)連通的，即強(qiáng)連通的，即D是強(qiáng)連通圖。是強(qiáng)連通圖。 例例2 說明下圖說明下圖D是強(qiáng)連通圖。是強(qiáng)連通圖。v1v5v4v2v3v6D 解：解：v1v5v6v2v4v3v2v4v5v6v

12、2v1是含是含D所有頂點(diǎn)的一條回路。所有頂點(diǎn)的一條回路。14 例例3 求下圖求下圖D的強(qiáng)連通分支、單向連通分支。的強(qiáng)連通分支、單向連通分支。 定義定義9 設(shè)設(shè)D是是有向圖有向圖D=(V, E)的一個(gè)子圖。如果的一個(gè)子圖。如果D是是強(qiáng)連通的強(qiáng)連通的(單向連通的、弱連通的單向連通的、弱連通的),且且D中不存在真包含中不存在真包含D的子圖是強(qiáng)連通的的子圖是強(qiáng)連通的(單向連通的、弱連通的單向連通的、弱連通的),則稱則稱D是是D的的一個(gè)強(qiáng)連通分支一個(gè)強(qiáng)連通分支(單向連通分支、弱連通分支單向連通分支、弱連通分支)。613254879D15 (1) D的強(qiáng)連通分支的強(qiáng)連通分支12, 3, 9, 8, 4,

13、7613254879D56 上面點(diǎn)集導(dǎo)出的子圖是上面點(diǎn)集導(dǎo)出的子圖是 D的強(qiáng)的強(qiáng)連通分支。連通分支。32487916516 (2) D的單向連通分支的單向連通分支D的單向連通分支就是的單向連通分支就是D本身。本身。613254879D注：求注：求D的強(qiáng)、弱連通分支比較的強(qiáng)、弱連通分支比較容易，求單向分支比較困難。容易，求單向分支比較困難。 定理定理2： 有向圖有向圖D=(V,E)的每個(gè)點(diǎn)位于且僅位于的每個(gè)點(diǎn)位于且僅位于D的某個(gè)的某個(gè)強(qiáng)強(qiáng)(弱弱)連通分支中。連通分支中。 證明：對(duì)于弱連通分支情形，命題結(jié)論是顯然的。證明：對(duì)于弱連通分支情形，命題結(jié)論是顯然的。 對(duì)于強(qiáng)連通分支情形，因?yàn)椴浑y證明：對(duì)

14、于強(qiáng)連通分支情形，因?yàn)椴浑y證明：D中頂點(diǎn)間的強(qiáng)中頂點(diǎn)間的強(qiáng)連通關(guān)系是等價(jià)關(guān)系。該等價(jià)關(guān)系對(duì)應(yīng)的等價(jià)類在連通關(guān)系是等價(jià)關(guān)系。該等價(jià)關(guān)系對(duì)應(yīng)的等價(jià)類在D中的導(dǎo)中的導(dǎo)出子圖必然是出子圖必然是D的一個(gè)強(qiáng)分支。而的一個(gè)強(qiáng)分支。而D的一個(gè)強(qiáng)分支包含的頂?shù)囊粋€(gè)強(qiáng)分支包含的頂點(diǎn)也必然是該等價(jià)關(guān)系的一個(gè)等價(jià)類。點(diǎn)也必然是該等價(jià)關(guān)系的一個(gè)等價(jià)類。17 但是，對(duì)于單向連通分支來說，但是，對(duì)于單向連通分支來說，D的某個(gè)頂點(diǎn)，可能會(huì)分的某個(gè)頂點(diǎn)，可能會(huì)分屬于屬于D的若干個(gè)單向連通分支。原因是單向連通關(guān)系不是等的若干個(gè)單向連通分支。原因是單向連通關(guān)系不是等價(jià)關(guān)系。價(jià)關(guān)系。(三三)、圖的定向問題、圖的定向問題 圖的定向問題

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

16、一個(gè)無環(huán)圖對(duì)于任意一個(gè)無環(huán)圖G，要對(duì)其作強(qiáng)連通定向，需要解決，要對(duì)其作強(qiáng)連通定向，需要解決兩個(gè)問題：一是強(qiáng)連通定向的存在性問題，二是如何定向問兩個(gè)問題：一是強(qiáng)連通定向的存在性問題，二是如何定向問題。題。 上面兩個(gè)問題都已經(jīng)得到解決。上面兩個(gè)問題都已經(jīng)得到解決。 1、存在性問題、存在性問題 定理定理3( 羅賓斯，羅賓斯，1939) 非平凡連通圖非平凡連通圖G具有強(qiáng)連通定向當(dāng)具有強(qiáng)連通定向當(dāng)且僅當(dāng)且僅當(dāng)G是是2邊連通的。邊連通的。羅賓斯羅賓斯(1915-2001), 美國拓?fù)鋵W(xué)家，數(shù)理統(tǒng)計(jì)學(xué)家。美國拓?fù)鋵W(xué)家，數(shù)理統(tǒng)計(jì)學(xué)家。 2、強(qiáng)連通定向算法、強(qiáng)連通定向算法19 2、強(qiáng)連通定向算法、強(qiáng)連通定向算法

17、 該算法采用頂點(diǎn)標(biāo)號(hào)方法給邊標(biāo)上方向。設(shè)該算法采用頂點(diǎn)標(biāo)號(hào)方法給邊標(biāo)上方向。設(shè)G=(V, E)是是2邊連通圖。邊連通圖。 (1) 在在G中任取頂點(diǎn)中任取頂點(diǎn)w, 令令l (w)=1, L=w,U=V-w,A=; ; (2) 在在L中求點(diǎn)中求點(diǎn)v, 使得使得l (v)最大且滿足在最大且滿足在U中存在其鄰點(diǎn)中存在其鄰點(diǎn)u。然。然后作有向邊后作有向邊。令。令l (u)=l (v)+1 , L = Lu,U=U-u且且A=A ; (3) 若若LV,轉(zhuǎn)轉(zhuǎn)(2); 否則轉(zhuǎn)否則轉(zhuǎn)(4); (4) 對(duì)剩下的未賦予方向的邊，按由標(biāo)號(hào)值大的頂點(diǎn)指向標(biāo)對(duì)剩下的未賦予方向的邊，按由標(biāo)號(hào)值大的頂點(diǎn)指向標(biāo)號(hào)值小的頂點(diǎn)賦予

18、方向。號(hào)值小的頂點(diǎn)賦予方向。20 例例4 求下圖求下圖G的強(qiáng)連通定向。的強(qiáng)連通定向。v2v1v6v5v4v3v7G 解解: (1) 取點(diǎn)取點(diǎn)v1, 令令l (v1)=1, L=v1, U=v2,v3,v7,A=; ; (2) 在在U中取點(diǎn)中取點(diǎn)v7 , 作邊作邊。令。令l (v7)=l (v1)+1=2, L =v1,v7, U=v2,v3,v6, A= Gv2v1(1)v6v5v4v3V7(2)21 (2) 在在L中取中取v7, U中取點(diǎn)中取點(diǎn)v6 , 作邊作邊。令。令l (v6)=l (v7)+1=3, L =v1,v7,v6, U=v2,v3,v5, A= , Gv2v1(1)V6(3)

19、v5v4v3v7(2) (2) 在在L中取中取v6, U中取點(diǎn)中取點(diǎn)v5 , 作邊作邊。令。令l (v5)=l (v6)+1=4, L =v1,v7,v6,v5, U=v2,v3, v4, A= , , Gv2v1(1)V6(3)v5(4)v4v3v7(2)22 (2) 在在L中取中取v4, U中取點(diǎn)中取點(diǎn)v2 , 作邊作邊。令。令l (v2)=l (v4)+1=5, L =v1,v7,v6,v5,v2, U=v3, v4, A= , , , Gv2(5)v1(1)V6(3)v5(4)v4v3v7(2) (2) 在在L中取中取v2, U中取點(diǎn)中取點(diǎn)v3 , 作邊作邊。令。令l (v3)=l (

20、v2)+1=6, L =v1,v7,v6,v5,v2,v3, U=v4, A= , , , , Gv2(5)v1(1)V6(3)v5(4)v4v3(6)v7(2)23 (2) 在在L中取中取v3, U中取點(diǎn)中取點(diǎn)v4 , 作邊作邊。令。令l (v4)=l (v3)+1=7, L =v1,v7,v6,v5,v2,v3,v4, U=, A= , , , , , Gv2(5)v1(1)V6(3)v5(4)v4(7)v3(6)v7(2) (3) U=, 所以，由所以，由(4) ,對(duì)剩下的邊賦予方向。對(duì)剩下的邊賦予方向。Gv2(5)v1(1)V6(3)v5(4)v4(7)v3(6)v7(2)24 1、有

21、向路的性質(zhì)、有向路的性質(zhì)(四四)、有向路與有向圈、有向路與有向圈 定理定理4 (加萊加萊)有向圖有向圖D中最長有向路長度下界是中最長有向路長度下界是()-1D 證明：設(shè)證明：設(shè)A是是D中使得中使得D1=D-A不包含有向圈的極小邊不包含有向圈的極小邊集合。又假定集合。又假定D1中最長有向路的長度為中最長有向路的長度為k。 設(shè)設(shè)C=1,2,k+1是顏色集合。按如下方法給是顏色集合。按如下方法給D1中中頂點(diǎn)著色：頂點(diǎn)著色： 當(dāng)當(dāng)D1中以中以v為起點(diǎn)的最長有向路的長度為為起點(diǎn)的最長有向路的長度為i-1時(shí)，則給時(shí)，則給頂點(diǎn)頂點(diǎn)v著上著上i色。色。 如此得到如此得到D1的的k+1個(gè)頂點(diǎn)子集：個(gè)頂點(diǎn)子集：V

22、1,V2,Vk+125 下面證明：下面證明：V1,V2,Vk+1構(gòu)成構(gòu)成D的色劃分。的色劃分。 首先證明：首先證明：D1中任意一條有向路的兩個(gè)端點(diǎn)一定著了中任意一條有向路的兩個(gè)端點(diǎn)一定著了不同顏色。不同顏色。 設(shè)設(shè)P是是D1中的任意一條中的任意一條(u, v)路。設(shè)路。設(shè)v著了著了i色，則以色，則以v為為起點(diǎn)的最長路起點(diǎn)的最長路Q的長度為的長度為i-1。因?yàn)椤Ｒ驗(yàn)镈1中沒有有向圈，所中沒有有向圈，所以，以，u不可能在不可能在Q上，于是上，于是P的長度至少為的長度至少為i, 這表明這表明u沒有沒有著著i色。色。 其次證明：其次證明：D中任一有向邊的端點(diǎn)著了不同顏色。中任一有向邊的端點(diǎn)著了不同顏色。 事實(shí)上：設(shè)事實(shí)上：設(shè)e=uv是是D的任意一條邊。若的任意一條邊。若e是是D1中邊，則中邊，則因因e是路。由前面證明，是路。由前面證明，e的端點(diǎn)著了不同色；的端點(diǎn)著了不同色；26 設(shè)設(shè)e=uv是是D的任意一條邊。若的任意一條邊。若e不是不是D1中邊，則因中邊，則因A的的極小性，極小性，D+uv必然有唯一圈必然有唯一圈C， 顯然，顯然，C-uv是是D1中的一中的一條條(u, v)路，所以，路，所