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

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

4.1圖的基本概念

圖4.1.1無(wú)向圖G說(shuō)明

元素可以重復(fù)出現(xiàn)的集合稱(chēng)作多重集合。某元素重復(fù)出現(xiàn)的次數(shù)稱(chēng)作該元素的重復(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。從多重集合的角度考慮，無(wú)元素重復(fù)出現(xiàn)的集合是各元素重復(fù)度均為1的多重集。4.1圖的基本概念

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

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

圖4.1.10無(wú)向圖G4.1圖的基本概念定義4.1.3

在無(wú)向圖中，如果關(guān)聯(lián)一對(duì)頂點(diǎn)的無(wú)向邊多于1條，則稱(chēng)這些邊為平行邊（paralleledges），平行邊的條數(shù)稱(chēng)作重?cái)?shù)。在有向圖中，如果關(guān)聯(lián)一對(duì)頂點(diǎn)的有向邊多于1條，并且這些邊的始點(diǎn)與終點(diǎn)相同（也就是它們的方向相同），則稱(chēng)這些邊為平行邊。含平行邊的圖稱(chēng)作多重圖（multigraph），既不含平行邊也不含環(huán)的圖稱(chēng)作簡(jiǎn)單圖（simplegraph）。在圖4.1.11中，e2和e3是平行邊，e5和e8是平行邊，e6和e1不是平行邊。圖4.1.11不是簡(jiǎn)單圖，圖4.1.10是簡(jiǎn)單圖。圖4.1.11有向圖D（多重圖）圖4.1.10無(wú)向圖G（簡(jiǎn)單圖）平行邊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為懸掛頂點(diǎn)，e2為懸掛邊。圖4.1.12無(wú)向圖G圖4.1.13有向圖D

看成一個(gè)大頂點(diǎn)V1懸掛頂點(diǎn)懸掛邊4.1圖的基本概念定理4.1.1

握手定理（handshakingtheorem）

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

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

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

圖4.1.12無(wú)向圖G圖4.1.13有向圖D4.1圖的基本概念

4.1圖的基本概念圖4.1.14分別示意了幾種常見(jiàn)的無(wú)向完全圖。圖4.1.15為1階、2階、3階有向完全圖。圖4.1.16為1階、2階、3階、4階競(jìng)賽圖。圖4.1.14無(wú)向完全圖圖4.1.15有向完全圖圖4.1.16競(jìng)賽圖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

圖及其補(bǔ)圖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刪除邊、刪除頂點(diǎn)、邊的收縮4.1圖的基本概念圖重點(diǎn)關(guān)注的是頂點(diǎn)與頂點(diǎn)的鄰接關(guān)系，不在意頂點(diǎn)的位置和連線(xiàn)的形狀。對(duì)于給定的圖，圖的表現(xiàn)形式可能不唯一。如果將圖的頂點(diǎn)放置在不同的位置，邊用不同形狀的弧線(xiàn)或直線(xiàn)表示，則可以得到同一個(gè)圖的不同形式的圖形。因此，看起來(lái)完全不同的圖形，可能表示著同一個(gè)圖。為了描述看起來(lái)不同而其結(jié)構(gòu)完全相同的圖，引入同構(gòu)的概念。如圖4.1.25所示，雖然四個(gè)圖形的形式各不相同，但它們表示同一個(gè)圖。圖4.1.25形式不同的圖4.1圖的基本概念

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

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

4.2通路與回路

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

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

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

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

4.3圖的連通性圖中兩個(gè)頂點(diǎn)之間的通路可能不止一條，但是，總是存在長(zhǎng)度最短的一條，即最短通路（最短路徑）。

4.3圖的連通性例4.3.1

（擺渡問(wèn)題）一個(gè)人帶著一條狗、一只羊和一筐蔬菜來(lái)到河的南岸。河邊的小船一次只能載著人和他帶的一樣?xùn)|西（狗、羊或菜）。而在人不在場(chǎng)的情況下，狗和羊，羊和菜不能放在一塊，因?yàn)楣芬а?，羊?huì)吃菜。這個(gè)人怎樣才能把他的三樣?xùn)|西安全地運(yùn)到河對(duì)岸（北岸）？至少需要來(lái)回幾次？解

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

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

圖4.3.9無(wú)向圖4.3圖的連通性例4.3.2

