第8章 有向圖.ppt

1、圖論及其應(yīng)用,第8章 有向圖,圖論及其應(yīng)用,2,8.1 有向圖,有向圖（directed graph；digraph） D =（V，A） V(D) 頂點(diǎn)集。 A(D) 弧集。 弧a = (u,v)：其頭為v，其尾為u； 弧a從u連到(join to)v。 有向子圖（subdigraph） 有向圖D的基礎(chǔ)圖（underlying graph） 對(duì)應(yīng)于D的無向圖G（稱D為G的一個(gè)定向（orientation）圖）,圖論及其應(yīng)用,3,8.1 有向圖,（無向）圖的每個(gè)慨念在有向圖中仍然有效例如，右圖是2-連通圖；有Hamiton 圈；有完美匹配； = = 3；vrswu是它的一條(v,u)-路；vyz

2、wsrv是它的一個(gè)圈，等等。,此外，有向圖還有一些與方向有關(guān)的慨念，如有向途徑（directed walk）、有向跡（directed trail）、有向路（directed path）、有向Euler環(huán)游（direted Euler tour）、有向圈（directed cycle）等等。 例如右圖中，(v, e1, x, e2, y, e3, z, e4, w, e5, u)為一 有向(v,u)-路，可簡(jiǎn)記為 （v,x,y,z,w,u） ； 又， (y,z,w,s,r,x,y) 為一 有向圈。 稱 頂點(diǎn)v為 從u可達(dá)的（reachable from u） 存在有向（u，v）-路。 稱 頂點(diǎn)

3、u與v 為雙向連通的（diconnected；strongly connected） u與v彼此可達(dá)的。,圖論及其應(yīng)用,4,8.1 有向圖,易見，有向圖D = (V, A)中頂點(diǎn)間的雙向連通性是V上的一個(gè)等價(jià)關(guān)系，它的等價(jià)類確定了V的一個(gè)劃分 （V1，Vm），使頂點(diǎn)u與v雙向連通 u與v 同屬某等價(jià)類Vi 。稱每個(gè)導(dǎo)出子圖DV1，DVm為有向圖D的一個(gè)雙向分支（dicomponent；strong component）。當(dāng)D只有一個(gè)雙向分支時(shí)，稱D為雙向連通的。 易見，D的任二雙向分支之間的弧都是同一個(gè)方向的。 例,圖論及其應(yīng)用,5,8.1 有向圖,入度（indegree） 。 出度（outd

4、egree） 。 記號(hào) +， ：最小出、入度； + ， - ：最大出、入度。 稱有向圖D為嚴(yán)格的（strict） 無環(huán)、且不存在兩弧其端點(diǎn)及方向相同。,圖論及其應(yīng)用,6,8.1 有向圖習(xí)題,10.1.1. 一個(gè)簡(jiǎn)單圖有多少個(gè)定向圖？ 10.1.2. 證明： = = 。 10.1.3. 設(shè)有向圖D中無有向圈，則 (a) = 0 ； (b) 存在一個(gè)頂點(diǎn)排序v1，v ，使對(duì)1 i ，每條以vi為 頭的弧其尾都在v1，vi-1 中。 10.1.4. 證明：D是雙向連通的 D是連通的，且D的每個(gè)塊是雙向連通的。 10.1.5. D的逆圖 是把D中每弧的方向都改為其反向所得的有向圖。試用逆圖慨念及習(xí)題1

5、0.1.3.(a) 來證明： 若有向圖D中無有向圈，則+ = 0 。 10.1.6. 證明：嚴(yán)格有向圖包含長(zhǎng) max ，+的有向路。 10.1.7. 證明：嚴(yán)格有向圖中若max ，+ = k 1，則D包含長(zhǎng) k+1 的有向圈。,圖論及其應(yīng)用,7,8.1 有向圖習(xí)題（續(xù)）,10.1.8. 設(shè) 矩陣A = aij 為有向圖D的鄰接矩陣，其中aij 是D中以vi為尾、以vj為頭的弧數(shù)。證明：Ak的第(i,j)元素是D中長(zhǎng)為k的（vi ,vj）-有向途徑的數(shù)目。 10.1.9. 設(shè)D1，Dm為D的雙向分支。D的凝聚圖H是一有m個(gè)頂點(diǎn)w1，w 的有向圖。H中存在以wi為尾、以wj為頭的弧，當(dāng)且僅當(dāng)D中存

