圖和子圖(1).ppt

《圖和子圖(1).ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、圖和子圖(1)四川師范大學數(shù)學與軟件科學學院周思波1.1基本概念現(xiàn)實世界的許多現(xiàn)象可以用一類圖形來描述，這種圖形由一個點集和連接這個點集中某些點對的線所構(gòu)成．例如用點表示車站，線表示連接車站與車站的道路；或者用點表示人，連線表示一對朋友．在這種圖形中，人們主要感興趣的是：兩點是否被一條線所連接，而連線的長短曲直則無關(guān)緊要．大量的這類事實的數(shù)學抽象，產(chǎn)生了圖的概念．圖的概念有序三元組G＝[V(G)，E(G)，ΨG]稱為一個圖，其中：ⅰ)V(G)稱為頂點集合；ⅱ)E(G)∩V(G)=φ，E(G)稱為邊集合；ⅲ)ΨG是E(G)到{(a,b)

2、a,b∈V(G)}的映射，稱為關(guān)聯(lián)函數(shù)．V(G)中的元

3、素稱為頂點，E(G)中的元素稱為邊．V(G)所含元素的個數(shù)即頂點個數(shù)稱為圖的階，用

4、V(G)

5、表示．E(G)所含元素的個數(shù)稱為G的邊數(shù)，用

6、E(G)

7、表示．我們用G(p，q)表添一個階為p、邊數(shù)為q的圖G，這時也說G是一個(p，q)圖．例題G＝[V(G)，E(G)，ΨG]，其中：V(G)={v1,v2,v3,v4}，E(G)={e1,e2,e3,e4,e5,e6}，ΨG定義為：ΨG(e1)=v2v3，ΨG(e2)=v3v4ΨG(e3)=v4v4，ΨG(e4)=v2v4ΨG(e5)=v2v3，ΨG(e6)=v1v3e1e6e5e4e3e2e1e6e5e4e3e2相關(guān)概念在圖G＝[V(G)，E

8、(G)，ΨG]中,若e∈E(G)，u,v∈V(G)，而ΨG(e)=(u,v)，則稱u和v是e的端點，或e和u,v關(guān)聯(lián)，此時稱u和v是鄰接的。若兩條不同的邊ei和ej有一個公共端點，則稱是鄰接的，不與任何邊鄰接的邊稱為孤立邊，不與任何邊關(guān)聯(lián)的頂點稱為孤立點。兩端重合的邊稱為環(huán)，端點不同的邊稱為桿。若V(G)和E(G)都是有限集，則稱G為有限圖。G(0,0)稱為空圖，E(G)=φ即G是由孤立點所組成，稱為零圖。G(1,0)稱為平凡圖。簡單圖和完全圖圖中若連接兩個相同頂點的邊的條數(shù)大于1，則說這對頂點間有重邊相連．同一對頂點間邊的條數(shù)稱為邊的重數(shù)，既沒有環(huán)也沒有重邊的圖稱為簡單圖，否則稱為偽圖，

9、沒有環(huán)的偽圖稱為多重圖．每對不同的頂點均有邊相連的簡單圖稱為完全圖．n階完全圖記為Kn定理1.1：Kn有條邊二分圖圖G的頂點集V(G)若能分成兩個子集V1和V2，使得G的每條邊有一個端點在V1，另一個端點在V2中，則G稱為二分圖或偶圖．這樣一個把V(G)分成兩個集合V1、V2的分劃(V1,V2)稱為G的一個二分劃．設簡單二分圖G的二分劃為(V1,V2)，如果V1的每個頂點與V2的每一個頂點都鄰接，則G稱為完全二分圖．若

10、V1

11、=m,

12、V2

13、=n,則這樣的圖記為Km,n定理1.2Km,n有mn條邊。補圖G是簡單圖，如果簡單圖GC滿足，ⅰ)V(GC)=V(G)ⅱ)V(GC)中兩點當且僅當它們在

14、G中不鄰接時在GC中鄰接．那么GC稱為G的補圖．G：GC：平面圖在保持圖的頂點和邊的關(guān)聯(lián)關(guān)系不變的情況下，一個圖可以作出許多圖形．如果一個圖具有這樣的圖形，它的邊僅在頂點處相交，則稱它為平面圖．判斷圖1是否為平面圖？圖1：圖2：恒同和同構(gòu)兩個圖H和G，如果V(H)＝V(G)，E(H)＝E(G)且ΨH＝ΨG，那么H和G就稱為是恒同的，恒同的圖當然可以用一個圖形來表示．G＝[V(G)，E(G)，ΨG]和H＝[V(H)，E(H)，ΨH]，若存在1-1對應偶(θ,φ)，θ:V(G)→V(H)；φ:E(G)→E(H)，使得當且僅當ΨH(φ(e))=θ(u)θ(v)時，ΨG(e)=uv，則說這兩個圖同

15、構(gòu)，記為G≌H度與正則圖設v∈V(G)，G中與頂點v關(guān)聯(lián)的邊的數(shù)目稱為v在G中的度(次)，記為dG(v)或d(v)．一個環(huán)的端點的度數(shù)計為2．如果d(v)是奇數(shù)，就說v是奇頂點；如果d(v)是偶數(shù)，就說v是偶頂點．如果一個圖的每一個頂點都具有相同的度，則稱這個圖是正則圖。每個頂點的度均為k的正則圖，稱為k-正則圖．有關(guān)度的定理定理1.3圖G中各頂點度數(shù)之和等于邊數(shù)的2倍。推論1.4任意一個圖奇頂點的個數(shù)是偶數(shù)．推論1.5正則圖的階與各頂點度數(shù)不全為奇數(shù)．子圖設H和G是兩個圖，如果V(H)是V(G)的子集，E(H)是E(G)的子集且ΨH是ΨG在E(H)內(nèi)的導出函數(shù)，那么H稱為G的子圖，此時G

16、稱為H的母圖，記為如果而H≠G，則說H是G的真子圖，記為設H是G的子圖，如果V(H)=V(G)，則H稱為G的生成子圖。導出子圖設V’是V(G)的非空子集，H是G的一個子圖，如果：ⅰ)V(H)=V’；ⅱ)E(H)={e

17、e∈E(G),ΨG(e)=uv，u,v∈V’}；ⅲ)ΨH是ΨG在E(H)上的導出函數(shù)。那么H稱為由V’導出的G的子圖，記為G[V’]導出子圖G[V-V’]記為G-V’，它是從G中刪除V’中的頂點及與這些頂點