14.1 無向圖 有向圖概念

1、1 圖論圖論 2圖論部分前言圖論部分前言 n圖論圖論(Graph theory)是一門古老而年輕的學科是一門古老而年輕的學科.n古老古老:早在早在18世紀世紀,學者們便運用圖為工具來解決學者們便運用圖為工具來解決一些實際問題一些實際問題.n年輕年輕:直到直到20世紀中后期世紀中后期,尤其是隨著計算機科學尤其是隨著計算機科學與技術的發(fā)展與技術的發(fā)展,圖的理論和應用研究逐漸得到重視圖的理論和應用研究逐漸得到重視,圖論作為一個數(shù)學分支圖論作為一個數(shù)學分支,才確立了它的地位才確立了它的地位.31 圖論的起源n圖論的起源可以追溯到1736年,n瑞士數(shù)學家歐拉(Eular)(1707-1783)成功解決了

2、當時很有名的哥尼斯堡七橋問題,n并發(fā)表了第一篇圖論論文,歐拉成為圖論的創(chuàng)始人.哥尼斯堡位于立陶宛的普雷格爾河畔河中有有兩個小島和七座橋.居民們提出的問題是:可否從城市或島上的可否從城市或島上的一點出發(fā)一點出發(fā),經(jīng)由七橋經(jīng)由七橋,并且只經(jīng)過每座橋一次并且只經(jīng)過每座橋一次,然后回到原地然后回到原地.4n用結點表示兩岸和小島,用結點間的連線表示橋. 問題轉化為:是否能從某一點出發(fā)經(jīng)過每條線段恰好一次,然后再回到出發(fā)點. 最后,歐拉論證了七橋問題無解.n歐拉將該問題抽象下右圖.抽象5 可以看到b)圖是a)圖的抽象,人們不注重結點的位置邊的長短形狀.只關心結點與邊的聯(lián)結關系. 這與幾何學中的圖形有本質區(qū)

3、別.a)b)像這樣由結點和邊組成的離散結構就是本章討論的圖.6圖論的應用n圖論廣泛應用于建立和處理離散對象及其關系, 如:關系(關系圖)網(wǎng)絡運籌規(guī)劃等在計算機科學領域:算法設計操作系統(tǒng)網(wǎng)絡理論,都有廣泛應用.其他領域:生物學經(jīng)濟控制論運籌學等7 第第5 5章章 圖的基本概念圖的基本概念 5.1 無向圖及有向圖無向圖及有向圖8基本概念基本概念無序積無序積A B :用來表示無向圖的邊用來表示無向圖的邊.設設A,B為兩集合為兩集合, A B=(x,y) | x A且且y B A B為為A與與B的無序積的無序積, (x,y)叫無序對叫無序對.例如:設A=a1,a2,B=b1,b2,則 A&B=(a1,

4、b1),(a1,b2),(a2,b1),(a2,b2) A&A=(a1,a1),(a1,a2),(a2,a2)注意與笛卡兒積的區(qū)別注意與笛卡兒積的區(qū)別AB=,AA=,跟有序對不同跟有序對不同,對無序對對無序對,無論無論x,y是否相同是否相同 ,有有(x,y)=(y,x). 如如: (3,5)=(5,3)9多重集合多重集合: 元素可以重復出現(xiàn)的集合元素可以重復出現(xiàn)的集合. 在多重集合中在多重集合中: 1,1,2,2,3 1,2,3在集合論中在集合論中,同一個元素在集合中多次出現(xiàn)被同一個元素在集合中多次出現(xiàn)被認為是一個元素認為是一個元素,如如: 1,1,2,2,3=1,2,3多重集合的概念引入是為