在圖4.3.10(a)中，頂點(diǎn)5、6、10是割點(diǎn)，頂點(diǎn)子集{1，4}是點(diǎn)割集，而頂點(diǎn)子集{1，9}、{7，8}、{4，5}、{1，3，4}不是點(diǎn)割集。邊{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)中，頂點(diǎn)3、4是割點(diǎn)，頂點(diǎn)子集{2，8}、{5，7}是點(diǎn)割集，而頂點(diǎn)子集{1，9}、{4，5}、{1，2，8}不是點(diǎn)割集。邊{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無(wú)向圖的點(diǎn)割集、邊割集、割點(diǎn)和割邊4.3圖的連通性

圖4.3.9無(wú)向圖4.3圖的連通性

圖4.3.9無(wú)向圖4.3圖的連通性

4.3圖的連通性

4.3圖的連通性

圖4.3.11強(qiáng)連通圖、單向連通圖和弱連通圖4.3圖的連通性定理4.3.2

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

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

圖4.4.1無(wú)向圖G

v1v2v3v4v5e1e2e3e4e5e64.4圖的矩陣表示

4.4圖的矩陣表示

有向圖D的關(guān)聯(lián)矩陣M(D)有以下幾個(gè)性質(zhì)：（1）每列恰好有一個(gè)1和一個(gè)-1，說(shuō)明每條有向邊有一個(gè)起點(diǎn)和一個(gè)終點(diǎn)；（2）矩陣的所有元素和為0，即-1的個(gè)數(shù)等于1的個(gè)數(shù)，都等于邊數(shù)m；（3）第i行中，1的個(gè)數(shù)等于頂點(diǎn)vi的出度d+(vi)，-1的個(gè)數(shù)等于頂點(diǎn)vi的入度d-(vi)；（4）平行邊所對(duì)應(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無(wú)向圖G

4.4圖的矩陣表示

4.4圖的矩陣表示

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

給定無(wú)孤立頂點(diǎn)的圖G，通過(guò)圖（無(wú)向圖或有向圖）中所有邊一次且僅一次的通路稱(chēng)作歐拉通路（eulerpath）。通過(guò)圖中所有邊一次且僅一次的回路稱(chēng)作歐拉回路（eulercircuit）。具有歐拉回路的圖稱(chēng)作歐拉圖（eulergraph）。具有歐拉通路而無(wú)歐拉回路的圖稱(chēng)作半歐拉圖（semi

eulergraph）。顯然，每個(gè)歐拉圖必然是連通圖。規(guī)定平凡圖是歐拉圖。歐拉通路是經(jīng)過(guò)圖中所有邊的長(zhǎng)度最短的通路，歐拉回路是經(jīng)過(guò)圖中所有邊長(zhǎng)度最短的回路。4.5.1歐拉圖圖4.5.1(a)為歐拉圖，v1e1v2e2v3e3v4e4v1e5v1為圖中的一條歐拉回路。圖4.5.1(b)不是歐拉圖，也不是半歐拉圖，圖中既沒(méi)有歐拉回路，也沒(méi)有歐拉通路。圖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

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

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

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

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

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

G是非平凡的歐拉圖，當(dāng)且僅當(dāng)G是連通的且是若干個(gè)邊不重的圈的并集。圖4.5.5(a)所示的為歐拉圖，該圖可以看成圈v7v8v6v7，v8v1v2v8，v2v3v4v2，v4v5v6v4的并集（見(jiàn)圖4.5.5(b)），也可以看成圈v7v8v1v2v3v4v5v6v7和圈v8v2v4v6的并集（見(jiàn)圖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無(wú)向圖解

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

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

4.6樹(shù)4.6.1無(wú)向樹(shù)及其性質(zhì)定義4.6.1

連通無(wú)回路的無(wú)向圖稱(chēng)作無(wú)向樹(shù)，或簡(jiǎn)稱(chēng)樹(shù)。每個(gè)連通分支都是樹(shù)的無(wú)向圖稱(chēng)作森林。平凡圖稱(chēng)作平凡樹(shù)。在無(wú)向樹(shù)中，懸掛頂點(diǎn)稱(chēng)作樹(shù)葉，度數(shù)大于或等于2的頂點(diǎn)稱(chēng)作分支點(diǎn)。說(shuō)明

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

4.6.1無(wú)向樹(shù)及其性質(zhì)

圖4.6.2無(wú)向樹(shù)

4.6.1無(wú)向樹(shù)及其性質(zhì)例4.6.2

飽和碳?xì)浠衔锏耐之悩?gòu)體。飽和碳?xì)浠衔顲nH2n+2由n個(gè)碳原子和2n+2個(gè)氫原子組成，碳原子是4價(jià)鍵，氫原子是1價(jià)鍵。當(dāng)n=1，2，3，4時(shí)，各有多少種可能的飽和碳?xì)浠衔铩＝?/p>

用4度頂點(diǎn)代表碳原子，1度頂點(diǎn)代表氫原子，表示CnH2n+2的圖的度數(shù)列由n個(gè)4和2n+2個(gè)1組成。它有3n+2個(gè)頂點(diǎn)，度數(shù)之和等于4n+(2n+2)=2(3n+1)，因此是一顆樹(shù)。當(dāng)n=1，2，3時(shí)，都只有一棵非同構(gòu)的樹(shù)；當(dāng)n=4時(shí)，有兩棵不同構(gòu)的樹(shù)，如圖4.6.3所示。這說(shuō)明含有1個(gè)、2個(gè)和3個(gè)碳原子的飽和碳?xì)浠衔锒贾挥幸环N，而含有4個(gè)碳原子的飽和碳?xì)浠衔锟赡苡袃煞N。事實(shí)上，分別含有1個(gè)、2個(gè)和3個(gè)碳原子的飽和碳?xì)浠衔锓謩e是甲烷、乙烷和丙烷，而含有4個(gè)碳原子的飽和碳?xì)浠衔镉袃煞N同分異構(gòu)體，分別是丁烷和異丁烷。圖4.6.3飽和碳?xì)浠衔?.6.1無(wú)向樹(shù)及其性質(zhì)例4.6.3

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

設(shè)樹(shù)T有x片樹(shù)葉，則T的頂點(diǎn)數(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，即樹(shù)T有9片樹(shù)葉。例4.6.4

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

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

4.6.2生成樹(shù)

4.6.2生成樹(shù)定理4.6.4

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

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

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

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

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

4.6.3根樹(shù)

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

4.6.3根樹(shù)例4.6.6

利用Huffma