離散數(shù)學(xué)及其應(yīng)用 課件 第4章圖論

《離散數(shù)學(xué)及其應(yīng)用》第4章圖論目錄4.1圖的基本概念4.2通路與回路4.3圖的連通性4.4圖的矩陣表示4.5歐拉圖和哈密爾頓圖4.6樹圖論是以圖為研究對象的數(shù)學(xué)分支。圖論中的圖指的是一些結(jié)點以及連接這些點的線的總體。通常用結(jié)點代表事物，連接兩結(jié)點的線代表事物間的關(guān)系。圖論研究的是事物對象在上述表示法中具有的特征與性質(zhì)，即研究圖的基本概念和性質(zhì)、圖的理論及其應(yīng)用。在自然界和人類社會的實際生活中，用圖來描述和表示某些事物之間的關(guān)系既方便又直觀。例如，國家用頂點表示，有外交關(guān)系的國家用線連接，于是世界各國之間的外交關(guān)系就用一個圖形描述出來了。另外我們常用工藝流程圖來描述某項工程中各工序之間的先后關(guān)系，用網(wǎng)絡(luò)圖來描述某通信系統(tǒng)中各通信站之間信息傳遞關(guān)系，用開關(guān)電路圖來描述集成電路（integratedcircuit，IC）中各元件電路導(dǎo)線連接關(guān)系，等等。最早關(guān)于圖論的論文可以追溯到1736年，當(dāng)時瑞士數(shù)學(xué)家萊昂哈德·歐拉（LeonhardEuler）發(fā)表了一篇論文，給出了圖論中的一個一般性的理論，其中包括現(xiàn)在被稱為哥尼斯堡七橋問題的解。其背景是一個非常有趣的問題：18世紀，東普魯士的哥尼斯堡城中的一個公園里，有7座橋?qū)⑵绽赘駹枺≒regel）河中兩個島及島與河岸連接起來，該城的居民喜歡在星期日繞城散步，如何從河岸或島上的某一個位置出發(fā)，7座橋正好各經(jīng)過一次，最后回到出發(fā)地。這就是有名的哥尼斯堡七橋問題（見圖4.0.1）。哥尼斯堡七橋問題看起來不復(fù)雜，因此，立刻吸引了眾多人的注意。有人嘗試了很多次，然而始終沒有成功。歐拉1707年4月15日生于瑞士巴塞爾，1783年9月18日卒于俄國圣彼得堡。他生于牧師家庭。15歲在巴塞爾大學(xué)獲學(xué)士學(xué)位，翌年得碩士學(xué)位。1727年，歐拉應(yīng)圣彼得堡科學(xué)院的邀請到俄國。1731年接替丹尼爾·伯努利成為物理教授。他以旺盛的精力投入研究，在俄國的14年中，他在分析學(xué)、數(shù)論和力學(xué)方面作了大量出色的工作。1741年受普魯士腓特烈大帝的邀請到柏林科學(xué)院工作，達25年之久。在柏林期間他的研究內(nèi)容更加廣泛，涉及行星運動、剛體運動、熱力學(xué)、彈道學(xué)、人口學(xué)，這些工作和他的數(shù)學(xué)研究相互推動。歐拉這個時期在微分方程、曲面微分幾何以及其他數(shù)學(xué)領(lǐng)域的研究都是開創(chuàng)性的。1766年他又回到了圣彼得堡。歐拉小時候他就特別喜歡數(shù)學(xué)，不滿10歲就開始自學(xué)《代數(shù)學(xué)》。這本書連他的幾位老師都沒讀過?？尚W拉卻讀得津津有味，遇到不懂的地方，就用筆作個記號，事后再向別人請教。1720年，13歲的歐拉靠自己的努力考入了巴塞爾大學(xué)，得到當(dāng)時最有名的數(shù)學(xué)家約翰·伯努利（JohannBernoulli，1667-1748年）的精心指導(dǎo)。這在當(dāng)時是個奇跡，曾轟動了數(shù)學(xué)界。小歐拉是這所大學(xué)，也是整個瑞士大學(xué)校園里年齡最小的學(xué)生。歐拉在論文中給出了該問題的數(shù)學(xué)模型，用4個點代表4個被河隔開的陸地（兩岸和島嶼），把橋表示為連接兩個陸地之間的邊，則得到圖4.0.1所示的圖，從而問題變?yōu)槿绾螐膱D中的某個點出發(fā)，經(jīng)過所有的邊正好一次，最后回到這個點。在研究這個圖的基礎(chǔ)上，歐拉在論文中證明了該七橋問題無解，并且給出了一些規(guī)律性的理論。把實際問題抽象成點和邊構(gòu)成的圖進行研究，標(biāo)志著圖論研究的開始。點邊哥尼斯堡七橋問題與歐拉圖:哥尼斯堡七橋問題就是要求在這個圖中走一條歐拉回路，由于4個頂點都是奇度頂點，所以該問題無解。4.1圖的基本概念4.1圖的基本概念