5、了表示圖的平行邊多重集合的概念引入是為了表示圖的平行邊.10無向圖無向圖定義定義 一個無向圖一個無向圖G是一個二元組是一個二元組,即即G=, 其中其中(1) V是一個非空集合是一個非空集合,稱為稱為G的頂點集的頂點集(vertex)，V中元素稱為中元素稱為頂點或結點頂點或結點.(2) E為無序積為無序積V V的一個多重子集的一個多重子集(元素可以重元素可以重復出現(xiàn)復出現(xiàn))，稱為，稱為G的邊集的邊集,E中元素稱為中元素稱為無向邊無向邊，簡稱簡稱邊邊(edge).用無序對用無序對(a,b)表示表示連接頂點a和頂點b的邊,(a,b)=(b,a).例如例如, G=如圖所示如圖所示, 其中其中V=v1,

6、 v2, ,v5, E=(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 注意注意:連接連接v2,v3的邊有兩條的邊有兩條. 無向圖的邊沒有方向.11有向圖有向圖定義定義 有向圖有向圖D=, 其中其中(1) V是是頂點集頂點集, 元素也稱為元素也稱為頂點頂點(2) E是邊集是邊集,為笛卡兒積為笛卡兒積V V的多重子集，其元素的多重子集，其元素 稱為稱為有向邊有向邊，簡稱，簡稱邊邊.用有序對用有序對表示表示頂點a指向頂點b的邊,注:在有向圖中,有向邊,是有方向方向的, 箭頭從a指向b,表示a是起點,b是終點.右圖是有向圖，

7、試寫出它的右圖是有向圖，試寫出它的V和和E V=a,b,c,dE=, 注意注意:頂點頂點a指向指向b的邊的邊有兩條有兩條, ,是兩條方向相反的邊是兩條方向相反的邊.12為了表示的方便為了表示的方便,邊的還有另一種表示法邊的還有另一種表示法:用用ek表示表示無向邊或有向邊無向邊或有向邊. 如下圖如下圖e1=(v1,v1), e2=(v1,v2)E=e1,e2,e3,e4,e5,e6,e7E=e1,e2,e3,e4,e5,e6,e7邊的另一種表示方法:13相關概念與規(guī)定相關概念與規(guī)定nn 階圖階圖: n個頂點的圖個頂點的圖n有限圖有限圖: V, E都是有窮集合的圖都是有窮集合的圖,本書只討本書只討

8、論有限圖論有限圖n零圖零圖: 邊集邊集E=n平凡圖平凡圖: 1 階零圖階零圖n空圖空圖: 頂點集頂點集V=D(Directed graph)表示有向圖表示有向圖,也常用也常用G泛指無向圖和有向圖泛指無向圖和有向圖,通常用通常用G(Graph)表示無向圖表示無向圖.145.5例題分析: p134n例5.7 給定圖的集合表示,畫出圖形.152 2 頂點和邊的關系頂點和邊的關系- -關聯(lián)關聯(lián)定義定義 設設ek=(vi, vj)是無向圖是無向圖G=的一條的一條邊邊, 稱稱vi, vj為為ek的的端點端點, ek與與vi ( vj)關聯(lián)關聯(lián). 若若vi vj, 則稱則稱ek與與vi ( vj)的的關聯(lián)次

9、數(shù)為關聯(lián)次數(shù)為1; 若若vi = vj, 則稱則稱ek為為環(huán)環(huán), 此時稱此時稱ek與與vi 的的關關聯(lián)次數(shù)為聯(lián)次數(shù)為2; 若若vi不是不是ek端點端點, 則稱則稱ek與與vi 的的關聯(lián)次數(shù)關聯(lián)次數(shù)為為0. 無邊關聯(lián)的頂點稱作無邊關聯(lián)的頂點稱作孤立點孤立點.ekvivj問:e1與v1的關聯(lián)次數(shù)是多少e2與v1和v2的關聯(lián)次數(shù)是多少?16對對無向圖無向圖G=, vi,vj V, ek,el E, 若若(vi,vj)組成一條邊組成一條邊, 則稱則稱vi,vj相鄰相鄰(點相鄰點相鄰); v1和v2點相鄰 若若ek,el至少有一個公共端點至少有一個公共端點, 則稱則稱ek,el相鄰相鄰(邊相鄰邊相鄰).

10、 e2和e3邊相鄰.相鄰相鄰(點相鄰，邊相鄰，鄰接到）點相鄰，邊相鄰，鄰接到）對對有向圖有向圖有類似定義有類似定義. 設設ek= vi,vj 是有是有向圖的一條邊向圖的一條邊,又稱又稱vi是是ek的的始點始點, vj是是ek的的終點終點, vi鄰接到鄰接到vj, vj鄰接于鄰接于vi. a鄰接于鄰接于b, a是起點是起點,b是終點是終點17鄰域和關聯(lián)集鄰域和關聯(lián)集 )(vN)(vD )()(vvNvNDD )(vD )()()(vvvNDDD 設無向圖設無向圖G, v V(G) v的鄰域的鄰域 N(v)=u|u V(G) (u,v) E(G) u v v的閉鄰域的閉鄰域 = N(v)v v的關

11、聯(lián)集的關聯(lián)集 I(v)=e|e E(G) e與與v關聯(lián)關聯(lián)設有向圖設有向圖D, v V(D) v的后繼元集的后繼元集 =u|u V(D) E(G) u v v的先驅元集的先驅元集 =u|u V(D) E(G) u v v的鄰域的鄰域 v的閉鄰域的閉鄰域18頂點的度數(shù)頂點的度數(shù)(Degree)-(Degree)-點作為邊的端點次數(shù)之和點作為邊的端點次數(shù)之和 設設G=為無向圖為無向圖, v V, v的度數(shù)的度數(shù)(度度) d(v): v作為邊的端點次數(shù)之和作為邊的端點次數(shù)之和 懸掛頂點懸掛頂點: 度數(shù)為度數(shù)為1的頂點的頂點 懸掛邊懸掛邊: 與懸掛頂點關聯(lián)的邊與懸掛頂點關聯(lián)的邊 G的最大度的最大度 (

12、G)=maxd(v)| v V G的最小度的最小度 (G)=mind(v)| v V例如例如 d(v1)=4, d(v2)=4, d(v3)=2, d(v4)=1, d(v5)=3, (G)=4, (G)=1, v4是懸掛頂點是懸掛頂點, e7是懸掛邊是懸掛邊, e1是環(huán)是環(huán) 19有向圖有向圖的度數(shù)的度數(shù) 設設D=為有向圖為有向圖, v V, v的出度的出度d+(v): v作為邊的始點次數(shù)之和作為邊的始點次數(shù)之和 v的入度的入度d (v): v作為邊的終點次數(shù)之和作為邊的終點次數(shù)之和 v的度數(shù)的度數(shù)(度度) d(v): v作為邊的端點次數(shù)之和作為邊的端點次數(shù)之和 d(v)= d+(v)+ d-

13、(v)D的最大出度的最大出度 +(D), 最小出度最小出度 +(D) 最大入度最大入度 (D), 最小入度最小入度 (D) 最大度最大度 (D), 最小度最小度 (D) 例如例如 d+(a)=4, d-(a)=1, d(a)=5, d+(b)=0, d-(b)=3, d(b)=3, +(D)=4, +(D)=0, (D)=3, (D)=1, (D)=5, (D)=3. 20頂點度數(shù)和邊數(shù)的關系頂點度數(shù)和邊數(shù)的關系握手定理握手定理n握手定理是圖論中的基本定理.n它是歐拉在1736年給出的n主要包括兩個定理,一個推論.要求能熟練應用.21握手定理握手定理 定理定理1 任意無向圖和有向圖的所有頂點度

14、數(shù)之和都任意無向圖和有向圖的所有頂點度數(shù)之和都等于邊數(shù)的等于邊數(shù)的2倍倍. 上圖度數(shù)和為上圖度數(shù)和為6,邊為邊為3定理定理2:有向圖的所有頂點入度之和等于出度之和等有向圖的所有頂點入度之和等于出度之和等于邊數(shù)于邊數(shù).bc度數(shù)和:2+1+1=4邊:2入度和:1=1=2出度和:2a頂點: a b c入度: 0 1 1出度: 2 0 022握手定理握手定理( (續(xù)續(xù)) ) 21)()()(2VvVvVvvdvdvdm 2)(Vvvd 1)(Vvvd推論推論 在任何無向圖和有向圖中，奇度頂點的個數(shù)必在任何無向圖和有向圖中，奇度頂點的個數(shù)必 為偶數(shù)為偶數(shù).證證 設設G=為任意圖，令為任意圖，令 V1=v

15、 | v V d(v)為奇數(shù)為奇數(shù) V2=v | v V d(v)為偶數(shù)為偶數(shù)則則V1V2=V, V1V2=，由握手定理可知，由握手定理可知 由于由于2m, 均為偶數(shù)，所以均為偶數(shù)，所以 也為偶數(shù)也為偶數(shù), 但因為但因為V1中頂點度數(shù)都為奇數(shù)，所以中頂點度數(shù)都為奇數(shù)，所以|V1|必為偶數(shù)必為偶數(shù). 23 設無向圖設無向圖G的頂點集的頂點集V=v1, v2, , vnG的度數(shù)列的度數(shù)列: d(v1), d(v2), , d(vn)如右圖度數(shù)列如右圖度數(shù)列:4,4,2,1,3(邊數(shù)為邊數(shù)為7)設有向圖設有向圖D的頂點集的頂點集V=v1, v2, , vn如右圖如右圖D度數(shù)列度數(shù)列:5,3,3,3

16、出度列出度列:4,0,2,1 入度列入度列:1,3,1,2(邊數(shù)為邊數(shù)為7)24n推論推論 在任何無向圖和有向圖中，奇度頂點在任何無向圖和有向圖中，奇度頂點的個數(shù)必為偶數(shù)的個數(shù)必為偶數(shù).度數(shù)列度數(shù)列:4,4,2,1,3度數(shù)列度數(shù)列:5,3,3,325握手定理的應用握手定理的應用例例1 (3,3,3,4), (2,3,4,6,8)能成為圖的度數(shù)列嗎能成為圖的度數(shù)列嗎?解解 不可能不可能. 它們都有奇數(shù)個奇度數(shù)它們都有奇數(shù)個奇度數(shù).例例2 一個無向圖一個無向圖G有有21條邊條邊,3個個4度頂點度頂點,其余都是其余都是3度頂點度頂點,問該圖有幾個頂點問該圖有幾個頂點? 解解 設設G有有n個個3度頂點

17、度頂點. 由握手定理由握手定理, 3 4+3 n=2 21解得解得 n=10, 該圖有該圖有13個頂點個頂點26握手定理的應用握手定理的應用(續(xù)續(xù))例例3 證明不存在具有奇數(shù)個面且每個面都具有奇數(shù)證明不存在具有奇數(shù)個面且每個面都具有奇數(shù)條棱的多面體條棱的多面體.證證 用反證法用反證法. 假設存在這樣的多面體假設存在這樣的多面體, 作無向圖作無向圖G=, 其中其中V=v | v為多面體的面為多面體的面, E=(u,v) | u,v V u與與v有公共的棱有公共的棱 u v. 根據(jù)假設根據(jù)假設, |V|為奇數(shù)且為奇數(shù)且 v V, d(v)為奇數(shù)為奇數(shù). 這與握這與握手定理的推論矛盾手定理的推論矛盾

18、.27n課堂練習-習題: 5.1 （1，2，3） 5.2 第1,2學時完28多重圖與簡單圖多重圖與簡單圖 定義定義 (1) (1) 在在無向圖無向圖中中, ,如果有如果有2 2條或條或2 2條以條以上的邊關聯(lián)同一對頂點上的邊關聯(lián)同一對頂點, , 則稱這些邊為則稱這些邊為平行邊平行邊, , 平行邊的條數(shù)稱為平行邊的條數(shù)稱為重數(shù)重數(shù). .(2)(2)在有向圖中在有向圖中, ,如果有如果有2 2條或條或2 2條以上的邊條以上的邊具有相同的始點和終點具有相同的始點和終點, , 則稱這些邊為則稱這些邊為有向平行邊有向平行邊, , 簡稱簡稱平行邊平行邊, , 平行邊的條平行邊的條數(shù)稱為數(shù)稱為重數(shù)重數(shù). .

19、(3) (3) 含平行邊的圖稱為含平行邊的圖稱為多重圖多重圖. .(4) (4) 既無平行邊也無環(huán)的圖稱為既無平行邊也無環(huán)的圖稱為簡單圖簡單圖. .注意注意: :簡單圖是極其重要的概念簡單圖是極其重要的概念 29多重圖與簡單圖多重圖與簡單圖( (續(xù)續(xù)) )例如例如e5和和e6 是平行邊是平行邊重數(shù)為重數(shù)為2不是簡單圖不是簡單圖e2和和e3 是平行邊是平行邊,重數(shù)為重數(shù)為2e6和和e7 不是平行邊不是平行邊(why?)不是簡單圖不是簡單圖30圖的同構（了解）n用圖解表示法來表示一個圖時,結點在平面上排列的位置是沒有限制的,因此,用一個事物之間的關系可能畫出不同形狀的圖n這樣的圖叫同構(G1 G2

20、).設設A=a,b,c,R=,abcabc31同構同構的定義的定義定義定義 設設G1=, G2=為兩個無向圖為兩個無向圖,若存在雙射函若存在雙射函數(shù)數(shù) f: V1V2, 使得對于使得對于任意任意的的vi,vj V1, (vi,vj) E1當且僅當當且僅當 (f(vi),f(vj) E2，并且并且, (vi,vj)與與 (f(vi),f(vj) 的重數(shù)相同，則稱的重數(shù)相同，則稱G1與與G2是是同構同構的，的，記作記作G1 G2. 例例: :v1v2v3v4v5u1u2u3u4u5設G1=,G2=,存在一個雙射函數(shù)f: V1V2,使得使得f(vi)=ui.G1G232 如何判斷圖是否同構如何判斷圖

21、是否同構? ?同構的同構的必要條件必要條件, 但它們都不是充分條件但它們都不是充分條件: 邊數(shù)相同，頂點數(shù)相同邊數(shù)相同，頂點數(shù)相同 度數(shù)列相同度數(shù)列相同 對應頂點的關聯(lián)集相同，等等對應頂點的關聯(lián)集相同，等等若破壞必要條件，則兩圖不同構若破壞必要條件，則兩圖不同構 但這些都是必要條件但這些都是必要條件,不是充分條件不是充分條件.至今沒有找到判斷兩個圖是否同構的有效算法至今沒有找到判斷兩個圖是否同構的有效算法 ,還只能根據(jù)定義還只能根據(jù)定義來判斷來判斷 例例: :33例 :下圖中G=(V,E),G=(V,E)是同構的.v1v2v3v4v5v6u1u2u3u4u5u6對任意vi,vj V,當當(vi

22、,vj) E時時,有有(ui,uj) E如如:(v1,v2) E,有有(u1,u2) Evi和ui一一對應.GG34n例例 下圖中下圖中G=（V，E）與）與G =（V ，E ）同）同構嗎？構嗎？n雖然有相同的結點,邊數(shù),但不滿足同構的定義,原因是兩個圖邊與結點的關聯(lián)關系不同. G中度為中度為3的的4個結個結點構成一個長為點構成一個長為4的的回路回路,而而G中沒有中沒有.GG35課堂練習:n例例1 試畫出試畫出4階階3條邊的所有非同構的無向簡單圖條邊的所有非同構的無向簡單圖例例2 判斷下述每一對圖是否同構判斷下述每一對圖是否同構:度數(shù)列不同度數(shù)列不同不同構不同構3,4,3,22,5,2,336例

23、例2 (續(xù)續(xù)) (2)不同構不同構入入(出出)度列不同度列不同(3)度數(shù)列相同度數(shù)列相同但不同構但不同構為什么為什么?37完全圖n定義定義 設G為n階無向簡單圖,若G中每個頂點均與其余的n-1個頂點相鄰,則稱G為n階無向完全圖,記作Kn。 例例 下圖分別給出了一個結點、二個結點、三個圖分別給出了一個結點、二個結點、三個結點、四個結點和五個結點的完全圖。結點、四個結點和五個結點的完全圖。什么是簡單圖什么是簡單圖:不含平行邊也不含環(huán)不含平行邊也不含環(huán).38n階無向完全圖階無向完全圖Kn性質性質: 邊數(shù)邊數(shù)m=n(n-1)/2, = =n-1右圖為右圖為5階完全圖階完全圖K5邊數(shù)邊數(shù):m=5(5-1

24、)/2=10度數(shù)度數(shù): = =439n階有向完全圖階有向完全圖: 每對頂點之間均有兩條方向每對頂點之間均有兩條方向相反的有向邊的相反的有向邊的n階有向簡單圖階有向簡單圖.性質性質: 邊數(shù)邊數(shù)m=n(n-1), = =2(n-1), += += -= -=n-1右圖為3階有向完全圖.邊數(shù)m=3(3-1)=6度數(shù) = =2(3-1)=440n階階k正則圖正則圖: 設設G為為n階無向簡單圖階無向簡單圖,若對所有若對所有頂點頂點,均有均有d(v)=k,則稱則稱G為為n階階k正則圖正則圖.性質性質: 邊數(shù)邊數(shù)m=nk/2右圖是右圖是3 正則圖正則圖,也叫也叫彼得森圖彼得森圖. d(v)=3邊數(shù)邊數(shù):m=

25、103/2=1541完全圖與正則圖完全圖與正則圖( (續(xù)續(xù)) ) (1) 為為5階完全圖階完全圖K5 (2) 為為3階有向完全圖階有向完全圖 (3) 為彼得森圖為彼得森圖, 它是它是3 正則圖正則圖 (1)(2)(3)彼得森圖彼得森圖42都有15條邊，頂點數(shù)都是10，所有頂點的度數(shù)都是3，這樣的圖叫彼得森圖。它的一般形狀是下面的第一張圖，與之同構的圖多種多樣，形狀各異，共有100多種。43子圖子圖 定義定義 設設G=, G =是是2個圖個圖n若若V V且且E E, 則稱則稱G 為為G的的子圖子圖, G為為G 的的母圖母圖, 記作記作G G. 如如:G1,G2是是G的子圖的子圖.(2) 若若G

26、G 且且V =V，則稱，則稱G 為為G的的生成子圖生成子圖. G2是是G的生成子圖的生成子圖.(3) 若若V V 或或E E，稱，稱G 為為G的的真子圖真子圖. G1,G2是是G的真子圖的真子圖.GG1G244子圖子圖( (續(xù)續(xù)) )例例 畫出畫出K4的所有非同構的生成子圖的所有非同構的生成子圖 45導出子圖導出子圖(4) 設設V V 且且V , 以以V 為頂點集為頂點集, 以以兩端兩端點都在點都在V 中的所有邊中的所有邊為邊集的為邊集的G的子圖稱作的子圖稱作V 的導出子圖的導出子圖，記作，記作 GV 下圖下圖,V=a,b,G1是是V的導出子圖的導出子圖.G2呢呢?GG1G2練習:畫出V=a,d,c的導出子圖.46(5) 設設E E且且E , 以以E 為邊集為邊集, 以以E 中中邊邊關聯(lián)的所有頂點關聯(lián)的所有頂點為頂點集的為頂點集的G的子圖稱作的子圖稱作E 的導出子圖的導出子圖, 記作記作 GE .下圖下圖,E=e1,e2,e3,G1