圖論課件有向圖

本次課主要內(nèi)容(一)、有向圖的概念與性質(zhì)(二)、有向圖的連通性有向圖(三)、圖的定向問題(四)、有向路與有向圈1本次課主要內(nèi)容(一)、有向圖的概念與性質(zhì)(二)、有向圖的連通

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的頂點，那么稱e是由u連接到v，記為e=<u,v>。同時，稱u為e的弧尾(起點),v為e的弧頭(終點)。(一)、有向圖的概念與性質(zhì)注：有向圖可以簡單地理解為“邊有方向的圖”。21、概念定義1一個有向圖D是

例如：有向圖Dv4v3v2v1e2e1e4e3e6e5e7v3與v2分別是e1

的起點與終點。定義2在一個有向圖D中，具有相同起點和終點的邊稱為平行邊。兩點間平行邊的條數(shù)稱為該兩點間的重數(shù)。例如，在上圖中，e6與e7是平行邊。3例如：有向圖Dv4v3v2v1e2e1e

定義3在一個有向圖D中，如果沒有有向環(huán)和平行邊，則稱該圖為簡單有向圖。定義4設(shè)D是有向圖，去掉D中邊的方向后得到的無向圖G，稱為D的基礎(chǔ)圖。又若G是無向圖，給G的每條邊加上方向后得到的有向圖D稱為G的一個定向圖。e3非簡單有向圖Dv4v3v2v1e2e1e4e6e5e7簡單有向圖Dv4v3v2v1e2e1e4e6e54定義3在一個有向圖D中，如果沒有有向

定義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)。有向圖Dv4v3v2v1e2e1e4e6e5e75定義5設(shè)D是有向圖，v是D中頂點。以