4.1圖的基本概念

圖4.1.1無向圖G說明

元素可以重復(fù)出現(xiàn)的集合稱作多重集合。某元素重復(fù)出現(xiàn)的次數(shù)稱作該元素的重復(fù)度。例如，在多重集合{a，a，b，b，b，b，c，c，c，d，e，e，e，e，e，e}中，a、b、c、d、e的重復(fù)度分別為2、4、3、1、6。從多重集合的角度考慮，無元素重復(fù)出現(xiàn)的集合是各元素重復(fù)度均為1的多重集。4.1圖的基本概念

圖4.1.2有向圖D4.1圖的基本概念與無向圖和有向圖的定義相關(guān)的概念和規(guī)定：（1）圖（graph）：無向圖和有向圖統(tǒng)稱作圖，但有時也常把無向圖簡稱作圖。通常用G表示無向圖，用D表示有向圖，有時也用G泛指圖（無向的和有向的）。用V(G)和E(G)分別表示無向圖G的頂點集和邊集，則|V(G)|和|E(G)|分別是G的頂點數(shù)和邊數(shù)。用V(D)和E(D)分別表示有向圖D的頂點集和邊集，則|V(D)|和|E(D)|分別是有向圖D的頂點數(shù)和邊數(shù)。圖4.1.1中|V(G)|=5和|E(G)|=7，圖4.1.2中|V(D)|=4和|E(D)|=7。（2）階（order）：圖的頂點數(shù)稱作圖的階。圖4.1.1中圖G的階數(shù)為5，圖4.1.2中圖D的階數(shù)為4。（3）n階圖（order-ngraph）：n個頂點的圖稱作n階圖。圖4.1.1為5階圖，圖4.1.2為4階圖。（4）(n，m)圖：n個頂點，m條邊的圖，有時也稱為(n，m)圖。圖4.1.1為(5，7)圖，圖4.1.2為(4，7)圖。圖4.1.1無向圖G圖4.1.2有向圖D4.1圖的基本概念圖4.1.310階零圖N10圖4.1.4零圖應(yīng)用舉例（目標(biāo)檢測）（5）零圖（nullgraph）：一條邊也沒有的圖稱作零圖。n階零圖記作Nn。圖4.1.3為10階零圖。圖4.1.4為含有三種不同稀疏程度的點簇圖，圖中黑色像素點可以看做一系列頂點集，頂點與頂點之間沒有邊的連接，也可視為一種零圖。（6）平凡圖（trivialgraph）：1階零圖N1稱作平凡圖。平凡圖只有一個頂點，沒有邊。(1，0)圖是平凡圖。（7）空圖（emptygraph）：在圖的定義中規(guī)定頂點集V為非空集，但在圖的運算中可能產(chǎn)生頂點集為空集的運算結(jié)果，為此規(guī)定頂點集為空集的圖為空圖，并將空圖記作?。4.1圖的基本概念（8）標(biāo)定圖（labeledgraph）和非標(biāo)定圖（unlabeledgraph）：當(dāng)用圖形表示圖時，如果給每一個頂點和每一條邊指定一個符號（字母或數(shù)字，字母還可以帶下標(biāo)），稱這樣的圖為標(biāo)定圖，否則稱作非標(biāo)定圖。圖4.1.5為標(biāo)定圖，圖4.1.6為非標(biāo)定圖。圖4.1.5標(biāo)定圖圖4.1.6非標(biāo)定圖4.1圖的基本概念（9）基圖（basegraph）：將有向圖的各條有向邊改成無向邊后得到的無向圖，稱作這個有向圖的基圖。圖4.1.7所示有向圖D的基圖如圖4.1.8所示。圖4.1.7有向圖D圖4.1.8有向圖D的基圖

圖4.1.5標(biāo)定圖基圖環(huán)4.1圖的基本概念

圖4.1.7有向圖D圖4.1.5標(biāo)定圖孤立點孤立邊4.1圖的基本概念

圖4.1.9賦權(quán)圖（總權(quán)值數(shù)27）2權(quán)值4.1圖的基本概念

圖4.1.10無向圖G4.1圖的基本概念定義4.1.3

