【正文】 電子科技大學(xué)應(yīng)用數(shù)學(xué)學(xué)院 張先迪 圖論簡介 現(xiàn)實(shí)生活中許多問題都可歸結(jié)為由點(diǎn)和線組成的圖形的問題，例如，鐵路交通圖，公路交通圖，市區(qū)交通圖，自來水管網(wǎng)系統(tǒng)，甚至電路圖在研究某些問題時(shí)也可簡化為由點(diǎn)和線組成的圖形，如： 圖論就是研究這些由點(diǎn)和線組成的圖形的問題 圖論起源于 18世紀(jì)，是一門較為年青的數(shù)學(xué)分支。但在歷史上遺留了許多著名的圖論問題，例如： 18世紀(jì)東普魯士有一個(gè)城市稱為個(gè)普尼斯堡，它位于普雷格爾河畔，河中有兩個(gè)小島，通過七座橋彼此相聯(lián)（如圖）。當(dāng)時(shí)有人提出： 能否從某個(gè)地點(diǎn)出發(fā)經(jīng)過每個(gè)橋一次且僅一次然后返回出發(fā)點(diǎn)？ A B C D ABCDEuler的 解： ABCDABCDEuler 證 明了該 問題無 解，這 是圖論 的第一扁 論文。 因此， Euler 是圖論 的創(chuàng)始 人。2. Hamilton 周游世界問題 1859年 Hamilton 提出這樣一個(gè)問題：一個(gè)正十二面體有 20個(gè)頂點(diǎn)，它們代表世界上 20個(gè)重要城市。正十二面體的每個(gè)面均為五邊形，若兩個(gè)頂點(diǎn)之間有邊相連，則表示相應(yīng)的城市之間有航線相通。 Hamilton 提出 “ 能否從某城市出發(fā)經(jīng)過每個(gè)城市一次且僅一次然后返回出發(fā)點(diǎn)？ ” 1840年數(shù)學(xué)家茂比烏斯（ M246。bius） 提出一個(gè)猜想： 任何平面地圖，總可以把它的一個(gè)國家用四種顏色的一種著染，使相鄰國家著不同色。 這就是著名的 四色猜想 。如： 1890年希五德（ Heawood） 指出“ 4換為 5”猜想成立。 1976年兩位數(shù)學(xué)家在三臺百萬次的電子計(jì)算機(jī)上花了 1200小時(shí)證明了猜想成立。猜想成為定理。 3. 四色問題 4. 中國郵路問題 1962年中國數(shù)學(xué)家管梅谷提出：一個(gè)郵遞員從郵局出發(fā)遞送郵件，要求對他所負(fù)責(zé)的轄區(qū)的每條街至少走一次，問如何選取路程最短 的路線？這個(gè)問題稱為中國郵路問題。 該問題可用專門的算法來求解。 圖論的應(yīng)用范圍很廣，它不但能應(yīng)用于自然科學(xué)，也能應(yīng)用于社會科學(xué)。它非但廣泛應(yīng)用于電信網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、運(yùn)輸能力開關(guān)理論、編碼理論、控制論、反饋理論、隨機(jī)過程、可靠性理論、化學(xué)化合物的辨認(rèn)、計(jì)算機(jī)的程序設(shè)計(jì)、故障診斷、人工智能、印刷電路板的設(shè)計(jì)、圖案識別、地圖著色、情報(bào)檢索，也應(yīng)用于語言學(xué)、社會結(jié)構(gòu)、經(jīng)濟(jì)學(xué)、運(yùn)籌學(xué)、遺傳學(xué)等。 圖論作為一個(gè)數(shù)學(xué)分支，有一套完整的體系和廣泛的內(nèi)容，在這里我們只準(zhǔn)備介紹圖論的初步知識，其目的是今后在其它有關(guān)學(xué)科的學(xué)習(xí)和研究時(shí)，可以用圖論的基本知識作為工具。 167。 圖和簡單圖 一．圖的定義 定義 1 一個(gè)圖 G 定義為一個(gè)有序?qū)?(V, E)，記為 G = (V, E)，其中 （ 1） V是一個(gè)非空集合，稱為頂點(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)集也記為 V(G), 邊集也記為 E(G)。圖G 的頂點(diǎn)數(shù)（或階數(shù)）和邊數(shù)可分別用符號 n(G) (或 |V(G)| ) 和 m(G)表示。 例 1 設(shè) V ={v1, v2, v3, v4}， E ={v1v2 , v1v2, v2v3 }，則 G = (V, E) 是一個(gè) 4階圖。 若用小圓點(diǎn)代表點(diǎn)，連線代表邊，則可將一個(gè)圖用“圖形”來表示 , 如 例 1 中的圖可表為 v1 v2 v3 v4 注 : 也可記邊 uv 為 e ，即 e = uv。 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) 是一個(gè)圖。 相關(guān)概念 : (1) 若邊 e = uv , 此時(shí)稱 u 和 v 是 e 的 端點(diǎn) 。 并稱 u 和 v 相鄰 ， u (或 v)與 e 相關(guān)聯(lián) 。若兩條邊有一個(gè)共同的端點(diǎn)，則稱這兩條 邊相鄰 。 點(diǎn) v1與 v2 相鄰， v1與 v3不相鄰；邊 e1與 e2相鄰， e1與e3 不相鄰；點(diǎn) v1與邊 e1相關(guān)聯(lián)。 這是一個(gè) 5 階圖。例 4環(huán)孤立點(diǎn)v2 v3v1e1 e3二重邊e2（ 2）特殊點(diǎn)、邊 孤立點(diǎn)： 不與任何邊相關(guān)聯(lián)的點(diǎn)； 環(huán)： 兩端點(diǎn)重合的邊； 重邊： 連接兩個(gè)相同頂點(diǎn)的邊的條數(shù)，叫做邊的 重?cái)?shù) 。重?cái)?shù)大于 1的邊稱為重邊。 (4) 既沒有環(huán)也沒有重邊的圖稱為 簡單圖 。其他所有的圖都稱為 復(fù)合圖。 簡單圖 非 簡單 圖 例 3 平凡圖 ● (3) 點(diǎn)集與邊集均為有限集合的圖稱為 有限圖 ，本書只討論有限圖。只有一個(gè)頂點(diǎn)而無邊的圖稱為 平凡圖 。邊集為空的圖稱為 空圖 。 二．圖的同構(gòu) 定義 2 設(shè)有兩個(gè)圖 G1 = (V1, E1)和 G2 = (V2, E2)，若在其頂點(diǎn)集合之間存在雙射，即存在一一對應(yīng)的關(guān)系，使得邊之間有如下的關(guān)系：設(shè) 1 1 1u v E? 2 2 2u v E? 11uv 22uv當(dāng)且僅當(dāng) ， ；且 的重?cái)?shù)與 的重?cái)?shù)相同，則稱兩圖同構(gòu)，記為 G1≌ G2。 12uu? 12vv?1 1 1,u v V? 2 2 2,u v V? ，對應(yīng)為： 例如 ≌ 說明： (1) 兩個(gè)同構(gòu)的圖均有相同的結(jié)構(gòu)，沒有本質(zhì)上的差異 , 差異只是頂點(diǎn)和邊的名稱不同。 （ 2） 圖同構(gòu)的幾個(gè)必要條件： ① 頂點(diǎn)數(shù)相同； ② 邊數(shù)相同； ③ 度數(shù) 相等的頂點(diǎn)個(gè)數(shù)相同。 定義 設(shè) v為 G 的頂點(diǎn)， G 中與 v 為端點(diǎn)的邊的條數(shù)（環(huán)計(jì)算兩次）稱為點(diǎn) v 的度數(shù)，簡稱為點(diǎn) v的 度 ，記為 dG (v)，簡記為 d(v)。 圖中 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)系是一個(gè)等價(jià)關(guān)系。該關(guān)系將所有的圖的集合，劃分為一些等價(jià)類，即相互同構(gòu)的圖作成同一個(gè)等價(jià)類。 （ 3） 在圖的圖形表示中我們可以不給圖的點(diǎn)和邊標(biāo)上符號，稱這樣的圖為 非標(biāo)定（號）圖 ，否則稱為 標(biāo)定（號）圖 。 非標(biāo)定圖實(shí)際上是代表一類相互同構(gòu)的圖。 不誤解時(shí)我們也不嚴(yán)格區(qū)分標(biāo)定圖與非標(biāo)定圖。 （ 4） 判定圖的同構(gòu)是很困難的，屬于 NP完全問題。對于規(guī)模不大的兩個(gè)圖，判定其是否同構(gòu)，可以采用觀察加推證的方法。 例 證明下面兩圖同構(gòu)。 證明 作映射 f : vi ? ui (i=1,2….10) ，易知該 映射為雙射。 ( a ) v 1 v 2 v 3 v 4 v 5 v 6 v 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)。 u1 v1 解 兩圖不同構(gòu)。 這是因若同構(gòu)，則兩圖中唯一的與環(huán)關(guān)聯(lián)的兩個(gè)點(diǎn) u1 與 v1 一定相對應(yīng)，而 u1的兩個(gè)鄰接點(diǎn)與 v1的兩個(gè)鄰接點(diǎn)狀況不同（ u1鄰接有 4度點(diǎn)，而 v1 沒有）。 所以，兩圖不同構(gòu)。 三．完全圖 ，偶圖 ，補(bǔ)圖 完全圖： 任意兩點(diǎn)均相鄰的簡單圖稱為完全圖，在同構(gòu)意義下， n 階完全圖只有一個(gè)，記為 Kn。 例如 K2, K3, K4分別為如下圖所示 。 K2 K3 K4 具有二分類（ X, Y）的偶圖（或二部圖）： 是指該圖的點(diǎn)集可以分解為兩個(gè)（非空）子集 X 和 Y ，使得每條邊的一個(gè)端點(diǎn)在 X 中，另一個(gè)端點(diǎn)在 Y 中。 ,mnK。 完全偶圖： 是指具有二分類（ X, Y）的簡單偶圖，其中 X的每個(gè)頂點(diǎn)與 Y 的每個(gè)頂點(diǎn)相連，若 |X|=m， |Y|=n，則這樣的偶圖記為 Km,n 例 K 3,3 K1,3 G1 G2 四個(gè)圖均為偶圖 。 K1,3 , K3,3為完全偶圖 例 偶圖 不是偶圖 ? ?1 ,E u v u v u v V? ? ?簡單 圖 G 的 補(bǔ)圖 : 設(shè) G =（ V, E），則圖 H =（ V， E1\E）稱為 G 的補(bǔ)圖，記為 , 其中集合 HG?例如 , 下圖中的 (a)， (b)兩圖是互補(bǔ)的。 （ 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）。 四． 頂點(diǎn)的度（續(xù)） , 度序列 前已定義： 設(shè) v為 G 的頂點(diǎn)， G 中與 v 為端點(diǎn)的邊的條數(shù)（環(huán)計(jì)算兩次）稱為點(diǎn) v 的度數(shù)，簡稱為點(diǎn) v的 度 ，記為 dG (v)， 簡記為 d(v)。 圖中 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)。 有 證明 因圖 G 的任一條邊均有兩個(gè)端點(diǎn) (可以相同 )，在計(jì)算度時(shí)恰被計(jì)算兩次 (每個(gè)端點(diǎn)各被計(jì)算了一次 )，所以各點(diǎn)的度數(shù)之和恰好為邊數(shù)的兩倍，即 () 式成立。 ? ? ? V v m v d 2 ) ( （ ） 定理 2 （握手定理）： 注： 該定理也稱為圖論第一定理，是由歐拉提出的。歐拉一身發(fā)表論文 886篇，著作 90部。 奇 (偶 )點(diǎn) : 奇 (偶 )數(shù)度的頂點(diǎn) 相關(guān)術(shù)語和記號 ? ?G? 圖 G的頂點(diǎn)的最小度 ? ?G? 圖 G的頂點(diǎn)的最大度 k正則圖 : 每個(gè)點(diǎn)的度均為 k 的 簡單圖 例如 ,完全圖和完全偶圖 Kn,n均是正則圖。 推論 1 任意圖中，奇點(diǎn)的個(gè)數(shù)為 偶數(shù)。 從而推知 也為偶。而和式中每個(gè) d(v)均為奇，故和 式中的被加項(xiàng)的項(xiàng)數(shù)應(yīng)為偶，這表明 G 中度為奇數(shù)的點(diǎn)有偶數(shù)個(gè)。 ? ? 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=Φ 。 由握手定理 ? ? V v v d ) ( ? ? 1 ) ( V v v d ? ? 2 ) ( V v v d 2m = = + （ 1） ? ? 2 ) ( V v v d （ 1）式中 2m為偶， 也為偶（因其中每個(gè) d(v)為偶）， 例 7 證明在任意一次集會中和奇數(shù)個(gè)人握手的人的個(gè)數(shù)為偶數(shù)個(gè)。 證明 : 將集會中的人作為點(diǎn)，若兩個(gè)人握手則對應(yīng)的點(diǎn)聯(lián)線，則得簡單圖 G。 這樣 G 中點(diǎn) v的度對應(yīng)于集會中與 v握手的人的個(gè)數(shù)。