例1一個簡單圖有多少個定向圖？答：因為每條邊有2種定向方式，所以共有2m(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的定向圖D.顯然：6例1一個簡單圖有多少個定向圖？

對，有

2、性質(zhì)定理1設(shè)D=(V,E)是有向圖，則：證明：由出度與入度的定義立即可得上面等式。

3、有向圖的矩陣表示7對，有

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)。稱矩陣M=(mij)n×m是D的關(guān)聯(lián)矩陣，其中8E=｛e1,e2,…,em｝(1

例1寫出下面有向圖D1的鄰接陣和D2的關(guān)聯(lián)陣。v4v3v2v1D1v4v3v2v1e1e4e3e2e5D29例1寫出下面有向圖D1的鄰接陣和D2的

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

3)若D中存在一條(u，v)路和一條(v,u)路，則稱u與v是雙向連通的或強(qiáng)連通的。D1D2D3定義8設(shè)D=(V,E)是有向圖。1)若D的基礎(chǔ)圖是連通的，稱D是弱連通圖；2)若D的中任意兩點是單向連通的，稱D是單向連通圖；3)若D的中任意兩點是雙向連通的，稱D是強(qiáng)連通圖；113)若D中存在一條(u，v)路和一條(v在上面三圖中，D1是強(qiáng)連通的，D2是單向連通的，而D3僅為弱連通圖。關(guān)于強(qiáng)連通圖，我們有如下結(jié)論：定理1：有向圖D=(V,E)是強(qiáng)連通的，當(dāng)且僅當(dāng)D中存在包含D中所有頂點的回路。證明：“必要性”設(shè)V(D)=｛v1,v2,…,vn｝。由于D是強(qiáng)連通圖，所以，對任意兩點vi與vj,都存在(vi,vj)路，同時也存在(vj,vi)路。所以存在如下閉途徑：v1→v2→…→vn→v1。這是一條包含D的所有頂點的回路。12在上面三圖中，D1是強(qiáng)連通的，D2是單向連通的，而“充分性”不失一般性，設(shè)C=v1→v2→…→vn→v1是包含D的所有頂點的一條回路。對于D的任意兩點vi與vj(i<j),一方面，由C可得到vi到vj的途徑vi→vi+1→…→vj。另一方面，由C又可得到vj到vi的途徑vj→vj+1→…vi-1→vi。所以D中任意兩點是強(qiáng)連通的，即D是強(qiáng)連通圖。例2說明下圖D是強(qiáng)連通圖。v1v5v4v2v3v6D解：v1v5v6v2v4v3v2v4v5v6v2v1是含D所有頂點的一條回路。13“充分性”不失一般性，設(shè)C=v1→v2例3求下圖D的強(qiáng)連通分支、單向連通分支。定義9設(shè)D`是有向圖D=(V,E)的一個子圖。如果D`是強(qiáng)連通的(單向連通的、弱連通的),且D中不存在真包含D`的子圖是強(qiáng)連通的(單向連通的、弱連通的),則稱D`是D的一個強(qiáng)連通分支(單向連通分支、弱連通分支)。613254879D14例3求下圖D的強(qiáng)連通分支、單向連通分支。(1)D的強(qiáng)連通分支｛1｝｛2,3,9,8,4,7｝613254879D｛5｝｛6｝

上面點集導(dǎo)出的子圖是D的強(qiáng)連通分支。32487916515(1)D的強(qiáng)連通分支｛1｝｛2,3,9,8(2)D的單向連通分支D的單向連通分支就是D本身。613254879D注：求D的強(qiáng)、弱連通分支比較容易，求單向分支比較困難。定理2：有向圖D=(V,E)的每個點位于且僅位于D的某個強(qiáng)(弱)連通分支中。證明：對于弱連通分支情形，命題結(jié)論是顯然的。對于強(qiáng)連通分支情形，因為不難證明：D中頂點間的強(qiáng)連通關(guān)系是等價關(guān)系。該等價關(guān)系對應(yīng)的等價類在D中的導(dǎo)出子圖必然是D的一個強(qiáng)分支。而D的一個強(qiáng)分支包含的頂點也必然是該等價關(guān)系的一個等價類。16(2)D的單向連通分支D的單向連通分支就是D本身但是，對于單向連通分支來說，D的某個頂點，可能會分屬于D的若干個單向連通分支。原因是單向連通關(guān)系不是等價關(guān)系。(三)、圖的定向問題圖的定向問題是有向圖中的一個典型問題之一，具有廣泛的應(yīng)用背景。城市交通網(wǎng)設(shè)計問題:一座城市為某種需要，要把所有街道改為單行道，使得人們在任意兩個位置都可以相互到達(dá)。如何設(shè)計單行道方向？圖論建模：街道交叉口模型為圖的頂點，兩點連線當(dāng)且僅當(dāng)該兩點是某街道的端點。17但是，對于單向連通分支來說，D的某個頂點，可能會分問題等價于在模型圖中給出其強(qiáng)連通定向。對于任意一個無環(huán)圖G，要對其作強(qiáng)連通定向，需要解決兩個問題：一是強(qiáng)連通定向的存在性問題，二是如何定向問題。上面兩個問題都已經(jīng)得到解決。1、存在性問題定理3(羅賓斯，1939)非平凡連通圖G具有強(qiáng)連通定向當(dāng)且僅當(dāng)G是2邊連通的。羅賓斯(1915---2001),美國拓?fù)鋵W(xué)家，數(shù)理統(tǒng)計學(xué)家。2、強(qiáng)連通定向算法18問題等價于在模型圖中給出其強(qiáng)連通定向。2、強(qiáng)連通定向算法該算法采用頂點標(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。然后作有向邊<v,u>。令l(u)=l(v)+1,L=L∪｛u｝,U=U-｛u｝且A=A∪｛<v,u>｝;(3)若L≠V,轉(zhuǎn)(2);否則轉(zhuǎn)(4);(4)對剩下的未賦予方向的邊，按由標(biāo)號值大的頂點指向標(biāo)號值小的頂點賦予方向。192、強(qiáng)連通定向算法該算法采用頂點標(biāo)號方法

例4求下圖G的強(qiáng)連通定向。v2v1v6v5v4v3v7G解:(1)取點v1,令l(v1)=1,L=｛v1｝,U=｛v2,v3,…,v7｝,A=Φ;

(2)在U中取點v7,作邊<v1,v7>。令l(v7)=l(v1)+1=2,L=｛v1,v7｝,U=｛v2,v3,…,v6｝,A=｛<v1,v7>｝Gv2v1(1)v6v5v4v3V7(2)20例4求下圖G的強(qiáng)連通定向。v2v1v6

(2)在L中取v7,U中取點v6,作邊<v7,v6>。令l(v6)=l(v7)+1=3,L=｛v1,v7,v6｝,U=｛v2,v3,…,v5｝,A=｛<v1,v7>,<v7,v6>｝Gv2v1(1)V6(3)v5v4v3v7(2)

(2)在L中取v6,U中取點v5,作邊<v6,v5>。令l(v5)=l(v6)+1=4,L=｛v1,v7,v6,v5｝,U=｛v2,v3,v4｝,A=｛<v1,v7>,<v7,v6>,<v6,v5>｝Gv2v1(1)V6(3)v5(4)v4v3v7(2)21(2)在L中取v7,U中取點v6,

(2)在L中取v4,U中取點v2,作邊<v4,v2>。令l(v2)=l(v4)+1=5,L=｛v1,v7,v6,v5,v2｝,U=｛v3,v4｝,A=｛<v1,v7>,<v7,v6>,<v6,v5>,<v4,v2>｝Gv2(5)v1(1)V6(3)v5(4)v4v3v7(2)

(2)在L中取v2,U中取點v3,作邊<v2,v3>。令l(v3)=l(v2)+1=6,L=｛v1,v7,v6,v5,v2,v3｝,U=｛v4｝,A=｛<v1,v7>,<v7,v6>,<v6,v5>,<v4,v2>,<v2,v3>｝Gv2(5)v1(1)V6(3)v5(4)v4v3(6)v7(2)22(2)在L中取v4,U中取點v2,

(2)在L中取v3,U中取點v4,作邊<v3,v4>。令l(v4)=l(v3)+1=7,L=｛v1,v7,v6,v5,v2,v3,v4｝,U=Φ,A=｛<v1,v7>,<v7,v6>,<v6,v5>,<v4,v2>,<v2,v3>,<v3,v4>｝Gv2(5)v1(1)V6(3)v5(4)v4(7)v3(6)v7(2)(3)U=Φ,所以，由(4),對剩下的邊賦予方向。Gv2(5)v1(1)V6(3)v5(4)v4(7)v3(6)v7(2)23(2)在L中取v3,U中取點v4,

1、有向路的性質(zhì)(四)、有向路與有向圈

定理4(加萊)有向圖D中最長有向路長度下界是

證明：設(shè)A是D中使得D1=D-A不包含有向圈的極小邊集合。又假定D1中最長有向路的長度為k。

設(shè)C=｛1,2,…,k+1｝是顏色集合。按如下方法給D1中頂點著色：

當(dāng)D1中以v為起點的最長有向路的長度為i-1時，則給頂點v著上i色。

如此得到D1的k+1個頂點子集：｛V1,V2,…,Vk+1｝241、有向路的性質(zhì)(四)、有向路與有向圈

下面證明：｛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色。

其次證明：D中任一有向邊的端點著了不同顏色。

事實上：設(shè)e=uv是D的任意一條邊。若e是D1中邊，則因e是路。由前面證明，e的端點著了不同色；25下面證明：｛V1,V2,…,Vk+1｝構(gòu)

設(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+(v)>0(或d-(v)>0),則D中存在有向圈。(2)若D連通，且對任意的v∈V(D)均有d+(v)=1(或d-(v)=1),則D中存在唯一有向圈。26設(shè)e=uv是D的任意一條邊。若e不是D

定理6設(shè)D=(V,E)是有向圖。D中存在有向歐拉環(huán)游，當(dāng)且僅當(dāng)D連通且每個點的出度和入度相等；D中存在有向歐拉跡，當(dāng)且僅當(dāng)D連通且除了兩個點外，每個點的出度和入度相等。而這兩個點中，一個點的入度比出度大1，另一個點出度比入度大1.

在各種比賽中，循環(huán)比賽是常見形式，即對與對之間都要進(jìn)行比賽。循環(huán)比賽的結(jié)果可以用所謂的“競賽圖”來表示。u隊?wèi)?zhàn)勝了v隊，則由點u向v畫一條有向邊。顯然，“競賽圖”是完全圖的一種定向圖。27定理6設(shè)D=(V,E)是有向圖。D