在無向圖中，如果關(guān)聯(lián)一對頂點的無向邊多于1條，則稱這些邊為平行邊（paralleledges），平行邊的條數(shù)稱作重數(shù)。在有向圖中，如果關(guān)聯(lián)一對頂點的有向邊多于1條，并且這些邊的始點與終點相同（也就是它們的方向相同），則稱這些邊為平行邊。含平行邊的圖稱作多重圖（multigraph），既不含平行邊也不含環(huán)的圖稱作簡單圖（simplegraph）。在圖4.1.11中，e2和e3是平行邊，e5和e8是平行邊，e6和e1不是平行邊。圖4.1.11不是簡單圖，圖4.1.10是簡單圖。圖4.1.11有向圖D（多重圖）圖4.1.10無向圖G（簡單圖）平行邊4.1圖的基本概念

4.1圖的基本概念圖4.1.12中，d(v2)=4，d(v5)=6（環(huán)提供2度）。在圖4.1.13中，d+(v2)=1，d-(v2)=2，d(v2)=1+2=3，v5為懸掛頂點，e2為懸掛邊。圖4.1.12無向圖G圖4.1.13有向圖D

看成一個大頂點V1懸掛頂點懸掛邊4.1圖的基本概念定理4.1.1

握手定理（handshakingtheorem）

無向圖G中，所有頂點的度數(shù)和等于邊數(shù)的2倍。在圖4.1.12中，共5個頂點、9條邊，d(v1)=2，d(v2)=4，d(v3)=3，d(v4)=3，d(v5)=6，所有頂點的度數(shù)和等于18，正好是邊數(shù)的2倍。定理4.1.2

有向圖中，所有頂點的入度之和與所有頂點的出度之和都等于邊數(shù)，且所有頂點的度數(shù)之和等于邊數(shù)的2倍。在圖4.1.13中，共5個頂點，8條邊，所有頂點的出度之和與入度之和都等于8。推論

任何圖（無向圖或有向圖）中，奇度頂點的個數(shù)是偶數(shù)。圖4.1.12無向圖G圖4.1.13有向圖D4.1圖的基本概念

圖4.1.12無向圖G圖4.1.13有向圖D4.1圖的基本概念

4.1圖的基本概念圖4.1.14分別示意了幾種常見的無向完全圖。圖4.1.15為1階、2階、3階有向完全圖。圖4.1.16為1階、2階、3階、4階競賽圖。圖4.1.14無向完全圖圖4.1.15有向完全圖圖4.1.16競賽圖4.1圖的基本概念

圖4.1.175階2-正則圖圖4.1.1810階3-正則圖4.1圖的基本概念

圖4.1.19二部圖圖4.1.20完全二部圖K2,3圖4.1.21完全二部圖K3,34.1圖的基本概念

在圖4.1.22中，取V1={v1，v2，v3}，圖(b)是圖(a)的V1導(dǎo)出的子圖。取E1={e1，e3}，圖(c)是圖(a)的E1導(dǎo)出的子圖。圖(e)和圖(f)都為圖(d)的子圖，但圖(f)是圖(d)的導(dǎo)出的子圖而圖(e)不是，圖(e)為圖(d)的生成子圖而圖(f)不是。圖4.1.22導(dǎo)出子圖與生成子圖(a)(b)(c)(d)(e)(f)4.1圖的基本概念

(a)(b)(c)(d)圖4.1.23

圖及其補圖4.1圖的基本概念

4.1圖的基本概念在圖4.1.24中，設(shè)圖(a)中圖為G，則圖(b)為G-e5，圖(c)為G-{e1，e4}，圖(d)為G-v5，圖(e)為G-{v4，v5}，而圖(f)為G\e5。圖4.1.24刪除邊、刪除頂點、邊的收縮4.1圖的基本概念圖重點關(guān)注的是頂點與頂點的鄰接關(guān)系，不在意頂點的位置和連線的形狀。對于給定的圖，圖的表現(xiàn)形式可能不唯一。如果將圖的頂點放置在不同的位置，邊用不同形狀的弧線或直線表示，則可以得到同一個圖的不同形式的圖形。因此，看起來完全不同的圖形，可能表示著同一個圖。為了描述看起來不同而其結(jié)構(gòu)完全相同的圖，引入同構(gòu)的概念。如圖4.1.25所示，雖然四個圖形的形式各不相同，但它們表示同一個圖。圖4.1.25形式不同的圖4.1圖的基本概念

(a)(b)(c)圖4.1.26圖的同構(gòu)（彼得松圖）

4.2通路與回路4.2通路與回路

4.2通路與回路