6、在尾在Di 、而頭在Dj中的弧。證明：H中不包含有向圈。 10.1.10. 證明：任一圖G都有一個(gè)定向圖D，使對(duì)每個(gè)頂點(diǎn)v都有|d+(v) - d-(v)| 1 10.1.11.證明：D是雙向連通的 對(duì) 10.1.12 在連通非空有向圖D中，證明：D是雙向連通的 D中每弧在一有向圈上 10.1.13. 設(shè)D為一以（頂點(diǎn)）u為根的有向圖（對(duì)D中任一頂點(diǎn)，D中都存在一有向(u,v)-路），證明：D中有一以為根的有向樹，中每一（唯一）有向(u,v)-路是D中最短有向(u,v)-路 。 10.1.14. 有向圖中任一有向閉跡恒可劃分為一些邊不重的有向圈的併。,圖論及其應(yīng)用,8,8.1 有向圖習(xí)題（續(xù)）

7、,10.1.15. 設(shè)T =(V,A)為一有向樹（ （無向）樹的一個(gè)定向），F(xiàn)A(T) 。證明：存在一頂點(diǎn)x，它恰只是F中弧的頭（即不能是尾）。,圖論及其應(yīng)用,9,10.2 有向路,定理10.1 (Roy,1967; Gallai,1968) 有向圖D包含一長(zhǎng)為 - 1 的有向路。 證明：令D為D的極大無有向圈、有向生成子圖（注：D 可由空生成子圖作為開始，在保持無有向圈的條件下，通過逐步加弧而得） 。令k為D 中最長(zhǎng)有向路的長(zhǎng)。今用色1，2，k+1對(duì)D 進(jìn)行頂點(diǎn)著色如下： 將v著以色i D 中以v為起點(diǎn)的最長(zhǎng)有向路的長(zhǎng)為i - 1 。來證這是D的正常(k+1)-頂點(diǎn)著色： 先證，D 中任一有

8、向(u,v)-路P的起、終點(diǎn)u與v一定不同色：設(shè)v被著以色i 。則由著色法知，在 D 中以v為起點(diǎn)的一最長(zhǎng)有向路，設(shè)為，Q的長(zhǎng)為i - 1 。由于D 中無有向圈，PQ為一有向路，起點(diǎn)為u，長(zhǎng) i 。從而u上的色j i。 只要再證，D中任一弧(u,v)的兩端一定不同色：當(dāng) (u,v)為D 中的弧時(shí)，它就是D 中的一有向(u,v)-路，從而u與v不同色。,在有向圖中，最長(zhǎng)路的長(zhǎng)和最長(zhǎng)有向路的長(zhǎng)之間并無任何密切的關(guān)系，例如右面的有向圖最長(zhǎng)路的長(zhǎng)為 （可任意大） ，而最長(zhǎng)有向路的長(zhǎng)卻為1,圖論及其應(yīng)用,10,10.2 有向路,當(dāng) (u,v)不是D 中的弧時(shí)，由D 之極大性知 D + (u,v)包含一有

9、向圈C。于是， C - (u,v)是 D 中的有向(v,u)-路，從而u與v也不同色。 由上述知，D為(k+1)-可著色的，因此 k+1 ，得k - 1 ，故D中有長(zhǎng)為 - 1 的有向路。 # 注 定理10.1在如下意義下是最佳的： 對(duì)每個(gè)（無向）圖G，都存在G的一個(gè)定向圖，其最長(zhǎng)有向路的長(zhǎng)恰為 - 1。 證明：令（V1，V-1）為G的正常 -頂點(diǎn)著色。今作G的定向圖D如下：邊uv（不妨設(shè)， u Vi ，v Vj）定向?yàn)榛?(u,v) i - 1的有向路。再由定理10.1得證。 # 稱完全圖的定向圖為競(jìng)賽圖（tournament，是簡(jiǎn)單圖?。?。,圖論及其應(yīng)用,11,10.2 有向路,推論10.

10、1 (Redei,1934) 每個(gè)競(jìng)賽圖都有一Hamilton 路。 證明：注意到 = 即可。 # 設(shè)(u,v)為有向圖D中的一弧，則稱u為v的內(nèi)鄰點(diǎn)（in-neighbour）；稱v為u的外鄰點(diǎn)（out-neighbour）。記 和 分別為有向圖D中頂點(diǎn)v的內(nèi)鄰集和外鄰集。,圖論及其應(yīng)用,12,10.2 有向路,定理10.2 (Chavtal d+(v) = d-(v) , 對(duì) v Vx,y 。 利用習(xí)題10.3.2.證明：D中存在m條弧不重的有向（x，y）-路。 10.3.4* 證明：包含奇圈的雙向連通有向圖也包含有向奇圈。 10.3.5 稱非平凡有向圖D是k-弧連通的，如果對(duì)V的每個(gè)非空

