4.3-有向圖 Euler路.ppt

1、4.3有向圖 Euler路,定義4.3.1 G=(P, A)稱為有向圖，如果P是點集合，A是從一點引到一點(不要求一定是另一點)的弧集合。當(dāng)P為有限集時，G稱為有限有向圖。 若e是一條從點v到點v的弧，則稱v為e的起點，記為v=init(e)；v為e的終點，記為v=fin(e)。 把起點和終點都是點v的弧稱為反身弧，有向圖中兩點(可以是相同的)間的弧可以有無窮條。顯然，有限有向圖中的集合A未必是有限集。即，有限有向圖中的弧可以有無窮多條。,4.3.1 有向圖與有向樹,例：,有向圖中點v的輸出次數(shù)(出度)是集合e|init(e)=v的元數(shù)；點v的輸入次數(shù)(入度)是集合e | fin(e)=v的元

2、數(shù)；點v的度等于點v的輸入次數(shù)加輸出次數(shù)。 今后，為簡便計，有時也將有向圖G中的點v、弧e，寫成vG，eG。,定義4.3.2,設(shè)G，H是有向圖。如果P(H) P(G)，A(H)A(G)，則稱H為G的有向子圖(簡稱子圖)。G是H的母圖。如果H是G的子圖，并且P(H)=P(G)，則稱H是G的支撐子圖。,定義4.3.3,設(shè)G=(P, A)是有向圖，弧序列(e1, ,en)稱為G的從v到v其長度為n的有向路，如果1）eiA(G), i=1, ,n 2）v=init(e1), v=fin(en) 3）fin(ek)=init(ek+1), 1kn-1 在不引起混亂的情況下，有時也將有向路(e1, , e

3、n)寫成(v1, , vn, vn+1)，其中 vi=init(ei) (i=1, , n)，vn+1=fin(en)。,定義4.3.4,有向圖的有向路(e1,en)稱為簡單的，如果1）init(e1), , init(en)互不相同，2）fin(e1), , fin(en)互不相同。,定義4.3.5,設(shè)G=(P, A)是有向圖，vP(G)，從點v到自身的簡單有向路(長度可以為1或2)稱為有向回路。,(e2),(e3, e4, e2),(e3, e5, e6, e10, e2),(e3, e5, e6, e7, e1)是從C到B的4個有向路。這4條有向路只有第一條，第四條是簡單的；,(e3,

4、e4),(e3, e5, e6, e10),(e8),(e9)是4條有向回路；有向圖G中，從B到其它任意點都沒有有向路。,例：,定義,定義4.3.6 設(shè)G=(P，A)是有向圖，對G中任意兩點v，v (vv)，如果都有從v到v的有向路，則稱G是強連通的。 定義4.3.7 設(shè)G=(P，A)是有向圖，rP(G)。稱r為G的根，如果對G中任一點v (vr)，都有從v到r的有向路。 顯然，強連通圖的每一點都是根，反之，每一點都是根的有向圖也必是強連通的。,漠視圖,有向圖G的漠視圖G0： (1)刪去G中自身到自身的?。?(2)G中任意兩點，若有弧，只保留一條； (3)刪去弧的方向，即得G0。 稱有向圖G是

5、連通的，如果G的漠視圖G0是連通的。 顯然，若有向圖G是強連通的，則G必有根； 若有向圖G有根，則漠視圖G0必連通。反之，不一定成立。亦即，若G0連通，則G不一定有根； 若有根，則G未必強連通。,例：,定義4.3.8,有向圖G稱為有向樹（或有根樹），如果G中有一點r，并且滿足：(1) G中每一點v(vr)都恰是一條弧e的起點。(2) r不是任一條弧的起點。 (3) r是根。 從定義中我們可推出有向樹有如下性質(zhì)： 1) 每一點v(vr)到r恰有一條有向路； 2) 沒有有向回路； 3) 兩點間最多有一條弧。,有向樹擴展應(yīng)用案例,例：,定理4.3.1（轉(zhuǎn)化定理）,對有向樹G，若無視各弧之方向，則得一

6、樹G0；反之，若G0是樹，可選取任一點做根，并適當(dāng)指定各邊之方向，則得一有向樹G。 證明：1) 首先證第一個命題。 因有向樹有根，所以G0是連通的，以下證G0無回路。 用反證法。假設(shè)G0中有回路，設(shè)(v0, , vn) 是G0中一回路，其中v0= vn，n3。,定理4.3.1（轉(zhuǎn)化定理）,(1) 若r在此路中，不妨假設(shè)v0=r，則在G中對應(yīng)G0的邊v0v1的弧一定是從v1到v0的，又因G中除根外每一點恰發(fā)一弧，所以G0中邊v1v2必是G中從v2到v1的弧，G0中邊vk-1 vk必是G中vk到vk-1的弧，G0中邊vn-1vn必是G中vn到vn-1的弧，而vn= v0=r，矛盾。,vn = v0