4.2通路與回路如圖4.2.1所示，在無向圖G中，則有通路Γ(v1，v3)=(v1，e1，v1，e3，v4，e3，v1，e2，v2，e5，v4，e7，v3)，長度為6；回路Γ(v1，v1)=(v1，e1，v1，e3，v4，e3，v1，e2，v2，e4，v4，e3，v1)，長度為6；簡單通路Γ(v1，v3)=(v1，e1，v1，e3，v4，e4，v2，e5，v4，e7，v3)，長度為5；簡單回路Γ(v1，v1)=(v1，e1，v1，e3，v4，e4，v2，e2，v1)，長度為4；初級通路Γ(v1，v3)=(v1，e3，v4，e4，v2，e6，v3)，長度為3；初級回路Γ(v1，v1)=(v1，e3，v4，e7，v3，e6，v2，e2，v1)，長度為4，該回路是偶圈。然而，(v1，e4，v4，e6，v3，e2，v2，e3，v3)不是通路。圖4.2.1無向圖G4.2通路與回路如圖4.2.2所示，在有向圖D中，則有通路Γ(v1，v2)=(v1，e5，v3，e6，v4，e7，v1，e5，v3，e3，v2)，長度為5；回路Γ(v1，v1)=(v1，e5，v3，e6，v4，e7，v1，e5，v3，e4，v1)，長度為5；簡單通路Γ(v1，v2)=(v1，e5，v3，e3，v2，e2，v2)，長度為3；簡單回路Γ(v3，v3)=(v3，e3，v2，e2，v2，e1，v1，e5，v3)，長度為4；初級通路Γ(v1，v2)=(v1，e5，v3，e3，v2)，長度為2；初級回路Γ(v1，v1)=(v1，e5，v3，e3，v2，e1，v1)，長度為3，該回路是奇圈。圖4.2.2有向圖D4.2通路與回路

4.2通路與回路例4.2.1無向完全圖K3（見圖4.2.3）的頂點依次標(biāo)定為v1、v2和v3。在定義意義下，K3中有多少個不同的圈（初級回路）？圖4.2.3無向完全圖解

同構(gòu)意義下，K3中只有一個長度為3的圈（初級回路）。但在定義意義下，不同起點（或不同終點）的圈是不同的，頂點間排列順序不同的圈也看成是不同的，因而K3中有6個不同的長度都為3的圈：v1v2v3v1，v1v3v2v1，v2v1v3v2，v2v3v1v2，v3v1v2v3，v3v2v1v3。如果僅僅考慮起點（或終點）的差異，不考慮順時針和逆時針的差異，有3種不同的圈，長度都是3：v1v2v3v1，v2v3v1v2，v3v1v2v3。4.3圖的連通性4.3圖的連通性

4.3圖的連通性圖4.3.1為連通圖，圖4.3.2為非連通圖。圖4.3.1連通圖圖4.3.2非連通圖

4.3圖的連通性圖中兩個頂點之間的通路可能不止一條，但是，總是存在長度最短的一條，即最短通路（最短路徑）。

4.3圖的連通性例4.3.1

（擺渡問題）一個人帶著一條狗、一只羊和一筐蔬菜來到河的南岸。河邊的小船一次只能載著人和他帶的一樣?xùn)|西（狗、羊或菜）。而在人不在場的情況下，狗和羊，羊和菜不能放在一塊，因為狗要咬羊，羊會吃菜。這個人怎樣才能把他的三樣?xùn)|西安全地運到河對岸（北岸）？至少需要來回幾次？解

用頂點表示可能的狀況。例如，（人狗羊菜南，空北）表示人狗羊菜都在南岸，北岸什么也沒有；（人羊南，狗菜北）表示人羊在南岸，狗菜在北岸。兩個頂點之間有一條邊當(dāng)且僅當(dāng)一次擺渡使表示的一種狀態(tài)變成另一種狀態(tài)，如圖4.3.3所示。于是，從（人狗羊菜南，空北）到（空南，人狗羊菜北）的一條通路給出人把他的三樣?xùn)|西安全運到河對岸的一種方法，而這兩點之間的距離是至少需要來回的次數(shù)。如圖4.3.3所示，（人狗羊菜南，空北）（狗菜南，人羊北）（人狗菜南，羊北）（菜南，人狗羊北）（人羊菜南，狗北）（羊南，人狗菜北）（人羊南，狗菜）（空南，人狗羊菜北）是一條短程線（實線路徑），距離為7。因此人至少要擺渡7次，7次擺渡過程如下：（1）帶羊到北岸；（2）空手回到南岸；（3）帶狗到北岸；（4）帶羊回到南岸；（5）帶菜到北岸；（6）空手回到南岸；（7）帶羊到北岸。圖4.3.3擺渡路徑4.3圖的連通性另一條短程線（含虛線路徑）是（人狗菜羊南，空北）（狗菜南，人羊北）（人狗菜南，羊北）（狗南，人羊菜北）（人狗羊南，菜北）（羊南，人狗菜北）（人羊南，狗菜北）（空南，人狗羊菜北），擺渡方案與前面的不同，距離也是7次。（1）人帶著羊到北岸；（2）人空手回到南岸；（3）人帶著菜到北岸；（4）人帶著羊回到南岸；（5）人帶著狗到北岸；（6）人空手回到南岸；（7）人帶羊到北岸。圖4.3.3擺渡路徑4.3圖的連通性下面討論無向圖的連通程度。刪除圖中的頂點和邊常常會影響圖的連通性。例如，將連通圖圖4.3.4中的邊e5刪除，得到非連通圖，如圖4.3.5所示。圖4.3.4連通圖圖4.3.5非連通圖4.3圖的連通性

