資源描述：
《離散數(shù)學(xué)屈婉玲第九章.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、1第三部分圖論本部分主要內(nèi)容圖的基本概念樹歐拉圖與哈密頓圖二部圖與匹配平面圖著色2第九章圖的基本概念主要內(nèi)容圖通路與回路圖的連通性圖的矩陣表示預(yù)備知識多重集合——元素可以重復(fù)出現(xiàn)的集合無序集——A?B={(x,y)
2、x?A?y?B}14.1圖定義9.1無向圖G=,其中(1)V為非空有窮集,稱為頂點集，其元素稱為頂點(2)E為V?V的多重有窮集,稱為邊集,其元素稱為無向邊,簡稱邊例無向圖G=,其中V={v1,v2,v3,v4,v5},E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}4有向圖定義9.2
3、有向圖D=,其中(1)V為非空有窮集,稱為頂點集，其元素稱為頂點(2)E為V?V的多重有窮集,稱為邊集,其元素稱為有向邊,簡稱邊例有向圖D=,其中V={a,b,c,d}E={,,,,,,}注意：圖的集合表示與圖形表示之間的對應(yīng)5相關(guān)概念1.無向圖和有向圖通稱圖.記頂點集V(G),邊集E(G).2.圖的階,n階圖.3.n階零圖Nn,平凡圖N1.4.空圖?.5.標定圖與非標定圖.6.有向圖的基圖.7.無向圖中頂點與邊的關(guān)聯(lián)及關(guān)聯(lián)次數(shù),頂點與頂點、邊與邊的相鄰關(guān)系.8.有向圖中頂點與邊的關(guān)聯(lián),頂點與頂點
4、、邊與邊的相鄰關(guān)系.9.環(huán),孤立點.6多重圖與簡單圖定義9.3無向圖中關(guān)聯(lián)同一對頂點的2條和2條以上的邊稱為平行邊.有向圖中2條和2條以上始點、終點相同的邊稱為平行邊.平行邊的條數(shù)稱為重數(shù).含平行邊的圖稱為多重圖,不含平行邊和環(huán)的圖稱為簡單圖.定義9.4設(shè)G=為無向圖,?v?V,稱v作為邊的端點的次數(shù)之和為v的度數(shù),簡稱度,記作d(v).設(shè)D=為有向圖,?v?V,稱v作為邊的始點的次數(shù)之和為v的出度,記作d+(v);稱v作為邊的終點的次數(shù)之和為v的入度,記作d?(v);稱d+(v)+d?(v)為v的度數(shù),記作d(v).7頂點的度數(shù)設(shè)G=為無向圖,G的最大度
5、?(G)=max{d(v)
6、v?V}G的最小度?(G)=min{d(v)
7、v?V}設(shè)D=為無向圖,D的最大度?(D)=max{d(v)
8、v?V}D的最小度?(D)=min{d(v)
9、v?V}D的最大出度?+(D)=max{d+(v)
10、v?V}D的最小出度?+(D)=min{d+(v)
11、v?V}D的最大入度??(D)=max{d?(v)
12、v?V}D的最小入度??(D)=min{d?(v)
13、v?V}懸掛頂點:度數(shù)為1的頂點,懸掛邊:與懸掛頂點關(guān)聯(lián)的邊.偶度(奇度)頂點:度數(shù)為偶數(shù)(奇數(shù))的頂點8實例d(v1)=4,d(v2)=4,d(v3)=2,d(v4)=1,d(v5)=3.?
14、=4,?=1.v4是懸掛點,e7是懸掛邊.d+(a)=4,d?(a)=1,d(a)=5,d+(b)=0,d?(b)=3,d(b)=3,d+(c)=2,d?(c)=1,d(c)=3,d+(d)=1,d?(d)=2,d(d)=3,?+=4,?+=0,??=3,??=1,?=5,?=3.9定理9.1在任何無向圖中,所有頂點的度數(shù)之和等于邊數(shù)的2倍.證G中每條邊(包括環(huán))均有兩個端點，所以在計算G中各頂點度數(shù)之和時，每條邊均提供2度，m條邊共提供2m度.握手定理定理9.2在任何有向圖中，所有頂點的度數(shù)之和等于邊數(shù)的2倍;所有頂點的入度之和等于所有頂點的出度之和,都等于邊數(shù).推論任何圖(無向或有
15、向)中，奇度頂點的個數(shù)是偶數(shù).證由握手定理,所有頂點的度數(shù)之和是偶數(shù),而偶度頂點的度數(shù)之和是偶數(shù),故奇度頂點的度數(shù)之和也是偶數(shù).所以奇度頂點的個數(shù)必是偶數(shù)．10例1無向圖G有16條邊，3個4度頂點，4個3度頂點，其余均為2度頂點度，問G的階數(shù)n為幾？解本題的關(guān)鍵是應(yīng)用握手定理.設(shè)除3度與4度頂點外，還有x個頂點,由握手定理,16?2=32=3?4+4?3+2x解得x=4,階數(shù)n=4+4+3=11.握手定理應(yīng)用定理9.3設(shè)G為任意n階無向簡單圖，則?(G)?n?1．圖的同構(gòu)定義9.5設(shè)G1=,G2=為兩個無向圖(兩個有向圖)，若存在雙射函數(shù)f:V1?V2,使得
16、?vi,vj?V1,(vi,vj)?E1當且僅當(f(vi),f(vj))?E2（?E1當且僅當?E2)并且,(vi,vj)（）與(f(vi),f(vj))（）的重數(shù)相同，則稱G1與G2是同構(gòu)的，記作G1?G2.例12圖同構(gòu)的實例(1)(2)(3)(4)(1)與(2),(3)與(4),(5)與(6)均不同構(gòu).(5)(6)說明:1.圖的同構(gòu)關(guān)系具有自反性、對稱性和傳遞