7、=r,v1,v2,vk,vk-1,vn-1,定理4.3.1（轉(zhuǎn)化定理）,(2)若r不在此回路中，由有向樹定義知，v0或v1恰發(fā)一弧，不妨設(shè)G0中的邊v0v1是G中從v1到v0的弧，則v1已發(fā)弧，則G0中的邊v1v2必是G中從v2到v1的弧，則G0中邊vn-1vn是G中從vn到vn-1的弧，又vn=v0, 于是，得G中一有向回路，矛盾。,vn = v0,v1,v2,vk,vk-1,vn-1,故假設(shè)不成立，此連通圖G0無回路，故G0是樹,定理4.3.1（轉(zhuǎn)化定理）,2)再證第二個命題。 設(shè)G0是無向樹。 (1)若G0只有一個節(jié)點r，命題顯然成立。 (2)假設(shè)G0有n個節(jié)點時命題成立，則當(dāng)G0有n+

8、1個節(jié)點時。設(shè) r是G0中的一個節(jié)點且G0中與r相鄰的所有節(jié)點是v1,，v2，vk。去掉r及其所關(guān)聯(lián)的邊，得到k個子樹（由定理4.2.1及其證明能夠知道所有必須通過邊vir與節(jié)點r相連的節(jié)點之間是相連的，否則矛盾），其中v1,，v2，vk分別在 這k個子樹中。,定理4.3.1（轉(zhuǎn)化定理）,依歸納假設(shè)，我們可以把這k個分支化成以v1,，v2，vk為根的k棵有向樹，于是規(guī)定r所關(guān)聯(lián)的邊是到r的，則得到以r為根的有向樹。,定理4.3.1（轉(zhuǎn)化定理證法二）,若v=v1且v1=v，則(v,v,v2, ,r)， (v,v2,r)是兩條從v到r的簡單路，由于v2 v，所以這是兩條不同的從v到r的簡單路。矛盾

9、。 故由上面證明知，必有v=v1，或者v1=v，二者恰居其一。若v=v1，則按規(guī)定，邊vv改成從v到v的?。蝗魐1=v，則按規(guī)定，邊vv改成從v到v的弧。故按上述規(guī)定，樹G0中任一邊都能改成一個有確定方向的弧，即，將G0改成一個有向圖G。,定理4.3.1（轉(zhuǎn)化定理）,(2) 往證：G是以r為根的有向樹。 每一點v (vr)恰是一弧的起點； 任取G中一點v，且vr。由于在G0中存在從v到r的簡單路，故由上面的規(guī)定，在G中，v必是某條弧的起點。若v是兩條弧的起點，設(shè)這兩條弧的終點分別為v1，v1，且v1 v1。于是，按著上面規(guī)定，在G0中，從v到r有兩條簡單路：(v,v1,r)， (v,v1,r)

10、。矛盾。故點v恰是一條弧的起點。,定理4.3.1（轉(zhuǎn)化定理）, r不是任意一條弧的起點； 由規(guī)定知，此結(jié)論顯然成立。 r是根。 對G中任意一點v (vr) ，在G0中恰有一條從v到r的簡單路。按規(guī)定此簡單路上諸邊的方向都指向r，故在G中，這是一條從v到r的有向路。 綜上所述，G是一個有向樹。,4.3.2 Euler路 Euler圖,Konigsberg Seven Bridges Problem,4.3.2 Euler路 Euler圖,定義4.3.9 設(shè)G是有向圖，G中一條Euler路，就是一條有向路(e1, , en)，其中fin(en)=init(e1)，而且G中每條弧在此有向路中恰出現(xiàn)一

11、次。,Euler路是一有向圖中周游諸弧的路線。一個有向圖，如果存在著Euler路，就稱為Euler圖。,4.3.2 Euler路 Euler圖,定義4.3.10 設(shè)G是有向圖。G中點v說是孤立的，如果v的輸入和輸出次數(shù)全為0；G說是平衡的，如果G中每點v，都有有限的輸入次數(shù)和輸出次數(shù)，而且輸入次數(shù)和輸出次數(shù)相等。 于是，一有限平衡有向圖，其弧數(shù)有限。顯然，一有向圖若存在Euler路，則必平衡。因為Euler路每經(jīng)過一點一次，該點就得到輸入次數(shù)和輸出次數(shù)各一次。這樣，若一點共被經(jīng)過k次（k=0時是孤立的），則該點在這有向圖中的輸入次數(shù)和輸出次數(shù)就都是k。由此可見，Euler圖中每個點所觸及的弧必