圖4.3.6無向圖G圖4.3.7無向圖G刪除{v1，v3}圖4.3.8無向圖G刪除{v2}4.3圖的連通性

圖4.3.9無向圖4.3圖的連通性例4.3.2

在圖4.3.10(a)中，頂點5、6、10是割點，頂點子集{1，4}是點割集，而頂點子集{1，9}、{7，8}、{4，5}、{1，3，4}不是點割集。邊{5，6}是橋，邊子集{(1，2)，(2，4)}、{(6，9)，(6，10)}、{(1，2)，(1，3)，(1，5)}是割集，而邊子集{(3，4)，(4，5)}，{(1，3)，(1，5)，(4，5)}，{(6，10)，(9，10)，(10，11)}不是邊割集。在圖4.3.10(b)中，頂點3、4是割點，頂點子集{2，8}、{5，7}是點割集，而頂點子集{1，9}、{4，5}、{1，2，8}不是點割集。邊{3，4}是橋，邊子集{(2，3)，(3，8)}、{(4，5)，(4，7)}、{(1，2)，(2，9)，(2，8)，(3，8)}是邊割集，而邊子集{(3，4)，(4，5)}、{(2，3)，(2，8)，(3，8)}、{(1，2)，(2，8)，(1，8)}不是邊割集。(a)(b)圖4.3.10無向圖的點割集、邊割集、割點和割邊4.3圖的連通性

圖4.3.9無向圖4.3圖的連通性

圖4.3.9無向圖4.3圖的連通性

4.3圖的連通性

4.3圖的連通性

圖4.3.11強連通圖、單向連通圖和弱連通圖4.3圖的連通性定理4.3.2

一個n階簡單有向圖D=<V，E>是強連通圖，當(dāng)且僅當(dāng)D中包含一條經(jīng)過每個頂點有向回路。定理4.3.3

一個n階簡單有向圖D=<V，E>是單向連通圖，當(dāng)且僅當(dāng)D中包含一條經(jīng)過每個頂點至少一次的通路。4.4圖的矩陣表示4.4圖的矩陣表示事物之間的聯(lián)系可用圖來表示，用圖進行表示的優(yōu)點是直觀且形象。然而，當(dāng)頂點和邊比較多時，用圖進行表示反而會顯得混亂。此外，圖不但可以用集合來定義，還可以用矩陣來表示。用矩陣表示圖便于用代數(shù)方法研究圖的性質(zhì)，構(gòu)造算法，也便于用計算機存儲和處理圖。為了用矩陣表示圖，必須指定頂點或邊的順序，使其成為標(biāo)定圖，以確定矩陣元素和大小。本節(jié)主要討論圖的三種矩陣：關(guān)聯(lián)矩陣、鄰接矩陣和可達矩陣。關(guān)聯(lián)矩陣描述的是點與邊的鄰接情況。鄰接矩陣描述的是頂點與頂點之間的關(guān)系?？蛇_矩陣描述的是圖的連通情況。4.4圖的矩陣表示

圖4.4.1無向圖G

v1v2v3v4v5e1e2e3e4e5e64.4圖的矩陣表示

4.4圖的矩陣表示

有向圖D的關(guān)聯(lián)矩陣M(D)有以下幾個性質(zhì)：（1）每列恰好有一個1和一個-1，說明每條有向邊有一個起點和一個終點；（2）矩陣的所有元素和為0，即-1的個數(shù)等于1的個數(shù)，都等于邊數(shù)m；（3）第i行中，1的個數(shù)等于頂點vi的出度d+(vi)，-1的個數(shù)等于頂點vi的入度d-(vi)；（4）平行邊所對應(yīng)的列相同。

圖4.4.2所示的有向圖D的關(guān)聯(lián)矩陣為圖4.4.2有向圖D4.4圖的矩陣表示

4.4圖的矩陣表示圖4.4.3所示的有向圖D的鄰接矩陣為：