11、真子集S，都有 |(S, S)| k 。證明：非平凡有向圖是雙向連通的當(dāng)且僅當(dāng)它是1-弧連通的。 10.3.6 圖G的伴隨有向圖D(G)是指把G的每邊e都用兩條方向相反而和e有相同端點(diǎn)的弧代替所得的有向圖。 證明： (a) G中的路 和D(G)中的有向路 之間存在一一對(duì)應(yīng) ； (b) D(G)是k-弧連通的當(dāng)且僅當(dāng)G是k-邊連通的。,圖論及其應(yīng)用,20,10.4 工件排序問題,設(shè)一機(jī)器要加工幾種工件J1，J2，Jn ；每當(dāng)加工完一種工件Ji后，為了加工下一工件Jj ，機(jī)器必須用tij時(shí)間進(jìn)行調(diào)整。 問題 求加工順序，使總調(diào)整時(shí)間最短。 在賦權(quán)（tij）有向圖 D （其中：V(D) = J1，J

12、2，Jn ，且每對(duì)頂點(diǎn)間有二反向弧連接）中求一最小權(quán)有向Hamilton 路。 （注 ：如果生產(chǎn)過程是反復(fù)進(jìn)行，則問題變成求最小權(quán)有向Hamilton 圈 。） 注 在賦權(quán)有向圖中求最小權(quán)有向Hamilton 圈（路）問題是NP-hard prob. 。 代替辦法 （Heurestic alg. )1. 作有向圖D, 使V(D) = v1，v，且(vi, vj) A(D) tij tji i j 2. 在D中找一有向Hamilton 路P作為工作排序。（有好算法）,圖論及其應(yīng)用,21,10.4 工件排序問題,注。 本算法去掉了矩陣 tij 中較大的那一半，因此有理由期望得到較好的結(jié)果。當(dāng)然，這

13、只是一種一廂情愿的想法而已。例如，右圖情況下，“去掉了矩陣 tij 中較大的那一半”后，得到的是右圖中用直線段構(gòu)成的競(jìng)賽圖，其中的最短Hamilton 有向路的長(zhǎng)為12；而原問題的最優(yōu)解為4。又，注意到“去掉了矩陣 tij 中較大的那一半”后所得賦權(quán)圖（包含競(jìng)賽圖）中求該圖的最小權(quán)Hamilton 有向路問題，由前述知，仍然是NP-hard 困難問題。,圖論及其應(yīng)用,22,10.4 公路系統(tǒng)的單行線化,問題 任給一圖G是否有一雙向連通定向圖？顯然，G有一雙向連通定向圖 G為2-邊連通圖。 定理10.5 (Robins,1939) G為2-邊連通圖 G有一雙向連通定向圖 。 證明：由G為2-邊連

14、通知，G中含一圈G1 。歸納地定義G1，G2，如下：若Gi不是G的生成子圖，任取G不在Gi中的一個(gè)頂點(diǎn)vi 。由習(xí)題3.2.1.，易見，存在 vi 到Gi 的兩條邊不重的路Pi和Qi 。定義 Gi+1 = Gi Pi Qi 。由于(Gi+1) (Gi) ，該序列一定終止于G的一生成子圖Gn上。 今對(duì)Gn定向如下：把G1定向?yàn)橐挥邢蛉Γ?把Pi定向?yàn)橐灰詖i為起點(diǎn)的有向路；把Qi 定向?yàn)橐詖i為終點(diǎn)的有向路。顯然，每個(gè)Gi有一雙向連通定向。由于Gn是G的一生成子圖，G也存在雙向連通定向圖。,圖論及其應(yīng)用,23,10.4 公路系統(tǒng)的單行線化,定理（Nash-Williams ，1960）G為2k-邊連通的 G有k-弧連通定向圖。 （證略）（即 |（S，S ）| k S V） 上述定理的特殊情形為以下定理，其證明較容易，留給讀者完成： 定理10.6 G為2k-邊連通，且有一Euler 跡 G有一k-弧連通定向圖。 習(xí)題 1