12、為偶數(shù)條（輸入輸出各半）。,例,下圖是一有限平衡有向圖，而（e00, e01, e12, e22, e21, e10, e01, e12, e20）是其中的一條Euler路。,一個Euler圖G，如果沒有孤立點，則必強連通。事實上，這時G的全部點皆出現(xiàn)在一條有向路(e1,e2,em)上，即出現(xiàn)在Euler路上。其中，init(e1)=fin(em)。沿著這條路線走兩圈，總能夠先到達(dá)任一給定的頂點v，然后再到達(dá)另一個任給的頂點v。即對任意的v、v，都存在從v到v的有向路。 Euler路實際上是一條封閉的一筆畫路線。,定理4.3.2,設(shè)G是無孤立點的有限有向圖。于是，G有Euler路當(dāng)且僅當(dāng)G是平

13、衡的，并且強連通。 證明：必要性顯然。 充分性 由于G沒有孤立點，且平衡，所以G的任一點至少發(fā)出一條弧。于是G中存在至少一條有向路，并且在該有向路中沒有弧被重復(fù)使用。令 L=（e1, e2, , em） 是如此有向路中最長者。往證：L就是一條Euler路。,定理4.3.2,1) 證明 init(e1)=fin (em) 設(shè)v=fin (em)，設(shè)v的輸出次數(shù)為k (0km)，則v的輸入次數(shù)也為k 。 (1) 證明由v發(fā)出的k條弧必然全部出現(xiàn)在L中。 反證法，若e不在L中，且init(e)=v，則(e1，em，e)就是一條比L更長的由無重復(fù)弧構(gòu)成的有向路，矛盾。,定理4.3.2,(2) 證明由v

14、發(fā)出的k條弧中，必有e1，即證： init(e1)=v。 反證法，若從v發(fā)出的k條弧中無e1，則設(shè)這k條弧是ei1,ei2,eik，其中2ijm，因為ei1,ei2,eik從v發(fā)出且都在有向路L中, 則必有ei1-1,ei2-1,eik-1發(fā)到v，且1ij-1m-1，即至少有k條弧發(fā)到v，這k條弧中不包括em，因em也發(fā)到v，于是至少有k+1條弧發(fā)到v，即v的輸入次數(shù)至少是k+1，而輸出次數(shù)是k，矛盾。 (3) 類似地可證得：G中發(fā)到v的k條弧也都出現(xiàn)在L中，并且這k條弧中必有em。,2)最后證明：G的每條弧恰在L中出現(xiàn)一次。 因為已知L中的弧無重復(fù)，所以只需證：G的每條弧都在L中出現(xiàn)即可。

15、對于L，若頂點v在L中，則用1)中的方法可以證明，從v出發(fā)的所有弧都在L中。 任取eG，設(shè)u=init(e)，任取L中一點v，因為G強連通，v，u間有有向路(e1, e2, , ei)且init(e1)=v，fin(ei)=u，因v在L中，e1是由v發(fā)出的弧，所以e1在L中，因此fin(e1)= init(e2)=v1在L中，所以e2在L中，同理，ei的終點u在L中，所以e在L中。由e的任意性知，G中弧均出現(xiàn)在L中。 綜上，L是一條Euler路。,推論,設(shè)G是無孤立點的有限有向圖，于是，G有Euler路當(dāng)且僅當(dāng)G平衡，并且將G漠視為圖G0時是連通的,定理4.3.3,設(shè)G是無孤立點的有限有向圖，

16、并且G有一條Euler路(e1 , , em)。令r=fin(em)=init(e1)，對每個點vr，令ev=ei，其中i=maxj | init(ej)=v。于是，G的全部點和全部弧ev | vr作成的有向圖G，是一個以r為根的有向樹。,(e00, e01, e12, e22, e21, e10, e01, e12, e20)是其中的一條Euler路。,所以，用點v0, v1, v2,以及弧e12, e20作成以r=v0為根的有向樹,證明：,由ev的定義知： (1) 對每個點vr，恰有一弧ev發(fā)出， (2) r不發(fā)出任何弧。 下面我們證明： (3) r是根。 先證：有向圖G中無有向回路。 若