圖4.4.3有向圖D4.4圖的矩陣表示

圖4.4.3有向圖D4.4圖的矩陣表示

圖4.4.4無向圖G

4.4圖的矩陣表示

4.4圖的矩陣表示

4.5歐拉圖和哈密爾頓圖4.5.1歐拉圖歐拉圖是一類非常重要的圖，之所以如此，不僅是因為歐拉是圖論的創(chuàng)始人，更重要的是歐拉圖具有對邊的“遍歷性”。定義4.5.1

給定無孤立頂點的圖G，通過圖（無向圖或有向圖）中所有邊一次且僅一次的通路稱作歐拉通路（eulerpath）。通過圖中所有邊一次且僅一次的回路稱作歐拉回路（eulercircuit）。具有歐拉回路的圖稱作歐拉圖（eulergraph）。具有歐拉通路而無歐拉回路的圖稱作半歐拉圖（semi

eulergraph）。顯然，每個歐拉圖必然是連通圖。規(guī)定平凡圖是歐拉圖。歐拉通路是經(jīng)過圖中所有邊的長度最短的通路，歐拉回路是經(jīng)過圖中所有邊長度最短的回路。4.5.1歐拉圖圖4.5.1(a)為歐拉圖，v1e1v2e2v3e3v4e4v1e5v1為圖中的一條歐拉回路。圖4.5.1(b)不是歐拉圖，也不是半歐拉圖，圖中既沒有歐拉回路，也沒有歐拉通路。圖4.5.1(c)為半歐拉圖，v1e1v4e2v3e3v2e4v1e5為圖中的一條歐拉通路，但圖中不存在歐拉回路。圖4.5.1歐拉圖和半歐拉圖圖4.5.2(a)為歐拉圖，v1v2v3v4v5v6v7v8v9v6v10v4v11v2v12v11v10v9v12v8v1為圖中的一條歐拉回路。圖4.5.2(b)為半歐拉圖，v3v4v2v1v3v5v4為圖中的一條歐拉通路，但圖中不存在歐拉回路。圖4.5.2歐拉圖和半歐拉圖（a）（b）（c）（a）（b）4.5.1歐拉圖定理4.5.1

無向圖G是歐拉圖，當(dāng)且僅當(dāng)G是連通圖且沒有奇度頂點。根據(jù)定理4.5.1，圖4.5.1中的3個無向圖中，只有圖(a)中無奇度頂點，因而圖(a)是歐拉圖，而圖(b)、(c)都有奇度頂點，因而它們都不是歐拉圖。第4章開頭提到的哥尼斯堡七橋問題其實就是要求在圖4.5.3(b)中走一條歐拉回路。1736年瑞士數(shù)學(xué)家歐拉在所發(fā)表的論文中證明了定理4.5.1，由于哥尼斯堡七橋問題所對應(yīng)圖中的4個頂點都是奇度頂點，故該問題無解。歐拉這篇論文被公認為是第一篇關(guān)于圖論的論文。這也是歐拉回路和歐拉圖名字的來源。圖4.5.3哥尼斯堡七橋問題(a)(b)4.5.1歐拉圖定理4.5.2無向圖G是半歐拉圖，當(dāng)且僅當(dāng)G是連通的且恰有兩個奇度頂點，而且這兩個奇點即是歐拉通路的起點和終點。根據(jù)定理4.5.2，圖4.5.1(c)所示的是半歐拉圖，但圖4.5.1(b)所示的不是半歐拉圖。例4.5.1

圖4.5.4是一套平房的平面圖，從前門進入客廳，由客廳通向4個房間。如果要求每扇門只能進出一次，現(xiàn)在請你從前門進去，能否通過所有的門走遍所有的房間和客廳，最后從后門走出？(a)(b)解

將4個房間、一個客廳、前門外和后門外各對應(yīng)成頂點，若兩個頂點有邊相連，就表示該兩頂點所表示的位置有一扇門相通，如圖4.5.4所示。由于圖4.5.4(b)有4個頂點是奇度頂點，因此本題無解。圖4.5.4房子平面圖4.5.1歐拉圖定理4.5.3

有向圖D是歐拉圖，當(dāng)且僅當(dāng)D是強連通的且每個頂點的入度等于出度。定理4.5.4

有向圖D是半歐拉圖，當(dāng)且僅當(dāng)D是單向連通的且恰有兩個奇度頂點，其中一個頂點的入度比出度大，另一個頂點的出度比入度大1，而其余頂點的入度等于出度。定理4.5.5

