離散數(shù)學圖.

1、第第7章章 圖圖第第1節(jié)節(jié)圖的基本概念圖的基本概念第第2節(jié)節(jié)子圖與圖的運算子圖與圖的運算第第3節(jié)節(jié)路徑、回路和連通性路徑、回路和連通性第第4節(jié)節(jié)圖的矩陣表示圖的矩陣表示第第5節(jié)節(jié)歐拉圖和哈密頓圖歐拉圖和哈密頓圖第第6節(jié)節(jié)平面圖與歐拉公式平面圖與歐拉公式第第7節(jié)節(jié)二部圖與匹配二部圖與匹配第第8節(jié)節(jié)樹樹第第9節(jié)節(jié)根樹及其應用根樹及其應用第第1節(jié)節(jié) 圖的基本概念圖的基本概念1、圖的定義圖的定義2、無向圖、有向圖、混合圖、無向圖、有向圖、混合圖3、鄰接結點、鄰接邊、鄰接結點、鄰接邊4、自環(huán)、平行邊、簡單圖、自環(huán)、平行邊、簡單圖5、度（入度、出度）、度（入度、出度）6、奇結點、偶結點、奇結點、偶結點7、

2、孤立結點、端點（懸掛點）、懸掛邊、孤立結點、端點（懸掛點）、懸掛邊8、零圖、平凡圖、零圖、平凡圖、d度正則圖、完全圖度正則圖、完全圖9、圖同構、圖同構10、判斷兩個圖同構的必要條件、判斷兩個圖同構的必要條件1、圖的定義圖的定義圖圖G是一個三元組是一個三元組: GV(G), E(G),非空結點集合非空結點集合邊的集合邊的集合從從E(G)到結點無到結點無序偶（有序偶）序偶（有序偶）集合上的集合上的函數(shù)函數(shù)有向邊、無向邊有向邊、無向邊邊的曲、直、長、短以及結點的位置是無關緊要的邊的曲、直、長、短以及結點的位置是無關緊要的G(e i)=(vi,vj)結點的無序偶結點的無序偶無向邊無向邊用連接用連接vi