n階完全圖的定向有多少不同方式？2n種！當(dāng)n=12時，有1540億個。

定理7競賽圖中存在有向H圈。28n階完全圖的定向有多少不同方式？2n種！

作業(yè)

P256---259習(xí)題9：1，2，5，7，8，11，12，1329作業(yè)P256---259習(xí)題9：1，2，5ThankYou!30ThankYou!30本次課主要內(nèi)容(一)、有向圖的概念與性質(zhì)(二)、有向圖的連通性有向圖(三)、圖的定向問題(四)、有向路與有向圈31本次課主要內(nèi)容(一)、有向圖的概念與性質(zhì)(二)、有向圖的連通

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的頂點，那么稱e是由u連接到v，記為e=<u,v>。同時，稱u為e的弧尾(起點),v為e的弧頭(終點)。(一)、有向圖的概念與性質(zhì)注：有向圖可以簡單地理解為“邊有方向的圖”。321、概念定義1一個有向圖D是

例如：有向圖Dv4v3v2v1e2e1e4e3e6e5e7v3與v2分別是e1

的起點與終點。定義2在一個有向圖D中，具有相同起點和終點的邊稱為平行邊。兩點間平行邊的條數(shù)稱為該兩點間的重數(shù)。例如，在上圖中，e6與e7是平行邊。33例如：有向圖Dv4v3v2v1e2e1e