G是非平凡的歐拉圖，當(dāng)且僅當(dāng)G是連通的且是若干個邊不重的圈的并集。圖4.5.5(a)所示的為歐拉圖，該圖可以看成圈v7v8v6v7，v8v1v2v8，v2v3v4v2，v4v5v6v4的并集（見圖4.5.5(b)），也可以看成圈v7v8v1v2v3v4v5v6v7和圈v8v2v4v6的并集（見圖4.5.5(c)）。(a)(b)(c)圖4.5.5歐拉圖4.5.1歐拉圖

4.6.1歐拉圖例4.5.2

用Fleury算法從圖4.5.6中找出一條歐拉通路。圖4.5.6無向圖解

圖中奇度頂點是v1和v4，根據(jù)Fleury算法找出的一條歐拉通路如下：L=v1e1v1e2v1e4v3e5v4e8v2e3v5e6v4e7v5e10v1e9v44.6.2哈密爾頓圖圖論中還有一個看上去與歐拉圖問題相似的問題，即哈密爾頓問題。歐拉圖問題考慮邊的遍歷性，哈密爾頓圖問題考慮點的遍歷性。1859年，英國數(shù)學(xué)家哈密爾頓（Hamilton）提出一個問題，他用一個正十二面體的20個頂點代表世界上20個著名的大城市，要求沿著棱，從一個城市出發(fā)，經(jīng)過每個城市僅一次，最后又回到出發(fā)點。這就是當(dāng)時風(fēng)靡一時的“周游世界”游戲，解決這個問題就是在如圖4.5.7所示的圖中尋找一條經(jīng)過圖中每個頂點恰好一次的回路。圖4.5.7哈密爾頓圖問題4.6.2哈密爾頓圖定義4.6.2通過圖（無向圖或有向圖）中所有頂點一次且僅一次的通路稱作哈密爾頓通路。通過圖中所有頂點一次且僅一次的回路稱作哈密爾頓回路。具有哈密爾頓回路的圖稱作哈密爾頓圖。具有哈密爾頓通路而無哈密爾頓回路的圖稱作半哈密爾頓圖。規(guī)定平凡圖是哈密爾頓圖。哈密爾頓通路是經(jīng)過圖中所有頂點的長度最短的通路，哈密爾頓回路是經(jīng)過圖中所有頂點的通路中長度最短的回路。根據(jù)定義4.5.2，可直接得出下面結(jié)論：（1）每個哈密爾頓圖都連通且每個頂點的度數(shù)均大于或等于2；（2）若一個圖有哈密爾頓回路，則任何頂點所關(guān)聯(lián)的邊一定有兩條在該哈密爾頓回路上；（3）若一個圖有哈密爾頓回路，則該哈密爾頓回路上的部分邊不可能組成一個未經(jīng)過所有頂點的基本回路。判斷一個圖是否是哈密爾頓圖，可以借助定義以及上面給出的3個結(jié)論，但這對頂點數(shù)較多的圖來說不可行，因此有必要尋找其他方法，但可惜的是，盡管哈密爾頓圖問題看起來與歐拉圖問題類似，但它確實是一個至今尚未解決的難題?，F(xiàn)在人們只是給出了一些充分條件和一些必要條件，有些結(jié)論的證明還比較復(fù)雜，至今還沒有得到一個充分必要條件。4.5.3最短路問題、中國郵遞員問題與貨郎擔(dān)問題

4.5.3最短路問題、中國郵遞員問題與貨郎擔(dān)問題

4.6樹4.6.1無向樹及其性質(zhì)定義4.6.1

連通無回路的無向圖稱作無向樹，或簡稱樹。每個連通分支都是樹的無向圖稱作森林。平凡圖稱作平凡樹。在無向樹中，懸掛頂點稱作樹葉，度數(shù)大于或等于2的頂點稱作分支點。說明

定義中的回路是指初級回路或簡單回路。圖4.6.1(a)~(d)都是樹，其中圖(c)是平凡樹，它的頂點度數(shù)為0，而在任何非平凡樹中，都無度數(shù)為0的頂點。圖(e)所示的為森林。(a)(b)(c)(d)(e)圖4.6.1無向樹4.6.1無向樹及其性質(zhì)

4.6.1無向樹及其性質(zhì)

圖4.6.2無向樹

4.6.1無向樹及其性質(zhì)例4.6.2

飽和碳氫化合物的同分異構(gòu)體。飽和碳氫化合物CnH2n+2由n個碳原子和2n+2個氫原子組成，碳原子是4價鍵，氫原子是1價鍵。當(dāng)n=1，2，3，4時，各有多少種可能的飽和碳氫化合物。解