3、和和vj的無向線段表示的無向線段表示G(e i)=結點的有序偶結點的有序偶有向邊有向邊用連接用連接vi和和vj的有向線段表示的有向線段表示vi為邊為邊ei的起點的起點vj為邊為邊ei的終點的終點vivjvivje ie i圖的舉例圖的舉例G= V(G),E(G), G= V(G)=a,b,c,d V(G)=a,b,c,d E(G)=E(G)=e1 , , e2, , e3 , , e4 , , e5 , , e6 G G( (e1)=(a,b)=(a,b)，G G ( (e2)=(a,c) )=(a,c) G G ( (e3)=(b,d)=(b,d) ) G G ( (e4)=(b,c) )=

4、(b,c) G G ( (e5)=(d,c) )=(d,c) ，G G ( (e6)=(a,d)=(a,d)請畫出對應的無向圖。abdce1e2e3e4e5e6abdce1e2e3e4e5e62、無向圖、有向圖、混合圖、無向圖、有向圖、混合圖（1）有向圖有向圖：若圖：若圖G中所有的邊都是有向邊。中所有的邊都是有向邊。（2）無向圖無向圖：若圖：若圖G中所有的邊都是無向邊。中所有的邊都是無向邊。（3）混合圖混合圖：若圖：若圖G中一些邊是有向邊，另一些中一些邊是有向邊，另一些邊是無向邊。邊是無向邊。只討論有向圖和無向圖只討論有向圖和無向圖3、鄰接結點、鄰接邊、鄰接結點、鄰接邊關聯(lián)同一個結點的兩條邊關

5、聯(lián)同一個結點的兩條邊鄰接結點鄰接結點: 由一條邊相連接的兩個結點由一條邊相連接的兩個結點vivje ivi和和 vj鄰接鄰接鄰接邊鄰接邊:vivje iei和和 ej鄰接鄰接vke j鄰接結點、鄰接邊舉例鄰接結點、鄰接邊舉例a a、b b、c c、d d四個結點中的任意兩個結點四個結點中的任意兩個結點都是鄰接結點；都是鄰接結點； e e1 1和和e e5 5不鄰接；不鄰接； e e4 4和和e e6 6不鄰接；不鄰接； e e2 2和和e e3 3不鄰接。不鄰接。4、自環(huán)、平行邊、簡單圖、自環(huán)、平行邊、簡單圖圖圖G=（1）自環(huán)）自環(huán):關聯(lián)于同一個結點的邊關聯(lián)于同一個結點的邊（2）平行邊）平行邊

6、: 關聯(lián)于同一對結點的兩條邊關聯(lián)于同一對結點的兩條邊（3）簡單圖）簡單圖: 無平行邊和自環(huán)的圖無平行邊和自環(huán)的圖平行邊舉例平行邊舉例在有向圖中，如果邊在有向圖中，如果邊e e1 1和和e e2 2關聯(lián)于同一關聯(lián)于同一對結點，但方向相反，則它們不是平行邊。對結點，但方向相反，則它們不是平行邊。5、度（入度、出度）、度（入度、出度）圖圖G=vV(G)與結點與結點v相關聯(lián)的邊的條數(shù)相關聯(lián)的邊的條數(shù)（1）v的度的度:G是無向圖是無向圖,deg(v)（2）v的出度的出度:G是有向圖是有向圖, 以以v為起點的邊的條數(shù)為起點的邊的條數(shù)deg+(v)v的入度的入度:以以v為終點的邊的條數(shù)為終點的邊的條數(shù)deg

7、-(v)v的度的度: v的出度和入度之和的出度和入度之和deg(v)自環(huán)的度自環(huán)的度對于無向圖中的一個自環(huán)，給該結點的對于無向圖中的一個自環(huán)，給該結點的度增加度增加2；對于有向圖中的自環(huán)，給該結點對于有向圖中的自環(huán)，給該結點增加一增加一個出度和一個入度個出度和一個入度，故該結點的度也增加，故該結點的度也增加2。結點度的舉例結點度的舉例給出圖給出圖1 1各結點的度；各結點的度；給出圖給出圖2 2各結點的出度、入度、度。各結點的出度、入度、度。解答解答deg(v1)=deg(v4)=3deg(v2)=deg(v3)=2deg+(v1)=1, deg-(v1)=1, deg(v1)=2deg+(v2

8、)=1, deg-(v2)=2, deg(v2)=3deg+(v3)=2, deg-(v3)=0, deg(v3)=2deg+(v4)=2, deg-(v4)=1, deg(v4)=3deg+(v5)=0, deg-(v5)=2, deg(v5)=2(n,m)圖圖圖圖n個結點個結點m條邊條邊(n,m)圖圖定理定理mvnii2)deg(1(n,m)圖圖所有結點的度之和等于邊數(shù)的兩倍所有結點的度之和等于邊數(shù)的兩倍證明證明因為因為 ：每條邊必關聯(lián)兩個結點：每條邊必關聯(lián)兩個結點一條邊給它所關聯(lián)的兩個結點的度各增加一條邊給它所關聯(lián)的兩個結點的度各增加1為整個圖的度數(shù)增加為整個圖的度數(shù)增加2所以：結點的度

9、數(shù)總和恰好為邊數(shù)的兩倍。所以：結點的度數(shù)總和恰好為邊數(shù)的兩倍。定理驗證定理驗證m=5deg(v1)+deg(v2)+deg(v3)+deg(v4)=3+2+2+3=10=2m定理定理mvvininii)(deg)(deg11(n,m)有向圖有向圖所有結點的出度之和等于入度之和等于邊數(shù)所有結點的出度之和等于入度之和等于邊數(shù)定理驗證定理驗證m=6deg+(v1)+ deg+(v2)+ deg+(v3) +deg+(v4)+ deg+(v5)=1+1+2+2+0=mdeg-(v1)+ deg-(v2)+ deg-(v3) +deg-(v4)+ deg-(v5)=1+2+0+1+2=m6、奇結點、偶結

10、點、奇結點、偶結點偶結點：偶結點：奇結點：奇結點： 度數(shù)為奇數(shù)的結點度數(shù)為奇數(shù)的結點度數(shù)為偶數(shù)的結點度數(shù)為偶數(shù)的結點定理定理在任何圖中，必有偶數(shù)個奇結點。在任何圖中，必有偶數(shù)個奇結點。證明證明mvvjVvVviji2)(deg)(deg21)(deg2jVvvj)(deg1Vviiv圖圖G=|E|=mV1:V2:V中奇結點集合中奇結點集合V中偶結點集合中偶結點集合偶結點的度數(shù)之和偶結點的度數(shù)之和偶數(shù)偶數(shù)偶數(shù)偶數(shù)奇結點的度數(shù)之和奇結點的度數(shù)之和偶數(shù)偶數(shù)|V1|偶數(shù)偶數(shù)偶數(shù)個奇結點偶數(shù)個奇結點7、孤立結點、端點（懸掛點）、懸掛邊、孤立結點、端點（懸掛點）、懸掛邊圖圖G= vV(G)（1）孤立結點）

11、孤立結點:deg(v)=0（2）端點）端點:deg(v)=1懸掛點懸掛點（3）懸掛邊）懸掛邊: 與懸掛點關聯(lián)的邊與懸掛點關聯(lián)的邊孤立結點、懸掛點、懸掛邊舉例孤立結點、懸掛點、懸掛邊舉例V V5 5是是懸掛點；懸掛點；(v(v4 4,v,v5 5) )是是懸掛邊懸掛邊; ;V V6 6是孤立結點是孤立結點8、零圖、平凡圖、零圖、平凡圖、d度正則圖、完全度正則圖、完全圖圖G=: 簡單無向圖簡單無向圖（1）零圖）零圖: E=(n,0)圖圖（2）平凡圖）平凡圖:|V|=1 E=(1,0)圖圖（3）d度正則圖度正則圖: 每個結點的度均為每個結點的度均為d（4）完全圖：）完全圖： 任意兩點間恰有一條邊連接

12、任意兩點間恰有一條邊連接Kn舉例舉例9、圖同構、圖同構兩個圖兩個圖G=G=雙射函數(shù)雙射函數(shù)g：V V v iVg(vi)= vi (g(vi),g(vj) E（1）無向圖）無向圖:(vi, vj) E（2）有向圖）有向圖: E EG與與G同構同構解釋解釋（1）無向圖）無向圖:雙射函數(shù)雙射函數(shù)g:VV: 保持結點間的鄰接關系保持結點間的鄰接關系（2）有向圖）有向圖:雙射函數(shù)雙射函數(shù)g:VV:保持結點間的鄰接關系保持結點間的鄰接關系保持邊的方向一致保持邊的方向一致無向圖同構舉例無向圖同構舉例證明下面兩個無向圖同構。證明下面兩個無向圖同構。證明證明雙射函數(shù)雙射函數(shù)g:V V:g(vi)=vi(i=1

13、,2,3,4,5,6)(v1,v4) E(v1, v4) E(v1,v5) E(v1, v5) E(v1,v6) E(v1, v6) E(v2,v4) E(v2, v4) E(v2,v5) E(v2, v5) E(v2,v6) E(v2, v6) E(v3,v4) E(v3, v4) E(v3,v5) E(v3, v5) E(v3,v6) E(v3, v6) E有向圖同構舉例有向圖同構舉例證明下面兩個有向圖同構。證明下面兩個有向圖同構。證明證明雙射函數(shù)雙射函數(shù)g:V V:g(i)=vi (i=1,2,3,4) E E E E E E E E10、判斷兩個圖同構的必要條件、判斷兩個圖同構的必要條

14、件（1）結點數(shù)相同；）結點數(shù)相同；（2）邊數(shù)相同；）邊數(shù)相同；（3）度數(shù)相同的結點數(shù)相同度數(shù)相同的結點數(shù)相同。解釋解釋1）如果兩個圖同構，則）如果兩個圖同構，則(1)、(2)、(3)成立；成立；2）(1)、(2)、(3)成立兩個圖不一定同構；成立兩個圖不一定同構；3）如果）如果(1)、(2)、(3)不成立，則兩個圖一定不成立，則兩個圖一定不同構；不同構；定理應用舉例定理應用舉例判定以下兩個有向圖是否同構？判定以下兩個有向圖是否同構？證明證明(1)|V|=|V|=5(2)|E|=|E|=8(3)d+(1)=2結點1:結點a:d-(1)=2d(1)=4;d+(a)=2d-(a)=2d(a)=4;d

15、+(2)=1結點2:結點b:d-(2)=2d(2)=3;d+(b)=1d-(b)=2d(b)=3;d+(3)=2結點3:結點c:d-(3)=1d(3)=3;d+(c)=2d-(c)=1d(c)=3;d+(4)=1結點4:結點d:d-(4)=2d(1)=3;d+(d)=2d-(d)=1d(d)=3;d+(5)=2結點5:結點e:d-(5)=1d(5)=3;d+(e)=2d-(e)=1d(e)=3;證明（續(xù)）證明（續(xù)）雙射函數(shù)雙射函數(shù)g:V V:g(5)=eg(1)=ag(2)=bg(3)=cg(4)=d E E E E E E E E E E E E E E第第2節(jié)節(jié) 子圖與圖的運算子圖與圖的運

16、算一、子圖一、子圖二、圖的運算二、圖的運算一、子圖一、子圖1、子圖、子圖2、真子圖、真子圖3、生成子圖、生成子圖4、結點導出子圖、結點導出子圖5、邊導出子圖、邊導出子圖1、子圖、子圖兩個圖兩個圖G=G=V VE EG是是G的的子圖子圖2、真子圖、真子圖兩個圖兩個圖G=G=V VE EG是是G的的真子圖真子圖3、生成子圖、生成子圖兩個圖兩個圖G=G=V=VE EG是是G的的生成子圖生成子圖子圖的舉例子圖的舉例4 4、結點導出子圖、結點導出子圖G=V VVV為結點集合為結點集合起點和終點均在起點和終點均在V中的邊的全體為邊集合中的邊的全體為邊集合由由V導出的導出的G的子圖的子圖GVV V導出子圖導

17、出子圖GV-VG-V結點導出子圖舉例結點導出子圖舉例求求: :(1)(1)由結點集合由結點集合V V=a,b,d,e =a,b,d,e 導出的導出的G G的子圖的子圖Ga,b,d,eGa,b,d,e(2)G-a,d(2)G-a,d解答解答5 5、邊導出子圖、邊導出子圖G=E EEV=v| v V ( e)(e E v與與e關聯(lián)關聯(lián))以以V為結點集合為結點集合以以E為邊集為邊集由由E導出的子圖導出的子圖邊導出子圖舉例邊導出子圖舉例求求: :由邊集合由邊集合E=eE=e1 1,e ,e2 2,e ,e5 5,e ,e7 7 導出的導出的G G的子圖的子圖GeGe1 1,e ,e2 2,e ,e5

18、5,e ,e7 7 解答解答二、圖的運算二、圖的運算1、可運算的、可運算的2、邊不相交的、邊不相交的3、點不相交的、點不相交的4、圖的交、圖的交5、圖的并、圖的并6、圖的差、圖的差7、圖的環(huán)和、圖的環(huán)和8、相對于圖、相對于圖G的補圖的補圖9、相對于完全圖的補圖、相對于完全圖的補圖1、可運算的、可運算的G1=G2=同為無向圖或同為有向圖同為無向圖或同為有向圖對任意的對任意的e E1E2 1(e)= 2(e)G1與與G2是可運算的是可運算的2、邊不相交的、邊不相交的G1=G2=同為無向圖或同為有向圖同為無向圖或同為有向圖G1與與G2是不相交的是不相交的E1E2 = V1V2 =G1與與G2是邊不相

19、交是邊不相交E1E2 = 3、點不相交的、點不相交的G1與與G2是點不相交的是點不相交的G1=G2=同為無向圖或同為有向圖同為無向圖或同為有向圖V1V2 =可運算的舉例可運算的舉例問：問： G G1 1和和G G2 2是否是可運算的？是否是可運算的？解答解答E1E2 =e1,e2,e5 1(e1)= (a,b) 2(e1)= (a,b) 1(e2)= (a,d) 2(e2)= (a,d) 1(e5)= (b,d) 2(e5)= (b,d)G1和和G2是可運算的是可運算的4、圖的交、圖的交G1=G2=是可運算的是可運算的V1V2為結點集為結點集E1E2為邊集合為邊集合G1和和G2的交的交G1G2

20、5、圖的并、圖的并G1=G2=是可運算的是可運算的V1 V2為結點集為結點集E1 E2為邊集合為邊集合G1和和G2的并的并G1 G26、圖的差、圖的差G1=G2=是可運算的是可運算的G1與與G2的差的差:在在G1中去掉中去掉G2的邊所得到的圖的邊所得到的圖G1 - G27、圖的環(huán)和、圖的環(huán)和G1=G2=是可運算的是可運算的V1 V2為結點集為結點集E1 E2為邊集合為邊集合G1和和G2的環(huán)和的環(huán)和G1 G2圖運算的舉例圖運算的舉例與如下圖所示，求：與如下圖所示，求：G G1 1G G2 2 G G1 1G G2 2 G G1 1- -G G2 2 G G2 2- -G G1 1 ， G G1

21、1 G G2 2 。G G1 1G G2 2V V1 1V V2 2E1 1E2 2=a,b,d= e1 1,e2 2,e5 5G G1 1G G2 2V V1 1V V2 2e1 1,e2 2,e3 3 , e4 4,e5 5,e6 6 ,e7 7 , e8 8,e9 9,e1010=a,b,c,d,eE1 1E2 2 =G G1 1 - -G G2 2G G2 2 G G1 1G G1 1 G G2 2E E1 1 E E2 2 =V V1 1V V2 2=a,b,c,d,ee3 3 , e4 4,e6 6 ,e7 7 , e8 8,e9 9,e10108、相對于圖、相對于圖G的補圖的補圖

22、G=的子圖的子圖:G=:給定另一個圖給定另一個圖G=（1）E E-E（2）V是是E中的邊所關聯(lián)的結點集合中的邊所關聯(lián)的結點集合G是子圖是子圖G的相對于圖的相對于圖G的補圖的補圖解釋解釋(1)EE (2)EE E(3) V僅是僅是E中的邊所關聯(lián)的結點集合，不中的邊所關聯(lián)的結點集合，不包含別的結點包含別的結點: GG G(4) G與與G的關系不是互逆的。的關系不是互逆的。相對補圖的舉例相對補圖的舉例圖圖G和圖和圖G 如下圖所示如下圖所示:求圖求圖G 相對于圖相對于圖G的補圖。的補圖。解答解答EEE-E= (a,e),(c,e),(d,e)V a,c,d,e圖圖G 相對于圖相對于圖G的補圖為的補圖為

23、GG相對于圖相對于圖G的補圖為的補圖為G 不是不是G沒有結點沒有結點e9、相對于完全圖的補圖、相對于完全圖的補圖補圖是互逆的補圖是互逆的給定一個圖給定一個圖GG中所有結點中所有結點能使能使G成為完全圖所添加的邊成為完全圖所添加的邊圖圖G相對于完全圖的補圖相對于完全圖的補圖G的補圖的補圖G補圖舉例補圖舉例求求G G1 1和和G G2 2的補圖。的補圖。解答解答解答解答第第3節(jié)節(jié) 路徑、回路和連通性路徑、回路和連通性一、路徑一、路徑二、連通性二、連通性一、路徑一、路徑1、路徑、路徑2、可達的、不可達的、可達的、不可達的1、路徑、路徑(1)路徑路徑(2)回路回路(3)簡單路徑、基本路徑簡單路徑、基本

24、路徑(1)路徑路徑路徑是結點和邊的路徑是結點和邊的交替序列交替序列圖圖G=v0,v1vn Ve1,e2en Eei:關聯(lián)關聯(lián)vi-1和和vi序列序列v0e1v1e2envn :從從v0到到vn的路的路路徑路徑路徑的起點路徑的起點路徑的終點路徑的終點路徑的長度路徑的長度: 路徑中邊的數(shù)目路徑中邊的數(shù)目(2)回路回路起點和終點為同一個結點的路徑起點和終點為同一個結點的路徑(3)簡單路徑、基本路徑簡單路徑、基本路徑簡單路徑簡單路徑:簡單回路簡單回路:基本路徑基本路徑:基本回路基本回路:邊不重復的路徑邊不重復的路徑邊不重復的回路邊不重復的回路點不重復的路徑點不重復的路徑點不重復的回路點不重復的回路路徑

25、舉例路徑舉例(1)AaAcBgChF:(2)AbDdEeBfChF:(3)AbDdEeBcA:從從A到到F的路徑的路徑長度為長度為4簡單路徑簡單路徑不是基本路徑不是基本路徑從從A到到F的路徑的路徑長度為長度為5簡單路徑簡單路徑 基本路徑基本路徑從從A到到A的回路的回路長度為長度為4簡單回路簡單回路 基本回路基本回路路徑舉例路徑舉例v1e2v2e3v3e4v4v4e1v1e2v2e3v3e4v4e1v1簡單路徑簡單路徑基本路徑基本路徑不是基本路徑不是基本路徑不是簡單路徑不是簡單路徑定理定理尋找基本路徑的方法尋找基本路徑的方法：v和和v是圖是圖G中的結點中的結點存在從存在從v到到v的路徑的路徑存在

26、從存在從v到到v的基本路徑的基本路徑從路徑中去掉所有的回路從路徑中去掉所有的回路證明證明從從v到到v存在路徑存在路徑P vv : v0e1v1e2elvlvv若若Pvv不是基本路徑不是基本路徑結點結點vi在該路徑中不止一次出現(xiàn)在該路徑中不止一次出現(xiàn)v0e1v1e2eivi ei+1 ejvjej+1elvlvi=vj在該路徑中去掉從在該路徑中去掉從vi到到vj的邊的邊v0e1v1e2eiviej+1elvl從從v0到到vl的路徑的路徑如此反復去掉所有的回路如此反復去掉所有的回路從從v0到到vl的基本路徑的基本路徑定理應用舉例定理應用舉例(1)ae2be10de9ae2be4c:(2)ae1ae

27、2be4c:求從求從a到到c的基本路徑的基本路徑是從是從a到到c的一條路徑的一條路徑,是從是從a到到c的一條路徑的一條路徑,求從求從a到到c的基本路徑的基本路徑解答解答(1)ae2be10de9ae2be4c:不是基本路徑不是基本路徑去掉回路去掉回路ae2be10de9aae2be4c基本路徑基本路徑(2)ae1ae2be4c:不是基本路徑不是基本路徑去掉回路去掉回路ae1aae2be4c基本路徑基本路徑定理定理n階圖中的基本路徑的長度小于階圖中的基本路徑的長度小于n。證明證明基本路徑基本路徑:點不重復的路徑點不重復的路徑在一個基本路徑中有在一個基本路徑中有l(wèi)個不同的結點個不同的結點 v0,v

28、1,vl-1有有l(wèi)-1條邊條邊:e1,e2,el-1v0e1v1e2el-1vl-1基本路徑基本路徑n階圖階圖: 有有n個不同的結點個不同的結點最多有最多有n-1條邊出現(xiàn)在基本路徑上條邊出現(xiàn)在基本路徑上n階圖中的基本路徑的長度小于階圖中的基本路徑的長度小于n2、可達的、不可達的、可達的、不可達的v1,v2:圖圖G中的結點中的結點存在從存在從v1到到v2的路徑的路徑從從v1到到v2 是可達的是可達的否則否則:從從v1到到v2不可達不可達v1可達可達v2 在無向圖中在無向圖中:在有向圖中在有向圖中:v2可達可達v1 V2不一定不一定可達可達v1 二、連通性二、連通性1、連通圖、連通圖2、基礎圖、基

29、礎圖3、強連通、單向連通、弱連通、強連通、單向連通、弱連通4、極大子圖、極大子圖5、分支、分支1、連通圖、連通圖G:無向圖無向圖任意兩個結點都相互可達任意兩個結點都相互可達連通圖連通圖否則否則:G是非連通圖是非連通圖2、基礎圖、基礎圖把每條把每條有向邊改為無向邊有向邊改為無向邊而得到的無向圖而得到的無向圖有向圖的基礎圖有向圖的基礎圖3、強連通、單向連通、弱連通、強連通、單向連通、弱連通G:有向圖有向圖(1)強連通圖強連通圖: 任意兩結點均互相可達任意兩結點均互相可達(2)單向（側(cè)）連通圖單向（側(cè)）連通圖:任意兩結點必有一結點可達另一個結點任意兩結點必有一結點可達另一個結點(3)弱連通圖弱連通圖

30、: G的基礎圖是連通的的基礎圖是連通的連通性舉例連通性舉例判斷圖判斷圖G G1 1,G,G2 2,G,G3 3是強連通圖、單向連通是強連通圖、單向連通圖還是弱連通圖？圖還是弱連通圖？解答解答v2不可達不可達v3v3也不可達也不可達v2G1不是單向連通圖不是單向連通圖G1的基礎圖是連通圖的基礎圖是連通圖 G1是弱連通圖是弱連通圖解答解答v1可達可達v3v3不可達不可達v1G2不是強連通圖不是強連通圖v2可達可達v3v2可達可達v1G2是單向連通圖是單向連通圖解答解答v1可達可達v2v2可達可達v1v1可達可達v3v3可達可達v1v2可達可達v3v3可達可達v2G3是強連通圖是強連通圖4、極大子圖

31、、極大子圖G:G的子圖的子圖G具有連通性具有連通性對于對于G的任意的具有連通性的子圖的任意的具有連通性的子圖GG GG=GG是是G的極大的極大 連通連通 子圖子圖強連通性強連通性強連通性強連通性強連通強連通單向連通性單向連通性單向連通性單向連通性單向連通單向連通弱連通性弱連通性弱連通性弱連通性弱連通弱連通5、分支、分支無向圖無向圖G的極大連通子圖的極大連通子圖 G的分支（分圖）的分支（分圖）:G的強分支（強分圖）的強分支（強分圖）:有向圖有向圖G的極大強連通子圖的極大強連通子圖G的單向分支（單向分圖）的單向分支（單向分圖）:有向圖有向圖G的極大單向連通子圖的極大單向連通子圖G的弱分支（弱分圖）

32、的弱分支（弱分圖）:有向圖有向圖G的極大弱連通子圖的極大弱連通子圖定理定理連通無向圖恰有一個分支連通無向圖恰有一個分支非連通無向圖有一個以上的分支非連通無向圖有一個以上的分支舉例舉例圖圖G G是一個連通無向圖是一個連通無向圖其只有一個極大連通子圖，就是其本身其只有一個極大連通子圖，就是其本身G G。舉例舉例圖圖G G是一個非連通無向圖是一個非連通無向圖其有兩個極大連通子圖其有兩個極大連通子圖G1G1和和G2G2。定理定理強強 連連 通有向圖恰有一個通有向圖恰有一個 強強 分支分支非非 強強 連連 通通 有向圖有一個以上的有向圖有一個以上的 強強 分支分支單向連通單向連通單向分支單向分支單向連通

33、單向連通單向分支單向分支弱連通弱連通弱連通弱連通弱分支弱分支弱分支弱分支定理定理G=:簡單有向圖簡單有向圖每一個結點都每一個結點都恰恰處于一個強分支中處于一個強分支中分支舉例分支舉例求求G G1 1、G G2 2的強分支、單向分支、弱分支。的強分支、單向分支、弱分支。解答解答解答解答定理定理無向圖無向圖G（連通或不連通）恰有兩個奇結點（連通或不連通）恰有兩個奇結點必有連接此兩結點的路徑必有連接此兩結點的路徑證明證明設設G中的兩個奇結點是中的兩個奇結點是v1和和v2(1)若若G是連通圖，則是連通圖，則v1和和v2之間必有路徑；之間必有路徑；(2)若若G是非連通圖，則是非連通圖，則G至少有兩個以上

34、的至少有兩個以上的分支分支因為，在任何一個圖中因為，在任何一個圖中必有偶數(shù)個奇結點必有偶數(shù)個奇結點所以：所以：v1和和v2必處于同一個分支中，即：必處于同一個分支中，即：V1和和v2之間必有路徑。之間必有路徑。第第4節(jié)節(jié) 圖的矩陣表示圖的矩陣表示一、鄰接矩陣一、鄰接矩陣二、可達性矩陣二、可達性矩陣三、完全關聯(lián)矩陣三、完全關聯(lián)矩陣一、鄰接矩陣一、鄰接矩陣1、簡單無向圖的鄰接矩陣、簡單無向圖的鄰接矩陣2、簡單有向圖的鄰接矩陣、簡單有向圖的鄰接矩陣3、矩陣、矩陣AAT4、矩陣、矩陣ATA5、矩陣、矩陣Am1、簡單無向圖的鄰接矩陣、簡單無向圖的鄰接矩陣G:簡單無向圖簡單無向圖n階方陣階方陣 A=(ai

35、j)nnV=v1,v2,vn鄰接矩陣鄰接矩陣:aij=(vi,vj) E10否則否則鄰接矩陣舉例鄰接矩陣舉例寫出簡單無向圖寫出簡單無向圖G G對應的鄰接矩陣對應的鄰接矩陣A A。A=abcdea b c de1111 111111111100000000000簡單無向圖鄰接矩陣的特點簡單無向圖鄰接矩陣的特點(1)主對角線均為主對角線均為0的的對稱陣；對稱陣；(2)每一行（列）中每一行（列）中“1”的個數(shù)的個數(shù)是該行所對應的結是該行所對應的結點的點的度度；(3)所有元素所有元素均為均為“0”的鄰接矩陣對應的是的鄰接矩陣對應的是零圖零圖;(4)除主對角線外所有元素均為除主對角線外所有元素均為“1”

36、的鄰接矩陣對的鄰接矩陣對應的是應的是完全圖完全圖。2、簡單有向圖的鄰接矩陣、簡單有向圖的鄰接矩陣G:簡單有向圖簡單有向圖n階方陣階方陣 A=(aij)nnV=v1,v2,vn鄰接矩陣鄰接矩陣:aij= E10否則否則鄰接矩陣舉例鄰接矩陣舉例寫出簡單有向圖寫出簡單有向圖G G對應的鄰接矩陣對應的鄰接矩陣A A。A=v1v2v3v4v1v2v3v4010 1111010100000簡單有向圖鄰接矩陣的特點簡單有向圖鄰接矩陣的特點(1)不一定是對稱陣；不一定是對稱陣；(2)每一行中每一行中“1”的個數(shù)的個數(shù)是該行所對應的結點的是該行所對應的結點的出度出度；(3)每一列中每一列中“1”的個數(shù)的個數(shù)是該

37、列所對應的結點的是該列所對應的結點的入度入度；(4)第第i行中行中“1”的個數(shù)與第的個數(shù)與第i列中列中“1”的個數(shù)之和，恰的個數(shù)之和，恰為記點為記點vi的度。的度。3、矩陣、矩陣AATA:有向圖有向圖G的鄰接矩陣的鄰接矩陣AT:A的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣A=(aij)nnB= AAT=(bij)nnbij =A=vivjai1aija1jainanjAT=a1iajiaj1aniajnai1 aj1+ ai2 aj2+ + ain ajn解釋解釋aik1ajk1aikajk1為為bij的求和中的值增加的求和中的值增加1aik1ajk1 E Evkvjvi由由vi,vj引出的邊共同地終止于結點引出的

38、邊共同地終止于結點vk1n矩陣矩陣AAT的特點的特點（1）矩陣）矩陣AAT中的第中的第i行第行第j列的記入值列的記入值bij，等于從等于從vi和和vj引出的邊能引出的邊能共同地終止于不同共同地終止于不同結點的數(shù)目結點的數(shù)目；（2）對角線上的記入值即為結點）對角線上的記入值即為結點vi的的出度出度。矩陣矩陣AAAAT T的舉例的舉例已知簡單有向圖已知簡單有向圖G G的鄰接矩陣的鄰接矩陣A A，求：求：矩陣矩陣AAAAT T，并指出各記入值的含義。，并指出各記入值的含義。解答解答AAT=v1v2v3v4v1v2v3v4112 0200012011103b11=1:v1的出度為的出度為1b22=2:

39、v2的出度為的出度為2b33=3:v3的出度為的出度為3b44=1:v4的出度為的出度為1b12=1:從從v1和和v2引出的邊引出的邊能共同地終止于能共同地終止于1個個結點結點v4b23=2:從從v2和和v3引出的邊引出的邊能共同地終止于能共同地終止于2個個結點結點v1,v44、矩陣、矩陣ATAnnijTbAAB)(ijbA:有向圖有向圖G的鄰接矩陣的鄰接矩陣AT:A的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣A=(aij)nn=a1i a1j+ a2i a2j+ + ani anjviAT=a1iajiaj1aniajnA=vjai1aija1jainanj矩陣矩陣ATA的特點的特點（1）矩陣）矩陣ATA中的第中的

40、第i行第行第j列的記入值，等列的記入值，等于從圖于從圖G中其它結點引出的邊中其它結點引出的邊共同地終止共同地終止于于vi和和vj的結點的數(shù)目的結點的數(shù)目；（2）矩陣）矩陣ATA中對角線上的記入值即為結中對角線上的記入值即為結點點vi的的入度入度。矩陣矩陣A AT TA A的舉例的舉例已知簡單有向圖已知簡單有向圖G G的鄰接矩陣的鄰接矩陣A A，求：求：矩陣矩陣A AT TA A，并指出各記入值的含義。，并指出各記入值的含義。解答解答11b22b33b44b12b14bATA=v1v2v3v4v1v2v3v4110 1000101202321=2:v1的入度為的入度為2=1: v2的入度為的入度

41、為1=1: v3的入度為的入度為1=3: v4的入度為的入度為3=1:有一個結點引出的邊能共同地終止于從有一個結點引出的邊能共同地終止于從v1和和v2v3=2:有兩個結點引出的邊能共同地終止于從有兩個結點引出的邊能共同地終止于從v1和和v4v2,v35、矩陣、矩陣A2A:有向圖有向圖G的鄰接矩陣的鄰接矩陣A2=AA=(aij)nn (aij)nn= (aij(2)nnA=vivjai1aija1jainanj=ai1 a1j+ ai2 a2j+ + ain anj解釋：解釋：有一條從有一條從vi經(jīng)經(jīng)vk終止于終止于vj的長度為的長度為2的路徑的路徑aik1akj1aikakj1vivjvk矩陣

42、矩陣Am的特點的特點aij(2):從從vi到到vj長度為長度為2的路徑數(shù)目的路徑數(shù)目aii(2):起始于起始于vi又終止于又終止于vi的長度為的長度為2的回路的數(shù)目的回路的數(shù)目aij(m): 從從vi到到vj長度為長度為m的路徑數(shù)目的路徑數(shù)目aii(m):起始于起始于vi又終止于又終止于vi的長度為的長度為m的回路的數(shù)目的回路的數(shù)目矩陣矩陣A Amm的舉例的舉例求圖求圖G G的的A A2 2和和A A3 3, ,并說明其中個數(shù)據(jù)的含義。并說明其中個數(shù)據(jù)的含義。解答解答A2=v1v2v3v4v1v2v3v4001 1020110010111a13(2)=1: 從從v1到到v3長度為長度為2的路徑

43、有的路徑有1條條v1v4v3a23(2)=1: 從從v2到到v3長度為長度為2的路徑有的路徑有1條條v2v4v3a33(2)=1: 從從v3到到v3長度為長度為2的回路有的回路有1條條v3v4v3a44(2)=1: 從從v4到到v4長度為長度為2的回路有的回路有1條條v4v3v4解答解答A3=v1v2v3v4111 1121011101212a12(3)=1: 從從v1到到v2長度為長度為3的路徑有的路徑有1條條v1v4v3a23(3)=1: 從從v2到到v3長度為長度為3的路徑有的路徑有1條條v2v4v3a22(3)=1: 從從v2到到v2長度為長度為3的回路有的回路有1條條v2v4v2a1

44、1(3)=1: 從從v1到到v1長度為長度為3的回路有的回路有1條條v4v3v1v2v1v1v1v1v2v3v4定理定理G=: 簡單有向圖簡單有向圖V=v1,v2,vnA:G的鄰接矩陣的鄰接矩陣矩陣矩陣Am中的元素中的元素aij(m):從從vi到到vj長度為長度為m的路徑數(shù)目的路徑數(shù)目證明證明對對m進行歸納證明：進行歸納證明：(1)當當m=1時，時，Am=A，根據(jù)鄰接矩陣的定，根據(jù)鄰接矩陣的定義顯然成立；義顯然成立；(2)假設假設m=k時成立；時成立；(3)證明證明m=k+1時也成立時也成立證明（續(xù)）證明（續(xù)）aij(k)從從vi到到vj長度為長度為k的路徑數(shù)目的路徑數(shù)目Ak+1= AkA=a

45、i1(k)a1j+ ai2(k)a2j+ aih(k)ahj+ + ain(k)anj aih(k)從從vi到到vh長度為長度為k的路徑數(shù)目的路徑數(shù)目ahj從從vh到到vj長度為長度為1的路徑數(shù)目的路徑數(shù)目aih(k)ahj從從vi經(jīng)經(jīng)vh到到vj長度為長度為k+1的路徑數(shù)目的路徑數(shù)目對所有對所有h求和求和:aij(k+1)從從vi到到vj長度為長度為k+1的路徑總數(shù)的路徑總數(shù) m=k+1時成立時成立舉例舉例求圖求圖G G的的A A2 2、A A3 3和和A A4 4 , ,并說明其中個數(shù)并說明其中個數(shù)據(jù)的含義。據(jù)的含義。解答解答a13(2)=1: 從從v1到到v3長度為長度為2的路徑有的路徑

46、有1條條v1 v2 v3a31(2)=1: 從從v3到到v1長度為長度為2的路徑有的路徑有1條條v3 v2 v1a33(2)=1: 從從v3到到v3長度為長度為2的路徑有的路徑有1條條v3 v2 v3a44(2)=1: 從從v4到到v4長度為長度為2的路徑有的路徑有1條條v4 v5 v4解答解答a12(3)=2: 從從v1到到v2長度為長度為3的路徑有的路徑有2條條v1 v2 v3 v2v1 v2 v1 v2a23(3)=2: 從從v2到到v3長度為長度為3的路徑有的路徑有2條條v2 v1 v2 v3v2 v3 v2 v3a45(3)=1:從從v4到到v5長度為長度為3的路徑有的路徑有1條條v

47、4 v5 v4 v5主對角線元素均為主對角線元素均為0不存在長度為不存在長度為3的回路的回路解答解答a13(4)=2: 從從v1到到v3長度為長度為4的路徑有的路徑有2條條a11(4)=2: 從從v1到到v1長度為長度為4的回路有的回路有2條條v1 v2 v3 v2 v3v1 v2 v1 v2 v3v1 v2 v3 v2 v1v1 v2 v3 v2 v1二、可達性矩陣二、可達性矩陣1、可達性矩陣可達性矩陣P2、求可達性矩陣、求可達性矩陣P的方法的方法1、可達性矩陣可達性矩陣PG:簡單有向圖簡單有向圖V=v1,v2,vnn階方陣階方陣 P=(pij)nnG的可達性矩陣的可達性矩陣pij=10從從

48、vi到到vj至少存在一條路徑至少存在一條路徑否則2、求可達性矩陣、求可達性矩陣P的方法的方法(1)回憶兩個定理回憶兩個定理(2)求可達性矩陣求可達性矩陣P的方法的方法(1)回憶兩個定理回憶兩個定理n若存在從若存在從vi到到vj的路徑，則存在從的路徑，則存在從vi到到vj的的基本路徑；基本路徑；nn階圖的基本路徑長度小于階圖的基本路徑長度小于n;(2)求可達性矩陣求可達性矩陣P的方法的方法A：aij表示表示從從vi到到vj長度為長度為1的路徑的數(shù)目；的路徑的數(shù)目；A2:aij(2)表示從表示從vi到到vj長度為長度為2的路徑的數(shù)目；的路徑的數(shù)目；An:aij(n)表示從表示從vi到到vj長度為長

49、度為n的路徑的數(shù)目；的路徑的數(shù)目；令：令：Bn=A+A2+An 其中：其中： Bn中第中第i行第行第j列的記入值列的記入值bij表明：從表明：從vi到到vj長度長度小于或等于小于或等于n的路徑的數(shù)目的路徑的數(shù)目若若bij 0，則表明從，則表明從vi到到vj可達?？蛇_。求可達性矩陣求可達性矩陣P的方法（續(xù)）的方法（續(xù)）A:簡單有向圖簡單有向圖G的鄰接矩陣的鄰接矩陣（1）A2=AAA3=A2A ,An=An-1A（2）P= AA2An求可達性矩陣求可達性矩陣P P舉例舉例求圖求圖G G的鄰接矩陣的鄰接矩陣A A及可達性矩陣及可達性矩陣P P。A=v1v2v3v41001000010000000v1

50、v2v3v4v5v5000100001解答（續(xù)）解答（續(xù)）A=v1v2v3v4100 1000010000000v1v2v3v4v5v5000100 0 01解答（續(xù)）解答（續(xù)）由可達性矩陣由可達性矩陣P P可知：可知：v v1 1到到v v2 2,v,v4 4,v,v5 5可達；可達；v v2 2到到v v2 2,v,v4 4,v,v5 5可達；可達；v v3 3到到v v1 1 , v , v2 2,v,v4 4,v,v5 5可達；可達； v v4 4到到v v2 2,v,v4 4,v,v5 5可達；可達；v v5 5到到v v2 2,v,v4 4,v,v5 5可達；可達；三、完全關聯(lián)矩陣

51、：三、完全關聯(lián)矩陣：1、無向圖的完全關聯(lián)矩陣、無向圖的完全關聯(lián)矩陣2、有向圖的完全關聯(lián)矩陣、有向圖的完全關聯(lián)矩陣1、無向圖的完全關聯(lián)矩陣、無向圖的完全關聯(lián)矩陣G:無向圖無向圖V=v1,v2,vnE=e1,e2,emAe= (aij)nm圖圖G的完全關聯(lián)矩陣的完全關聯(lián)矩陣aij=10vi關聯(lián)關聯(lián)ej否則無向圖的完全關聯(lián)矩陣舉例無向圖的完全關聯(lián)矩陣舉例求無向圖求無向圖G G的完全關聯(lián)矩陣的完全關聯(lián)矩陣A AeAe=v1v2v3v41110111000001100e1e2e3e4e51001無向圖的完全關聯(lián)矩陣的特點無向圖的完全關聯(lián)矩陣的特點（1）每一）每一列列中只有中只有兩個兩個“1”；（2）每一

52、）每一行行中中“1”的個數(shù)的個數(shù)是該結點的是該結點的度度數(shù)；數(shù)；（3）若某）若某行行中的元素中的元素均為均為“0”，則該行所，則該行所對應的結點是對應的結點是孤立結點孤立結點；（4）平行邊平行邊所對應的所對應的兩列相同兩列相同；2、有向圖的完全關聯(lián)矩陣、有向圖的完全關聯(lián)矩陣G:有向圖有向圖V=v1,v2,vn E=e1,e2,emAe= (aij)nm圖圖G的完全關聯(lián)矩陣的完全關聯(lián)矩陣aij=10vi是是ej的起點的起點-1vi是是ej的終點的終點Vi與與ej不關聯(lián)不關聯(lián)有向圖的完全關聯(lián)矩陣舉例有向圖的完全關聯(lián)矩陣舉例求有向圖求有向圖G G的完全關聯(lián)矩陣的完全關聯(lián)矩陣AeAeAe=v1v2v3

53、v4-1-10-111000001100-1e1e2e3e4e501-10v5e61-1000000 0 0有向圖的完全關聯(lián)矩陣的特點有向圖的完全關聯(lián)矩陣的特點（1）每）每列列元素元素之和為之和為“0”；（2）每一）每一行行中中“1”的個數(shù)的個數(shù)是該行所對應結是該行所對應結點的點的出度出度；（3）每一）每一行行中中“-1”的個數(shù)的個數(shù)是該行所對應結是該行所對應結點的點的入度入度；（4）全為全為“0”的行的行所對應的結點為所對應的結點為孤立結孤立結點點。第第5節(jié)節(jié) 歐拉圖和哈密頓圖歐拉圖和哈密頓圖一、歐拉圖一、歐拉圖二、哈密頓圖二、哈密頓圖一、歐拉圖一、歐拉圖1、歐拉路徑、歐拉路徑2、歐拉回路、

54、歐拉回路3、歐拉圖、歐拉圖4、有向歐拉圖、有向歐拉圖歐拉圖的起源1、歐拉路徑、歐拉路徑G:無孤立結點的無向圖無孤立結點的無向圖經(jīng)過圖中每條邊一次且僅一次路徑經(jīng)過圖中每條邊一次且僅一次路徑歐拉路徑歐拉路徑:2、歐拉回路、歐拉回路G:無孤立結點的無向圖無孤立結點的無向圖歐拉回路歐拉回路:經(jīng)過圖中每條邊一次且僅一次回路經(jīng)過圖中每條邊一次且僅一次回路3、歐拉圖、歐拉圖具有具有歐拉回路歐拉回路的圖叫歐拉圖。的圖叫歐拉圖。歐拉圖舉例歐拉圖舉例判斷圖判斷圖G1和和G2是否是歐拉圖？是否是歐拉圖？解答解答G G1 1：歐拉回路歐拉回路1234563726781歐拉圖歐拉圖G G2 2：125462341歐拉回

55、路歐拉回路歐拉圖歐拉圖定理定理無向連通圖無向連通圖G G是歐拉圖是歐拉圖G的的每個結點均為偶結點每個結點均為偶結點哥尼斯堡七橋問題哥尼斯堡七橋問題deg(Adeg(A)=deg(B)=deg(D)=3)=deg(B)=deg(D)=3，deg(Cdeg(C)=5)=5哥尼斯堡七橋問題無解。哥尼斯堡七橋問題無解。歐拉圖應用舉例歐拉圖應用舉例環(huán)衛(wèi)工人清掃街道，清掃路線如圖所示，試環(huán)衛(wèi)工人清掃街道，清掃路線如圖所示，試問是否存在清掃路線問是否存在清掃路線使環(huán)衛(wèi)工人從使環(huán)衛(wèi)工人從V V1 1出發(fā)通過出發(fā)通過所有路線而不重復且最后所有路線而不重復且最后回到回到V V1 1。 解答解答由于圖中每個結點均為

56、偶次數(shù)，故由定理可知這樣由于圖中每個結點均為偶次數(shù)，故由定理可知這樣的一條清掃路線是存在的。的一條清掃路線是存在的。 (v1, v5, v11, v7, v12, v8, v10, v6, v9, v11, v12, v10, v9, v5, v2, v6, v4, v8, v3, v7, v1)deg(vdeg(v1 1)=deg(v)=deg(v2 2)=deg(v)=deg(v3 3)= deg(v)= deg(v4 4)= 2)= 2，deg(vdeg(v5 5)=deg(v)=deg(v6 6)=deg(v)=deg(v7 7)=deg(v)=deg(v8 8)=deg(v)=deg

57、(v9 9) )=deg(v=deg(v1010)=deg(v)=deg(v11 11)= deg(v)= deg(v1212)= 4)= 4定理定理無向連通圖無向連通圖G中結點中結點vi與與vj間存在間存在歐拉路徑歐拉路徑vi與與vj的度數(shù)均為奇數(shù)的度數(shù)均為奇數(shù)其它結點的度數(shù)均為偶數(shù)其它結點的度數(shù)均為偶數(shù)定理應用舉例定理應用舉例一筆畫問題：一筆畫問題：判別圖判別圖(1)(1)、(2)(2)是否可以一筆畫。是否可以一筆畫。解答解答圖圖(1)A、B為奇結點為奇結點C,D,E為偶結點為偶結點歐拉路徑歐拉路徑:AEDCBECAB解答解答圖圖(2)A、B為奇結點為奇結點其余各點為偶結點其余各點為偶結點

58、A與與B兩點間存在歐拉路徑，即兩點間存在歐拉路徑，即從從A到到B可以一筆畫?？梢砸还P畫。定理應用舉例定理應用舉例判斷圖（判斷圖（3 3）是否可以一筆畫）是否可以一筆畫 。A,B,C,D均為奇結點均為奇結點圖圖(3)中無歐拉路徑，中無歐拉路徑，因此不可以一筆畫。因此不可以一筆畫。4、有向、有向歐拉圖歐拉圖G:有向圖有向圖經(jīng)過圖中每條邊一次且僅一次的有向路徑經(jīng)過圖中每條邊一次且僅一次的有向路徑有向歐拉路徑有向歐拉路徑:有向歐拉回路有向歐拉回路:經(jīng)過圖中每條邊一次且僅一次的有向回路經(jīng)過圖中每條邊一次且僅一次的有向回路有向歐拉圖有向歐拉圖:有有向歐拉回路的有向圖有有向歐拉回路的有向圖定理定理一個連通有

59、向圖一個連通有向圖G是有向歐拉圖是有向歐拉圖對對G中的所有結點中的所有結點v,有：有：d +(v)=d-(v)有向歐拉圖舉例有向歐拉圖舉例判斷圖判斷圖G G1 1和和G G2 2是否為有向歐拉圖，如果是否為有向歐拉圖，如果是，請給出有向歐拉回路。是，請給出有向歐拉回路。圖圖G1圖圖G2解答解答d d+ +(v(v1 1)=d)=d- -(v(v1 1)=1)=1d d+ +(v(v2 2)=d)=d- -(v(v2 2)=2)=2d d+ +(v(v3 3)=d)=d- -(v(v3 3)=1)=1d d+ +(v(v4 4)=d)=d- -(v(v4 4)=2)=2d d+ +(v(v5 5

60、)=d)=d- -(v(v5 5)=2)=2是有向歐拉圖是有向歐拉圖有向歐拉回路有向歐拉回路:v1e1v2e3v4e7v5e5v1e6v4e8v5e4v3e2v1解答解答d d+ +(v(v4 4)=1)=1 d d- -(v(v4 4)=3)=3d d+ +(v(v5 5)=3)=3 d d- -(v(v5 5)=1)=1不是有向歐拉圖不是有向歐拉圖定理定理G:連通有向圖連通有向圖G中兩個結點中兩個結點vi和和vjvi的出度比入度大的出度比入度大1vj的出度比入度小的出度比入度小1其它結點的出度和入度相等其它結點的出度和入度相等G中存在從中存在從vi到到vj的有向歐拉路徑的有向歐拉路徑二、哈