17、不然，設(shè)有一個有向回路 (,ev,ev,)。其中fin(ev)=init(ev)=v。令ev=ej，ev=ek。因為弧ej發(fā)到點v。從而ej+1是由v發(fā)出的弧，但ek是由v發(fā)出的弧中下標(biāo)最大者，所以jk。,證明：,而此有向回路又可寫成： （ev, , ev） 與上面同樣的推理，可得：kj 。矛盾。 再證：對G中任一點v，在G中，有一條從v到r的有向路。 在G中，從v出發(fā)可以這樣走下去： v fin(ev) fin(e(fin(ev) 顯然，此有向路上的點沒有重復(fù)(否則，將出現(xiàn)有向回路)，由于G有限，故最后必然停止在不發(fā)出弧的點r上，故G是一個有向樹。,定理4.3.4,設(shè)G是有限平衡有向圖，G是

18、G的有向支撐樹，設(shè)G的根為r，G中點v(r)發(fā)出的弧為ev。設(shè)e1是r在G中發(fā)出的任一條弧，如果從e1開始任一條有向路：L=(e1, e2, , em) 滿足：(1)ej ek，當(dāng)jk時。 (2)ej =ev當(dāng)且僅當(dāng)init(ej)=v并且G中由v發(fā)出的弧都出現(xiàn)在(e1, , ej)中。 (3)L終止在em當(dāng)且僅當(dāng)G中從em的終點發(fā)出的弧都已經(jīng)在L中出現(xiàn)。 則有向路L是一條Euler路。,證明：,先證：fin(em)=init(e1)=r。 由條件(3)知，由fin(em)發(fā)出的弧，都在L中。 仿照定理4.3.2的證明，不難得到結(jié)論：fin(em)發(fā) 出的弧中，有一條是e1，即fin(em)=

19、init(e1)。 再證：G中每條弧恰在L中出現(xiàn)一次。 由條件(1)知，L中的弧無重復(fù)，所以只需證：G中每條弧都出現(xiàn)在L中。 若不然，設(shè)G中弧e不在L中，令fin(e)=v，由G和 L的平衡性知，G中有一條由v發(fā)出的弧e不在L 中，由于r發(fā)出的弧都在L中，故vr，由條件(2)知，ev不在L中。,證明：,同理，若fin(ev)r，efin(ev)不在L中， 于是，得一有向路：L=(e,ev,efin(ev),)， 并且L中的弧不在L中，L中的弧都是G的弧 (除e以外)，L不能無限延長，最終必然沿著G 的一條有向路到達(dá)r，于是，根據(jù)上面的推理， 有一條從r發(fā)出的弧不在L中，與條件(3)矛盾。 所以

20、G中弧均出現(xiàn)在L中。 綜上，L是一條Euler路。,例,(e12,e20,e00,e01,e10,e01,e12,e22,e21) (e12,e20,e00,e01,e12,e22,e21,e10,e01) (e12,e20,e01,e10,e00,e01,e12,e22,e21) (e12,e20,e01,e12,e22,e21,e10,e00,e01) (e12,e22,e20,e00,e01,e10,e01,e12,e21) (e12,e22,e20,e00,e01,e12,e21,e10,e01) (e12,e22,e20,e01,e10,e00,e01,e12,e21) (e12,e

21、22,e20,e01,e12,e21,e10,e00,e01),有向圖G，命G是G中由頂點v0,v1,v2和e01,e21組成的有向支撐樹(r=v1)。從弧e12出發(fā)，可按定理4.3.4的形成規(guī)則得出Euler路。,定義4.3.11 容許有平行邊和反身邊的圖G=(P, L)稱為無向圖，其中P為(節(jié))點集，L稱為線集（包括平行邊和反身邊）。,4.3.3無向圖 無向圖中的Euler路,定義4.3.12,設(shè)G=(P, L)為無向圖，lG。如果W(G-l) W(G)，則稱l為G的斷線。 對于斷線，下述結(jié)論是明顯的。 (1) l是G的斷線的充要條件是l不在G的回路上。 (2) 設(shè)P=S1S2，S1S2=

22、，若T=l | lG, x S1, y S2, x, y為l的端點僅有一個元素l，則l是G的斷線。 (3) 設(shè)G=(S, L)是無向圖G=(P, L)的子圖，若l是G的斷線，且lL，則l是G的斷線。 (4) 若有限無向圖G的的每點的度都是偶數(shù)，則G中無斷線。,定義4.3.12,在無向圖G中討論Euler路問題，是考慮能否對G中的線加上適當(dāng)?shù)姆较?，使之?gòu)成的有向圖為Euler圖。即若無向圖G中存在無重復(fù)線的路L=(l1, , lm)，滿足G中所有線都在L中，且l1的起點與lm的終點相同，則稱無向圖G為Euler圖。反之，若L=(l1, , lm)是無向圖G的Euler路，則沿著路L的走向?qū)Ω骶€li加方向，得到有向Euler圖。,定理4.3.5,設(shè)G有限無向圖。則G有Euler路當(dāng)且僅當(dāng)G中每點的度是偶數(shù)，并且漠視為圖后是連通的。 仿照定理4.3.2 及其推論可證得。,Konigsberg城七橋問題,推論,漠視圖為連通圖的無向圖G，有一條點u到點v(uv)的路經(jīng)過所有線恰好一次，當(dāng)且僅當(dāng)G中僅有u和v的度數(shù)為奇數(shù)。 證明：充分性； 在u與v之間再加一線uv連接起來，得到無向圖G， 則G中每點的度是偶數(shù)，并且漠視為圖后是連通的。于是由定理4.3.5知G為Euler圖。從而有Euler路L=(l