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