用4度頂點代表碳原子，1度頂點代表氫原子，表示CnH2n+2的圖的度數(shù)列由n個4和2n+2個1組成。它有3n+2個頂點，度數(shù)之和等于4n+(2n+2)=2(3n+1)，因此是一顆樹。當(dāng)n=1，2，3時，都只有一棵非同構(gòu)的樹；當(dāng)n=4時，有兩棵不同構(gòu)的樹，如圖4.6.3所示。這說明含有1個、2個和3個碳原子的飽和碳氫化合物都只有一種，而含有4個碳原子的飽和碳氫化合物可能有兩種。事實上，分別含有1個、2個和3個碳原子的飽和碳氫化合物分別是甲烷、乙烷和丙烷，而含有4個碳原子的飽和碳氫化合物有兩種同分異構(gòu)體，分別是丁烷和異丁烷。圖4.6.3飽和碳氫化合物4.6.1無向樹及其性質(zhì)例4.6.3

設(shè)T是一顆無向樹，它有兩個2度頂點，1個3度頂點，4個4度頂點，求T的葉數(shù)。解

設(shè)樹T有x片樹葉，則T的頂點數(shù)n=2+1+3+x=6+x，T的邊數(shù)m=n-1=5+x。

根據(jù)握手定理有2m=2(5+x)=2×2+3×1+4×3+x

解得x=9，即樹T有9片樹葉。例4.6.4

設(shè)T是一顆無向樹，它有7片樹葉，3個3度頂點，剩下的都是4度頂點，則T有幾個4度頂點？解

設(shè)樹T有x個4度頂點，則根據(jù)握手定理有7×1+3×3+4x=2×(7+3+x-1)解得x=1，即樹T有1個4度頂點。

4.6.2生成樹

4.6.2生成樹定理4.6.4

設(shè)T是圖G的生成樹，則（1）G的任何回路都至少包含T的一條弦；（2）若e為T的弦，則G中存在一條且只存在一條只含弦e，其余都是枝的初級回路，該回路稱為弦e的初級回路。定理4.6.5

設(shè)T是圖G的生成樹，則（1）G的任一割集都至少含有T的一條枝；（2）若e為T的枝，則G中恰好存在一個只含枝e的割集，其余都是弦的割集，該割集稱為枝e的基本割集。4.6.2生成樹例4.6.5

圖4.6.4(b)是圖4.6.4(a)的一個生成樹。（1）求此生成樹的所有弦以及相應(yīng)的基本回路。（2）求此生成樹的枝(2，3)相應(yīng)的基本割集。解

（1）圖4.6.4(b)生成樹的所有弦為(2，8)，(8，9)，(9，5)，(4，5)，(5，6)，(8，5)，(8，7)。它們對應(yīng)的基本回路分別是：(1，2，8，1)，(8，9，3，2，1，8)，(9，5，7，1，2，3，9)，(4，5，7，1，2，3，9，4)，(5，6，1，7，5)，(8，5，7，1，8)，(1，8，7，1)。（2）去掉圖4.6.4(b)生成樹枝(2，3)，則該生成樹就變成兩個不連通的部分，其頂點集合分別為{3，9，4}和{1，2，8，7，5，6}?；靖罴褪窃瓐D中連接這兩組頂點的所有邊的集合，即{(2，3)，(8，9)，(9，5)，(4，5)}(a)(b)圖4.6.4連通圖和它的生成樹4.6.3根樹定義4.6.3若有向圖的基圖是無向樹，則稱這個有向圖為有向樹。一個頂點的入度為0，其余頂點的入度為1的有向樹稱作根樹。入度為0的頂點稱作樹根，入度為1、出度為0的頂點稱作樹葉，入度為1、出度不為0的頂點稱作內(nèi)點，內(nèi)點和樹根統(tǒng)稱作分支點。從樹根到任意頂點v的路徑的長度（即路徑中的邊數(shù)）稱作v的層數(shù)，所有頂點的最大層數(shù)稱作樹高。一顆根樹，用圖形表示，有樹根在下（圖4.6.5(a)）或樹根在上（圖4.6.5(b)）兩種畫法。然而，通常將樹根畫最上方，有向邊的方向向下或斜下方，并省去各邊上的箭頭，如圖4.6.5(c)所示。在圖4.6.5(c)所示的根樹中，有6片樹葉、4個內(nèi)點、5個分支點，樹高為4，在樹葉v5和v6處達到。圖4.6.5根樹(a)(b)(c)4.6.3根樹

圖4.6.5根樹(a)(b)(c)4.6.3根樹

4.6.3根樹

圖4.6.6中的T4是最優(yōu)二叉樹，Huffman（霍夫曼）算法是一種常用的求最優(yōu)二叉樹的算法。圖4.6.6二叉樹4.6.3根樹

4.6.3根樹例4.6.6

利用Huffma