【正文】 7 v 8 v 9 v 10 u1 u 2 u 3 u 4 u 5 u 6 u 7 u 8 u 9 u 10 ( b ) 容易驗(yàn)證 ，對 ?vi v j ?E ((a)), 有 f (v i vj,) ? ui,uj,? E((b)) ， (1? i ? 10, 1? j ? 10 ) 由圖的同構(gòu)定義知，圖 (a)與 (b)是同構(gòu)的。 例 證明下面兩圖同構(gòu)。對于規(guī)模不大的兩個圖，判定其是否同構(gòu)，可以采用觀察加推證的方法。 非標(biāo)定圖實(shí)際上是代表一類相互同構(gòu)的圖。該關(guān)系將所有的圖的集合，劃分為一些等價類，即相互同構(gòu)的圖作成同一個等價類。 定義 設(shè) v為 G 的頂點(diǎn)， G 中與 v 為端點(diǎn)的邊的條數(shù)（環(huán)計(jì)算兩次）稱為點(diǎn) v 的度數(shù)，簡稱為點(diǎn) v的 度 ，記為 dG (v)，簡記為 d(v)。 ，且 例如 ≌ 說明： (1) 兩個同構(gòu)的圖均有相同的結(jié)構(gòu)，沒有本質(zhì)上的差異 , 差異只是頂點(diǎn)和邊的名稱不同。邊集為空的圖稱為 空圖 。 簡單圖 非 簡單 圖 例 3 平凡圖 ● (3) 點(diǎn)集與邊集均為有限集合的圖稱為 有限圖 ，本書只討論有限圖。 (4) 既沒有環(huán)也沒有重邊的圖稱為 簡單圖 。例 4環(huán)孤立點(diǎn)v2 v3v1e1 e3二重邊e2（ 2）特殊點(diǎn)、邊 孤立點(diǎn)： 不與任何邊相關(guān)聯(lián)的點(diǎn)； 自環(huán)： 兩端點(diǎn)重合的邊； 重邊： 連接兩個相同頂點(diǎn)的邊的條數(shù)，叫做邊的 重?cái)?shù) 。 點(diǎn) v1與 v2 相鄰， v1與 v3不相鄰；邊 e1與 e2相鄰， e1與e3 不相鄰；點(diǎn) v1與邊 e1相關(guān)聯(lián)。 并稱 u 和 v 相鄰 ， u (或 v)與 e 相關(guān)聯(lián) 。 v1 v2 v3 v4 e1 e2 e3 e4 e5 例 2 設(shè) V = {v1,v2,v3,v4}， E = {e1,e2,e3,e4,e5}， 其中 e1= v1v2， e2 = v2v3， e3 = v2v3， e4 = v3v4， e5 = v4v4 則 G = (V, E) 是一個圖。 例 1 設(shè) V ={v1, v2, v3, v4}， E ={v1v2 , v1v2, v2v3 }，則 G = (V, E) 是一個 4階圖。 第一章 圖的基本概念 符號說明 : 圖 G 的頂點(diǎn)集也記為 V(G), 邊集也記為 E(G)。 電子科技大學(xué)數(shù)學(xué)科學(xué)學(xué)院 王也洲 167。 圖和簡單圖 一．圖的定義 定義 1 一個圖 G 定義為一個有序?qū)?(V, E)，記為 G = (V, E)，其中 （ 1） V是一個非空集合，稱為頂點(diǎn)集或點(diǎn)集，其元素稱為頂點(diǎn)或點(diǎn)； （ 2） E是由 V中的點(diǎn)組成的無序點(diǎn)對構(gòu)成的集合，稱為邊集，其元素稱為邊，且同一點(diǎn)對在 E 中可出現(xiàn)多次。圖G 的頂點(diǎn)數(shù)（或階數(shù)）和邊數(shù)可分別用符號 n(G) (或 |V(G)| ) 和 m(G)表示。 若用小圓點(diǎn)代表點(diǎn)，連線代表邊，則可將一個圖用“圖形”來表示 , 如 例 1 中的圖可表為 v1 v2 v3 v4 注 : 也可記邊 uv 為 e ，即 e = uv。 相關(guān)概念 : (1) 若邊 e = uv , 此時稱 u 和 v 是 e 的 端點(diǎn) 。若兩條邊有一個共同的端點(diǎn)，則稱這兩條 邊相鄰 。 這是一個 5 階圖。重?cái)?shù)大于 1的邊稱為重邊。其他所有的圖都稱為 復(fù)合圖。只有一個頂點(diǎn)而無邊的圖稱為 平凡圖 。 二、圖的同構(gòu) 定義 2 設(shè)有兩個圖 G1 = (V1, E1)和 G2 = (V2, E2)，若在其頂點(diǎn)集合之間存在雙射，即存在一一對應(yīng)的關(guān)系，使得邊之間有如下的關(guān)系：設(shè) 12uu? 12vv?1 1 1,u v V? 2 2 2,u v V? ，對應(yīng)關(guān)系為： 1 1 1 2 2 2 u v E u v E??， 11uv 22uv當(dāng)且僅當(dāng) 的重?cái)?shù)與 的重?cái)?shù)相同，則稱兩圖同構(gòu)，記為 G1≌ G2。 （ 2） 圖同構(gòu)的幾個必要條件： ① 頂點(diǎn)數(shù)相同； ② 邊數(shù)相同； ③ 度數(shù) 相等的頂點(diǎn)個數(shù)相同。 圖中 d (v1) = 5 d (v2) = 4 d (v3) = 3 d (v4) = 0 d (v5) = 2 v1 v2 v3 v4 v5 例 注： 該圖中各點(diǎn)的度數(shù) 之和等于 14，恰好 是邊數(shù) 7的 兩 倍 (3) 易證，圖的同構(gòu)關(guān)系是一個等價關(guān)系。 （ 4） 在圖的圖形表示中我們可以不給圖的點(diǎn)和邊標(biāo)上符號，稱這樣的圖為 非標(biāo)定（號）圖 ，否則稱為 標(biāo)定（號）圖 。 （ 5） 判定圖的同構(gòu)是很困難的，屬于 NP完全問題。 不誤解時我們也不嚴(yán)格區(qū)分標(biāo)定圖與非標(biāo)定圖。 證明 作映射 f : vi ? ui (i=1,2….10) ，易知該 映射為雙射。 例 判斷下面兩圖是否同構(gòu)。 這是因若同構(gòu)，則兩圖中唯一的與環(huán)關(guān)聯(lián)的兩個點(diǎn) u1 與 v1 一定相對應(yīng)，而 u1的兩個鄰接點(diǎn)與 v1的兩個鄰接點(diǎn)狀況不同（ u1鄰接有 4度點(diǎn)，而 v1 沒有）。 三、完全圖 ，偶圖 ，補(bǔ)圖 完全圖： 任意兩點(diǎn)均相鄰的簡單圖稱為完全圖，在同構(gòu)意義下， n 階完全圖只有一個，記為 Kn。 K2 K3 K4 具有二分類（ X, Y）的偶圖（或二部圖）： 是指該圖的點(diǎn)集可以分解為兩個（非空）子集 X 和 Y ，使得每條邊的一個端點(diǎn)在 X 中，另一個端點(diǎn)在 Y 中。 完全偶圖： 是指具有二分類（ X, Y）的簡單偶圖，其中 X的每個頂點(diǎn)與 Y 的每個頂點(diǎn)相連，若 |X|=m， |Y|=n，則這樣的偶圖記為 Km,n 例 K 3,3 K1,3 G1 G2 四個圖均為偶圖 。 （ a） （ b） 定理 1 若 n 階圖 G是自補(bǔ)的（即 ），則 n = 0, 1（ mod 4） GG?證明 因?yàn)?G是自補(bǔ)的，則 G和其補(bǔ)圖有同樣多的邊數(shù)，且邊數(shù) m(G) +m )(G2 )1( ?nn= m(Kn) = 從而 4)1()( ?? nnGm又因 G 的邊數(shù) m(G)是整數(shù)，故 n(n1)/4 為整數(shù)，即只能有n≡0（ mod 4） , 或 (n1) ≡0 （ mod 4）。 圖中 d (v1) = 5 d (v2) = 4 d (v3) = 3 d (v4) = 0 d (v5) = 2 v1 v2 v3 v4 v5 例如 注： 該圖中各點(diǎn)的度數(shù) 之和等于 14，恰好 是邊數(shù) 7的 兩 倍 對任意的有 m條邊的圖 G = (V, E)。 ? ? ? V v m v d 2 ) ( （ ） 定理 2 （握手定理）： 注： 該定理也稱為圖論第一定理，是由歐拉提出的。 奇 (偶 )點(diǎn) : 奇 (偶 )數(shù)度的頂點(diǎn) 相關(guān)術(shù)語和記號 ? ?G? 圖 G的頂點(diǎn)的最小度 ? ?G? 圖 G的頂點(diǎn)的最大度 k正則圖 : 每個點(diǎn)的度均為 k 的 簡單圖 例如 ,完全圖和完全偶圖 Kn,n均是正則圖。 從而推知 也為偶。 ? ? 1 ) ( V v v d 證明 任給圖 G = (V, E)， 設(shè) G 有 m 條邊，令 V1={ v | v ??V ,d(v) 為奇數(shù) }, V2={ v | v ??V ,d(v) 為偶數(shù) } 顯然， V1 ∪ V2= V,V1∩ V2=Φ 。 證明 : 將集會中的人作為點(diǎn)，若兩個人握手則對應(yīng)的點(diǎn)聯(lián)線，則得簡單圖 G。于是，問題轉(zhuǎn)化為證明“圖 G 中度數(shù)為奇的點(diǎn)的個數(shù)為偶數(shù)”，這正是 推論 1的結(jié)論。 證明 設(shè) G是 k正則圖，若 k為奇數(shù)，則由推論 1知正則圖 G的點(diǎn)數(shù)必為偶數(shù)。 它是刻畫圖的特 征的重要“拓?fù)洳蛔兞俊薄? 圖劃分 : 正整數(shù) k的一個劃分 (d1, d2,… , dn)能成為某簡 單圖的度序列的 k的劃分 . 顯然，若正整數(shù) k 有圖劃分，則 k 必須是偶數(shù) 例 偶數(shù) 4有五種劃分： 4， 3+1， 2+2， 1+1+2， 1+1+1+1 但屬于圖劃分的卻只有兩種 : 2+1+1 1+1+1+1 對一個非負(fù)整數(shù)組 (d1, d2,… , dn)， mdni i21??? , 若 存在一個簡單圖 G，以它為度序列，則稱這個數(shù)組是 可圖 的 。 例 試判斷下列非負(fù)整數(shù)組 Π 是否可圖 ? ? ?5 5 3 3 2 2 2??? ?4 2 2 1 1 2???解 利用定理 5可得下列非負(fù)整數(shù)組 ? ?1 4 2 2 2 1 1??? ?1 1 1 1 0 1???? ?1 1 1 1 0 1???因 是可圖的 所以 也是可圖的 : ? ?5 5 3 3 2 2 2??v3 v4 v5 v1 v6 v2