定義3在一個有向圖D中，如果沒有有向環(huán)和平行邊，則稱該圖為簡單有向圖。定義4設(shè)D是有向圖，去掉D中邊的方向后得到的無向圖G，稱為D的基礎(chǔ)圖。又若G是無向圖，給G的每條邊加上方向后得到的有向圖D稱為G的一個定向圖。e3非簡單有向圖Dv4v3v2v1e2e1e4e6e5e7簡單有向圖Dv4v3v2v1e2e1e4e6e534定義3在一個有向圖D中，如果沒有有向

定義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)。有向圖Dv4v3v2v1e2e1e4e6e5e735定義5設(shè)D是有向圖，v是D中頂點。以

例1一個簡單圖有多少個定向圖？答：因為每條邊有2種定向方式，所以共有2m(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的定向圖D.顯然：36例1一個簡單圖有多少個定向圖？

對，有

2、性質(zhì)定理1設(shè)D=(V,E)是有向圖，則：證明：由出度與入度的定義立即可得上面等式。

3、有向圖的矩陣表示37對，有

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)。稱矩陣M=(mij)n×m是D的關(guān)聯(lián)矩陣，其中38E=｛e1,e2,…,em｝(1

例1寫出下面有向圖D1的鄰接陣和D2的關(guān)聯(lián)陣。v4v3v2v1D1v4v3v2v1e1e4e3e2e5D239例1寫出下面有向圖D1的鄰接陣和D2的

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

3)若D中存在一條(u，v)路和一條(v,u)路，則稱u與v是雙向連通的或強(qiáng)連通的。D1D2D3定義8設(shè)D=(V,E)是有向圖。1)若D的基礎(chǔ)圖是連通的，稱D是弱連通圖；2)若D的中任意兩點是單向連通的，稱D是單向連通圖；3)若D的中任意兩點是雙向連通的，稱D是強(qiáng)連通圖；413)若D中存在一條(u，v)路和一條(v在上面三圖中，D1是強(qiáng)連通的，D2是單向連通的，而D3僅為弱連通圖。關(guān)于強(qiáng)連通圖，我們有如下結(jié)論：定理1：有向圖D=(V,E)是強(qiáng)連通的，當(dāng)且僅當(dāng)D中存在包含D中所有頂點的回路。證明：“必要性”設(shè)V(D)=｛v1,v2,…,vn｝。由于D是強(qiáng)連通圖，所以，對任意兩點vi與vj,都存在(vi,vj)路，同時也存在(vj,vi)路。所以存在如下閉途徑：v1→v2→…→vn→v1。這是一條包含D的所有頂點的回路。42在上面三圖中，D1是強(qiáng)連通的，D2是單向連通的，而“充分性”不失一般性，設(shè)C=v1→v2→…→vn→v1是包含D的所有頂點的一條回路。對于D的任意兩點vi與vj(i<j),一方面，由C可得到vi到vj的途徑vi→vi+1→…→vj。另一方面，由C又可得到vj到vi的途徑vj→vj+1→…vi-1→vi。所以D中任意兩點是強(qiáng)連通的，即D是強(qiáng)連通圖。例2說明下圖D是強(qiáng)連通圖。v1v5v4v2v3v6D解：v1v5v6v2v4v3v2v4v5v6v2v1是含D所有頂點的一條回路。43“充分性”不失一般性，設(shè)C=v1→v2例3求下圖D的強(qiáng)連通分支、單向連通分支。定義9設(shè)D`是有向圖D=(V,E)的一個子圖。如果D`是強(qiáng)連通的(單向連通的、弱連通的),且D中不存在真包含D`的子圖是強(qiáng)連通的(單向連通的、弱連通的),則稱D`是D的一個強(qiáng)連通分支(單向連通分支、弱連通分支)。613254879D44例3求下圖D的強(qiáng)連通分支、單向連通分支。(1)D的強(qiáng)連通分支｛1｝｛2,3,9,8,4,7｝613254879D｛5｝｛6｝

上面點集導(dǎo)出的子圖是D的強(qiáng)連通分支。32487916545(1)D的強(qiáng)連通分支｛1｝｛2,3,9,8(2)D的單向連通分支D的單向連通分支就是D本身。613254879D注：求D的強(qiáng)、弱連通分支比較容易，求單向分支比較困難。定理2：有向圖D=(V,E)的每個點位于且僅位于D的某個強(qiáng)(弱)連通分支中。證明：對于弱連通分支情形，命題結(jié)論是顯然的。對于強(qiáng)連通分支情形，因為不難證明：D中頂點間的強(qiáng)連通關(guān)系是等價關(guān)系。該等價關(guān)系對應(yīng)的等價類在D中的導(dǎo)出子圖必然是D的一個強(qiáng)分支。而D的一個強(qiáng)分支包含的頂點也必然是該等價關(guān)系的一個等價類。46(2)D的單向連通分支D的單向連通分支就是D本身但是，對于單向連通分支來說，D的某個頂點，可能會分屬于D的若干個單向連通分支。原因是單向連通關(guān)系不是等價關(guān)系。(三)、圖的定向問題圖的定向問題是有向圖中的一個典型問題之一，具有廣泛的應(yīng)用背景。城市交通網(wǎng)設(shè)計問題:一座城市為某種需要，要把所有街道改為單行道，使得人們在任意兩個位置都可以相互到達(dá)。如何設(shè)計單行道方向？圖論建模：街道交叉口模型為圖的頂點，兩點連線當(dāng)且僅當(dāng)該兩點是某街道的端點。47但是，對于單向連通分支來說，D的某個頂點，可能會分問題等價于在模型圖中給出其強(qiáng)連通定向。對于任意一個無環(huán)圖G，要對其作強(qiáng)連通定向，需要解決兩個問題：一是強(qiáng)連通定向的存在性問題，二是如何定向問題。上面兩個問題都已經(jīng)得到解決。1、存在性問題定理3(羅賓斯，1939)非平凡連通圖G具有強(qiáng)連通定向當(dāng)且僅當(dāng)G是2邊連通的。羅賓斯(1915---2001),美國拓?fù)鋵W(xué)家，數(shù)理統(tǒng)計學(xué)家。2、強(qiáng)連通定向算法48問題等價于在模型圖中給出其強(qiáng)連通定向。2、強(qiáng)連通定向算法該算法采用頂點標(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。然后作有向邊<v,u>。令l(u)=l(v)+1,L=L∪｛u｝,U=U-｛u｝且A=A∪｛<v,u>｝;(3)若L≠V,轉(zhuǎn)(2);否則轉(zhuǎn)(4);(4)對剩下的未賦予方向的邊，按由標(biāo)號值大的頂點指向標(biāo)號值小的頂點賦予方向。492、強(qiáng)連通定向算法該算法采用頂點標(biāo)號方法

例4求下圖G的強(qiáng)連通定向。v2v1v6v5v4v3v7G解:(1)取點v1,令l(v1)=1,L=｛v1｝,U=｛v2,v3,…,v7｝,A=Φ;

(2)在U中取點v7,作邊<v1,v7>。令l(v7)=l(v1)+1=2,L=｛v1,v7｝,U=｛v2,v3,…,v6｝,A=｛<v1,v7>｝Gv2v1(1)v6v5v4v3V7(2)50例4求下圖G的強(qiáng)連通定向。v2v1v6

(2)在L中取v7,U中取點v6,作邊<v7,v6>。令l(v6)=l(v7)+1=3,L=｛v1,v7,v6｝,U=｛v2,v3,…,v5｝,A=｛<v1,v7>,<v7,v6>｝Gv2v1(1)V6(3)v5v4v3v7(2)

(2)在L中取v6,U中取點v5,作邊<v6,v5>。令l(v5)=l(v6)+1=4,L=｛v1,v7,v6,v5｝,U=｛v2,v3,v4｝,A=｛<v1,v7>,<v7,v6>,<v6,v5>｝Gv2v1(1)V6(3)v5(4)v4v3v7(2)51(2)在L中取v7,U中取點v6,

(2)在L中取v4,U中取點v2,作邊<v4,v2>。令l(v2)=l(v4)+1=5,L=｛v1,v7,v6,v5,v2｝,U=｛v3,v4｝,A=｛<v1,v7>,<v7,v6>,<v6,v5>,<v4,v2>｝Gv2(5)v1(1)V6(3)v5(4)v4v3v7(2)

(2)在L中取v2,U中取點v3,作邊<v2,v3>。令l(v3)=l(v2)+1=6,L=｛v1,v7,v6,v5,v2,v3｝,U=｛v4｝,A=｛<v1,v7>,<v7,v6>,<v6,v5>,<v4,v2>,<v2,v3>｝Gv2(5)v1(1)V6(3)v5(4)v4v3(6)v7(2)52(2)在L中取v4,U中取點v2,

(2)在L中取v3,U中取點v4,作邊<v3,v4>。令l(v4)=l(v3)+1=7,L=｛v1,v7,v6,v5,v2,v3,v4｝,U=Φ,A=｛<v1,v7>,<v7,v6>,<v6,v5>,<v4,v2>,<v2,v3>,<v3,v4>｝Gv2(5)v1(1)V6(3)v5(4)v4(7)v3(6)v7(2)(3)U