離散數(shù)學(xué)-第11章

圖論

主講:熊煥亮

圖論簡介圖論（graphtheory）是研究節(jié)點(diǎn)和邊組成的圖形的數(shù)學(xué)理論和方法，為離散數(shù)學(xué)的一個(gè)重要分支。圖論的基本元素是節(jié)點(diǎn)和邊（也稱線、弧、枝），用節(jié)點(diǎn)表示所研究的對象，用邊表示研究對象之間的某種特定關(guān)系。因此，圖論可用節(jié)點(diǎn)和邊組成的圖形及其有關(guān)的理論和方法來描述、分析和解決各種實(shí)際問題，已廣泛地應(yīng)用于物理、化學(xué)、運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)、電子學(xué)、信息論、控制論、網(wǎng)絡(luò)理論、管理科學(xué)、社會科學(xué)等幾乎所有學(xué)科領(lǐng)域的有關(guān)問題。圖論與組合數(shù)學(xué)、線性規(guī)劃、群論、矩陣論、概率論、數(shù)值分析等數(shù)學(xué)分支有密切的關(guān)系。2圖論簡介圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。圖論本身是應(yīng)用數(shù)學(xué)的一部份，因此，歷史上圖論曾經(jīng)被好多位數(shù)學(xué)家各自獨(dú)立地建立過。關(guān)于圖論的文字記載最早出現(xiàn)在瑞士數(shù)學(xué)家歐拉（Leonhard

Eular）1736年的論文中，解決了著名的哥尼斯保七橋問題。因此通常認(rèn)為歐拉是圖論的創(chuàng)始人。1845年，德國物理學(xué)家基爾霍夫?yàn)榱私鉀Q一類線性聯(lián)立方程組而創(chuàng)建“樹”理論。他把電網(wǎng)絡(luò)和其中的電阻、電容和電感等抽象化，用一個(gè)只有點(diǎn)和邊組成的組合結(jié)構(gòu)來代替電網(wǎng)絡(luò)，而不指明每條邊所代表的電器元件種類,這樣就可以方便地對方程組進(jìn)行求解。1852年，格思里在對地圖著色時(shí)發(fā)現(xiàn),無論多么復(fù)雜的地圖,只要用四種顏色就能將相鄰區(qū)域區(qū)分開來。這就是所謂“四色猜想”。經(jīng)過百余年的努力，直到1976年才由阿佩爾和赫肯借助電子計(jì)算機(jī)證明了四色定理。3圖論簡介1856年，哈密頓在給格雷夫斯的信中提出一個(gè)游戲：用正十二面體上20個(gè)頂點(diǎn)表示20個(gè)城市，要求游戲者沿著各邊行走，走遍每個(gè)城市一次且僅一次，最后回到原出發(fā)城市。這個(gè)游戲促使人們研究如何判斷一個(gè)圖有無這一性質(zhì)，如果有，則又如何確定這樣的路徑，即稱之為哈密頓圖。這是一個(gè)至今尚未完全解決的問題。1962年，中國數(shù)學(xué)家管梅谷提出一個(gè)所謂“中國郵路問題”：郵遞員帶著郵件從郵局出發(fā)，走遍他所管轄的每一條街道，最后回到郵局，如何選擇路線，使走的路程最短。1967年，埃德蒙茲給出中國郵路問題一個(gè)好的解法。圖論雖有200年的歷史,但受計(jì)算機(jī)科學(xué)發(fā)展的刺激,發(fā)展極其迅速。上世紀(jì)60年代以來圖論在各種學(xué)科領(lǐng)域中得到了廣泛應(yīng)用。圖論在理論上也得到了新的發(fā)展，如圖特等發(fā)展了擬陣?yán)碚摚悹枱岬劝l(fā)展了超圖理論，埃爾德什等發(fā)展了極圖理論等。本書介紹圖的基本概念、路與回路、圖的矩陣表示、歐拉圖與漢密爾頓圖、平面圖、對偶圖與著色、樹與生成樹、根樹及其應(yīng)用、二部圖、匹配等。各章節(jié)主要知識點(diǎn)關(guān)聯(lián)如圖4.0.0所示。4圖4.0.0第四部分各章節(jié)主要知識點(diǎn)關(guān)聯(lián)圖圖邊集頂點(diǎn)集連通性同構(gòu)性匹配性帶權(quán)圖平面圖著色性關(guān)聯(lián)矩陣鄰接矩陣可達(dá)矩陣平面圖的著色通路連通圖二部圖歐拉圖哈密頓圖樹圖的矩陣表示強(qiáng)連通圖單向連通圖弱連通圖哈密頓通路哈密頓回路歐拉通路歐拉回路生成樹森林根樹有向性最小生成樹最優(yōu)樹遍歷二叉樹中序行遍法前序行遍法后序行遍法Huffman算法簡單圖多重圖邊覆蓋集無平行邊，無環(huán)有平行邊無向圖有向圖平凡圖完全圖正則圖相鄰可達(dá)回路支配集點(diǎn)獨(dú)立集點(diǎn)覆蓋集帶權(quán)圖基圖5圖的基本概念目錄第十一章圖的基本概念

11.1圖的概念11.1.2簡單圖、多重圖和同構(gòu)圖11.1.3完全圖和正則圖11.1.4幾種特殊的圖11.1.5子圖11.1.6圖的操作11.2圖的連通性

11.2.1通路與回路11.2.2連通圖11.2.3二部圖11.3圖的矩陣表示11.3.1關(guān)聯(lián)矩陣11.3.2鄰接矩陣11.3.3可達(dá)矩陣11.4圖的運(yùn)算11.5歐拉圖

11.5.1歐拉通路和回路11.5.2半歐拉圖和歐拉圖11.5.3哥尼斯堡七橋問題11.6哈密頓圖11.6.1哈密頓圖11.6.2哈密頓圖的充分條件11.7帶權(quán)圖11.8平面圖11.8.1平面圖的基本概念及性質(zhì)11.8.2庫拉托夫基定理11.8.3平面圖著色及應(yīng)用11.8.4邊著色11.9應(yīng)用舉例*11.9.1中國郵路問題11.9.2冰箱分隔問題11.9.3排課表問題6第十一章圖的基本概念

11.1圖的概念現(xiàn)實(shí)世界中許多現(xiàn)象都可以用某種圖形表示，這些圖形由一些點(diǎn)和連接兩點(diǎn)間的連線所組成，點(diǎn)表示事物，用點(diǎn)與點(diǎn)之間是否有連線表示事物之間是否有某種聯(lián)系，這樣構(gòu)成的圖形就是圖論中的圖。711.1圖的概念11.1.1無向圖和有向圖定義11.1.1

一個(gè)圖是一個(gè)有序的二元組

<>,記作,其中(1)是有限非空集合，稱為頂點(diǎn)集,其元素稱為頂點(diǎn)或結(jié)點(diǎn)。

(2)是有限集合，稱為邊集,E中每個(gè)元素都有

V中的結(jié)點(diǎn)對與之對應(yīng)，稱為邊。定義11.1.1中的邊

e既可以是有向的,也可以是無向的。有向邊與有序結(jié)點(diǎn)對

<u,v>對應(yīng),這時(shí)稱

u為e的起點(diǎn),

v為e的終點(diǎn)。無向邊與無序結(jié)點(diǎn)對(u,v)對應(yīng),u,v稱為

e的兩個(gè)端點(diǎn)。(3)將圖的集合定義轉(zhuǎn)化成圖形表示之后，常用表示圖的邊，

稱頂點(diǎn)或邊用字母標(biāo)定的圖為標(biāo)定圖，否則稱為非標(biāo)定圖。(4)將有向圖各有向邊均改成無向邊后的無向圖稱為原有向圖的基圖。(5)若一條邊連接同一個(gè)點(diǎn)，稱其為圈。811.1圖的概念(6)若，,則通常稱它為（p,q）圖。p稱為圖G的階,（1，0）圖稱為平凡圖。邊集

E為空集的圖稱為零圖。頂點(diǎn)集

V和邊集

E都是有限集的圖稱為有限圖。(7)若，則稱點(diǎn)u與點(diǎn)v相鄰接。并說點(diǎn)u與邊e相關(guān)聯(lián)，點(diǎn)v與邊e相關(guān)聯(lián)。同樣，若邊e和邊f(xié)有一個(gè)共同的端點(diǎn)，則也稱邊e和邊f(xié)相鄰接。沒有邊關(guān)聯(lián)于它的頂點(diǎn)稱為孤立點(diǎn)，不與其它任何邊相鄰接的邊稱為孤立邊。例11.1.1(1)給定無向圖,其中V=,E=

給定有向圖D=，其中

V=，E=

。畫出G與D的圖形。

911.1圖的概念解 圖11.1.1中(a),(b)分別給出了無向圖G和有向圖D的圖形表示。圖11.1.1

例11.1.1無向圖G和有向圖D1011.1.2簡單圖、多重圖和同構(gòu)圖11.1.2簡單圖、多重圖和同構(gòu)圖定義11.1.2

在無向圖中，關(guān)聯(lián)一對頂點(diǎn)的無向邊如果多于1條，則稱這些邊為平行邊，平行邊的條數(shù)稱為重?cái)?shù)。在有向圖中，關(guān)聯(lián)一對頂點(diǎn)的有向邊如果多于1條，并且這些邊的始點(diǎn)與終點(diǎn)相同（也就是他們的方向相同），稱這些邊為平行邊。含平行邊的圖稱為多重圖，既不含平行邊也不含環(huán)的圖稱為簡單圖。在圖11.1.1中，(a)中是平行邊，在(b)中是平行邊；注意，與不是平行邊。(a)和(b)兩個(gè)都不是簡單圖。1111.1.2簡單圖、多重圖和同構(gòu)圖定義11.1.3

設(shè)為一無向圖，稱v作為邊的端點(diǎn)次數(shù)之和為v的度數(shù)，簡記為度，記作，在不發(fā)生混淆時(shí)，簡記為。設(shè)為有向圖，,稱v作為邊的始點(diǎn)的次數(shù)之和為v的出度，記作簡記為。稱v作為邊的終點(diǎn)的次數(shù)之和為v的入度，記作簡記為，稱+為v的度數(shù)，記作。在無向圖中，令稱，分別為G的最大度和最小度。在有向圖D中，類似可定義最大度和最小度。另外，令分別稱為D的最大出度，最小出度，最大入度，最小入度。以上記號可以1211.1.2簡單圖、多重圖和同構(gòu)圖分別簡記為。

另外，稱度數(shù)為1的頂點(diǎn)為懸掛頂點(diǎn)，與它關(guān)聯(lián)的邊稱為懸掛。度為偶數(shù)（奇數(shù)）的頂點(diǎn)稱為偶度（奇度）頂點(diǎn)。在圖11.1.1中，(a)的

(注意，環(huán)提供2度)，是懸掛頂點(diǎn)，是懸掛邊。(b)的(環(huán)提供出度1，提供入度1)，(在a點(diǎn)達(dá)到)，(在b點(diǎn)達(dá)到)，(在b點(diǎn)達(dá)到)，（在a和c點(diǎn)達(dá)到）。下面給出的定理是歐拉于1736年給出的，常稱為握手定理，它是圖論中的基本定理。1311.1.2簡單圖、多重圖和同構(gòu)圖定理11.1.1

設(shè)為任意圖，，則證

G中每條邊（包括環(huán)）均有兩個(gè)端點(diǎn)，所以加上一條邊就使得各結(jié)點(diǎn)的度數(shù)之和增加2，因此結(jié)論成立。推論11.1.1

任何圖（無向的或有向的）中，奇度頂點(diǎn)的個(gè)數(shù)為偶數(shù)。證 設(shè)為任意一圖，令則由于2,均為偶數(shù)，所以為偶數(shù)，但因中頂點(diǎn)度數(shù)為奇數(shù)，所以必為偶數(shù)。

1411.1.2簡單圖、多重圖和同構(gòu)圖設(shè)為一個(gè)階無向圖，稱,為G的度數(shù)列。對于頂點(diǎn)標(biāo)定的無向圖，它的度數(shù)列是唯一的。反之，對于給定的非負(fù)整數(shù)列，若存在以為頂點(diǎn)集的n階無向圖G,使得，則稱d是可圖化的。特別地，若所得的圖是簡單圖,則稱d是可簡單圖化的。例11.1.2

（1）（3，5，1，4），（1，2，3，4，5）能成為圖的度數(shù)列嗎？為什么？（2）已知圖G中有15條邊，2個(gè)度數(shù)為4的結(jié)點(diǎn)，4個(gè)度數(shù)為3的結(jié)點(diǎn)，其余結(jié)點(diǎn)度數(shù)均小于等于2，問G中至少有多少個(gè)結(jié)點(diǎn)？為什么？解 （1）由于給定的兩個(gè)度數(shù)列中奇度頂點(diǎn)個(gè)數(shù)均為奇數(shù)，由上述推論可知，他們都不能成為圖的度數(shù)列。（2）圖中邊數(shù)為15，由握手定理可知，G中所有結(jié)點(diǎn)度數(shù)和為30。除去2個(gè)度數(shù)為4的結(jié)點(diǎn)和4個(gè)度數(shù)為3的結(jié)點(diǎn)，還剩下10度。其余結(jié)點(diǎn)度數(shù)小于等于2，假設(shè)均為2，則至少要5個(gè)結(jié)點(diǎn)，所以總共至少要11個(gè)結(jié)點(diǎn)。1511.1.2簡單圖、多重圖和同構(gòu)圖定義11.1.4

設(shè)，為兩個(gè)無向圖（兩個(gè)有向圖），若存在雙射函數(shù),對于當(dāng)且僅當(dāng)并且與的重?cái)?shù)相同，則稱與是同構(gòu)的，記作。對于同構(gòu)，形象地說，若圖的結(jié)點(diǎn)可以任意挪動位置，而邊是完全彈性的，只要在不拉斷的條件下，一個(gè)圖可以變形為另一個(gè)圖，那么這兩個(gè)圖是同構(gòu)的。到目前為止，還沒有找到判斷兩個(gè)圖是否同構(gòu)的有效方法，還只能根據(jù)定義來判斷。需要注意的是，不要將兩個(gè)圖同構(gòu)的必要條件當(dāng)成充分條件。若，則他們的結(jié)點(diǎn)數(shù)相同，邊數(shù)相同，度數(shù)列相同，等等，破壞這些必要條件中的任何一個(gè)，兩個(gè)圖就不會同構(gòu)，但以上列出的條件都滿足，兩個(gè)圖也不一定同構(gòu)。1611.1.2簡單圖、多重圖和同構(gòu)圖例11.1.3

證明圖11.1.2中(a)和(b)是同構(gòu)的，(c)和(d)是不同構(gòu)的。圖11.1.2

同構(gòu)圖概念示意圖例1711.1.2簡單圖、多重圖和同構(gòu)圖證明：

(a)(b)同構(gòu)。構(gòu)造結(jié)點(diǎn)之間的雙射函數(shù)f如下：，，，，，，，，容易驗(yàn)證，f滿足同構(gòu)的定義。

(c)和(d)不同構(gòu)。通常證明兩圖不同構(gòu)，采用反證法。假設(shè)(c)和(d)同構(gòu)，并存在雙射函數(shù)f，則有和的度數(shù)一定相同，因此有即(c)中的3和(d)中的d對應(yīng)。而(c)中的3與一個(gè)1度頂點(diǎn)6鄰接，而(d)中的d與兩個(gè)1度頂點(diǎn)e,f

鄰接,故假設(shè)不成立。1811.1.3完全圖和正則圖11.1.3完全圖和正則圖定義11.1.5

設(shè)G為n階無向簡單圖，若G中每個(gè)頂點(diǎn)均與其余的個(gè)頂點(diǎn)相鄰，則稱G為n階無向完全圖，簡稱n階完全圖，記作。設(shè)D為n階有向簡單圖，若D中每個(gè)頂點(diǎn)均與其余的個(gè)頂點(diǎn)相鄰，又鄰接于其余的個(gè)頂點(diǎn)，則稱D是n階有向完全圖。設(shè)D為n階有向簡單圖，若D的基圖為n階無向完全圖，則稱D是n階競賽圖。在圖11.1.3中，(a)為，(b)為3階有向完全圖，(c)為4階競賽圖。

圖11.1.3

無向完全圖、有向完全圖與競賽圖示意圖例1911.1.3完全圖和正則圖易知，n階無向完全圖，n階有向完全圖，n階競賽圖的邊數(shù)分別為定義11.1.6

設(shè)G為n階無向簡單圖，若均有則稱G為正則圖。由定義可知，n階零圖是0-正則圖，n階無向完全圖是正則圖，彼得松圖是3-正則圖。由握手定理可知，n階k-正則圖中，邊數(shù)，因而當(dāng)k為奇數(shù)時(shí)，n必為偶數(shù)。2011.1.4幾種特殊的圖圖11.1.4給出了幾個(gè)特殊的圖，圖11.1.4（a）是星型圖，圖11.1.4（b）是環(huán)型圖，圖11.1.4（c）是輪型圖。星型圖常用（）表示，n是星型圖中懸掛點(diǎn)的個(gè)數(shù)，所以的階數(shù)是。環(huán)型圖常用（）表示，n即是環(huán)型圖的階數(shù)。輪型圖常用（）表示，它被看作是在環(huán)型圖添加一個(gè)頂點(diǎn)，而且把這個(gè)新頂點(diǎn)與里n個(gè)頂點(diǎn)逐個(gè)連接后所得的圖形，所以的階數(shù)是。這3種圖形是局域網(wǎng)經(jīng)常使用的拓?fù)淠Ｐ?。使用星型拓?fù)涞木钟蚓W(wǎng)，所有其他設(shè)備都連接到中央控制設(shè)備，消息通過中央控制設(shè)備進(jìn)行傳送；使用環(huán)型拓?fù)涞木钟蚓W(wǎng)，大家都圍繞著環(huán)把消息從設(shè)備送到設(shè)備，直到抵達(dá)消息目的地為止；使用輪型拓?fù)涞木钟蚓W(wǎng)是一種帶冗余的局域網(wǎng)，消息圍繞著環(huán)或通過中央控制設(shè)備來傳送。(a)(b)(c)圖11.1.4幾種特殊的圖2111.1.4幾種特殊的圖除掉這三個(gè)圖形外，還有一個(gè)特殊圖在并行計(jì)算的互聯(lián)網(wǎng)絡(luò)中經(jīng)常用到，它就是超立方體圖（用表示）。它具有個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)對應(yīng)一個(gè)長度為的n位串，兩個(gè)頂點(diǎn)相鄰，當(dāng)且僅當(dāng)它們所表示的位串恰恰相差一位。的頂點(diǎn)數(shù)是，圖11.1.5顯示的是，，。圖11.1.5

對于＝1，2，3的超立方體圖2211.1.4幾種特殊的圖對并行計(jì)算的超立方體網(wǎng)絡(luò)來說，處理器數(shù)是2的冪，即。p個(gè)處理器標(biāo)記成，每個(gè)處理器都有到n個(gè)其它處理器的雙向連接，處理器與下標(biāo)的二進(jìn)制表示與i的二進(jìn)制表示恰恰相差1位的處理器相連。超立方體網(wǎng)絡(luò)在每個(gè)頂點(diǎn)的直接連接數(shù)與保證處理器通信的中間連接數(shù)之間取得了平衡。已經(jīng)用超立方體網(wǎng)絡(luò)建造了許多巨型計(jì)算機(jī)，而且用超立方體網(wǎng)絡(luò)設(shè)計(jì)了許多并行算法。2311.1.5子圖定義11.1.7

設(shè)，為兩個(gè)圖(同為無向圖或同為有向圖)，若,則稱是的子圖，是的母圖，記作，又若，則稱是的真子圖，若，則稱是的生成子圖。設(shè)為一圖，，稱以為頂點(diǎn)集，以中兩個(gè)端點(diǎn)都在中的邊組成邊集的圖為的導(dǎo)出子圖，記作。又設(shè),稱以為邊集，以中邊關(guān)聯(lián)的頂點(diǎn)為頂點(diǎn)集的圖為的導(dǎo)出的子圖，記作。在圖11.1.6中，設(shè)如(a)中圖表示，取，則的導(dǎo)出子圖如(b)中圖所示。取，則的導(dǎo)出子圖如(c)圖所示。2411.1.5子圖圖11.1.6

子圖概念示意圖例2511.1.5子圖定義11.1.8

設(shè)為n階無向簡單圖，以V為頂點(diǎn)集，以所有使G成為完全圖的添加邊組成的集合為邊集的圖，稱為的G補(bǔ)圖，記作。若圖,則稱G是自補(bǔ)圖。在圖11.1.7中，(b)與(c)互為補(bǔ)圖，(a)是自補(bǔ)圖。圖11.1.7

補(bǔ)圖概念示意圖例2611.1.6圖的操作定義11.1.9

設(shè)為無向圖。（1）設(shè),用表示從中去掉邊，稱為刪除邊。又設(shè),用表示從中刪除中的所有邊，稱為刪除。（2）設(shè),用表示從中去掉及所關(guān)聯(lián)的一切邊，稱為刪除頂點(diǎn)。又設(shè)表示從中刪除中的所有邊，稱為刪除。（3）設(shè)邊表示從中刪除后，將的兩個(gè)端點(diǎn)用一個(gè)新的頂點(diǎn)(或用或用充當(dāng))代替，使關(guān)聯(lián)以外關(guān)聯(lián)的所有邊，稱為邊的收縮。（4）設(shè)(可能相鄰，也可能不相鄰)，用（或）表示在之間加一條邊（），稱為加新邊。2711.1.6圖的操作圖11.1.8

圖的操作概念示意圖例在收縮邊和加新邊過程中可能產(chǎn)生環(huán)和平行邊。在圖11.1.8中，設(shè)(a)中圖為G，則(b)為G-，(c)為G-{},(d)為G-，(e)為G-，而(f)為。2811.2圖的連通性11.2.1通路與回路定義11.2.1設(shè)為G無向標(biāo)定圖，G中頂點(diǎn)與邊的交替序列稱為到的通路，其中，為的端點(diǎn)，,分別成為的始點(diǎn)與終點(diǎn)，中邊的條數(shù)稱為它的長度，若，則稱為簡單回路。若的所有頂點(diǎn)(除與可能相同外)各異，所有邊也各異，則稱為初級通路或路徑，此時(shí)又若，則稱為初級回路或圈。將長度為奇數(shù)的圈稱為奇圈，長度為偶數(shù)大圈稱為偶圈。注意，在初級通路與初級回路的定義中，若將初級回路看成初級通路(路徑)的特殊情況，只是在應(yīng)用中初級通路(路徑)都是始點(diǎn)與終點(diǎn)不相同的，長為1的圈只能由環(huán)生成，長為2的圈只能由平行邊生成，因而在簡單無向圖中，圈的長度至少為3。2911.2.1通路與回路另外，若中有邊重復(fù)出現(xiàn)，則稱為復(fù)雜通路。又若則稱為復(fù)雜回路。在有向圖中，通路、回路及分類的定義與無向圖中非常類似，只是要注意有向邊方向的一致性。在以上的定義中，將回路定義成通路的特殊情況，即回路也是通路，又初級通路(回路)是簡單通路(回路)，但反之不真。用頂點(diǎn)與邊的交替序列定義了通路與回路，但還可以用更簡單的表示法表示通路與回路。（1）只用邊的序列表示通路(回路)。定義11.2.1中的可以表示成。（2）在簡單圖中也可以只用頂點(diǎn)序列表示通路(回路)。定義中的也可以表示成。（3）為了寫出非標(biāo)定圖中的通路(回路)，可以先將非標(biāo)定圖標(biāo)成標(biāo)定圖，再寫出通路與回路。3011.2.1通路與回路定理11.2.1

在n階圖G中，若頂點(diǎn)到

存在通路，則從到存在長度小于或等于()的通路。證 設(shè)=()為G中一條長度為的通路，若，則滿足要求，否則必有即上的頂點(diǎn)數(shù)大于G中的頂點(diǎn)數(shù)，于是必存在使得，即在上存在到自身的回路上的一切邊及除外的一切頂點(diǎn),得=任為到的通路，且長度至少比減少1.若還不滿足要求，則重復(fù)上述過程，由于G是有限圖。經(jīng)過有限步后，必得到到長度小于或等于的通路。推論11.2.1

在n階圖G中，若存在到存在通路，則到一定存在長度小于或等于的初級通路(路徑)。定理11.2.2

在一個(gè)n階圖G中，若存在到自身的回路,則一定存在到自身長度小于或等于n的回路。推論11.2.2在一個(gè)n階圖G中，若存在到自身的簡單回路，則一定存在長度小于或等于n的初級回路。3111.2.1通路與回路例11.2.1

無向完全圖中有幾種非同構(gòu)的圈？解長度相同的圈都是同構(gòu)的，因而只有長度不同的圈才是非同構(gòu)的，易知中含長度為的圈，所以中有種非同構(gòu)的圈。例11.2.2

無向完全圖的頂點(diǎn)依次標(biāo)定為在定義意義下中有多少個(gè)不同的圈？解在同構(gòu)意義下，中只有一個(gè)長度為3的圈。但在定義意義下，不同起點(diǎn)(終點(diǎn))的圈是不同的，頂點(diǎn)間排列順序不同的圈也看成是不同的，因而中有6個(gè)不同的長為3的圈：如果只考慮起點(diǎn)(終點(diǎn))的差異，而不考慮順時(shí)針逆時(shí)針的差異，應(yīng)該有3種不同的圈，當(dāng)然它們的長度都是3。3211.2.2連通圖11.2.2連通圖定義11.2.2

設(shè)無向圖,,若之間存在通路，則稱是連通的，記作～，規(guī)定～。由定義不難看出，無向圖中頂點(diǎn)之間的連通關(guān)系，顯然～是自反的，對稱的，傳遞的，因而～是V上的等價(jià)關(guān)系。定義11.2.3

若無向圖G是平凡圖或G中任何兩個(gè)頂點(diǎn)都是連通的，則稱G為連通圖，否則稱G為非連通圖或分離圖。易知，完全圖都是連通圖，而零圖都是分離圖。定義11.2.4

設(shè)無向圖,V關(guān)于頂點(diǎn)之間的連通關(guān)系～的商集～=為等價(jià)類，稱導(dǎo)出子圖為G的連通分支，連通分支數(shù)常記為。由定義可知，若G為連通圖，則=1，若G為非連通圖，則在所有的n階無向圖中，n階零圖是連通分支最多的，。3311.2.2連通圖例11.2.2

判斷圖11.2.1中圖和的連通性，并求其連通分支數(shù)。圖11.2.1

例11.2.2示意圖解:容易看出是連通圖，所以，是非連通圖，連通關(guān)系的等價(jià)類為,,,它們的導(dǎo)出的子圖為的3個(gè)連通分支，所以。3411.2.2連通圖定義11.2.5

設(shè)為一個(gè)有向圖，若從到存在通路，則稱可達(dá)，記作，規(guī)定總是可達(dá)自身的，即。若且，則稱與是相互可達(dá)的，記作，規(guī)定。與都是V上的二元關(guān)系，并且不難看出是V

上的等價(jià)關(guān)系。定義11.2.6 設(shè)為一個(gè)有向圖，若D

的基圖是連通圖，則稱是D弱連通圖，簡稱為連通圖，若與至少成立其一，則稱D

是單向連通圖，若均有，則稱D

是強(qiáng)連通圖。圖11.2.2

連通性示意圖例3511.2.2連通圖在圖11.2.2中，(a)為強(qiáng)連通圖，(b)為單向連通圖，(c)為弱連通圖。由定義可知，強(qiáng)連通圖一定是單向連通圖，單向連通圖一定是弱連通圖。下面給出強(qiáng)連通圖與單向連通圖的判別定理。定理11.2.3設(shè)有向圖，D是強(qiáng)連通圖當(dāng)且僅當(dāng)D

中存在經(jīng)過每個(gè)頂點(diǎn)至少一次回路。證 充分性顯然。下面證明必要性。由的強(qiáng)連通性可知，設(shè)為到的通路。又因?yàn)?設(shè)為到的通路，則所圍成的回路經(jīng)過D中每個(gè)頂點(diǎn)至少一次。3611.2.2連通圖定理11.2.4設(shè)D是n階有向圖，D

是單向連通圖當(dāng)且僅當(dāng)D

中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的通路。下面介紹一種證明方法，叫“擴(kuò)大路徑法”。設(shè)為n階無向圖，,設(shè)為G中的一條路徑，若此路徑的始點(diǎn)或終點(diǎn)與通路外的頂點(diǎn)相鄰，就將它們擴(kuò)到通路中來，繼續(xù)這一過程，直到最后得到的通路的兩個(gè)端點(diǎn)不與通路外的頂點(diǎn)相鄰為止，設(shè)最后得到的路徑為(長度為的路徑擴(kuò)大成了長度為的路徑)，稱為“極大路徑”，稱使用此種方法證明問題的方法為“擴(kuò)大路徑法”。3711.2.2連通圖例11.2.3設(shè)G為階無向簡單圖，證明G中存在長度大于或等于4的圈。證 不妨設(shè)G是連通圖，否則，因?yàn)镚的各連通分支的最小度也都大于或等于3，因?yàn)榭蓪λ哪硞€(gè)連通分支進(jìn)行討論。設(shè)為G中任意兩個(gè)頂點(diǎn)，由G是連通圖，因而之間存在通路，由定理11.2.4的推論可知，之間存在路徑，用“擴(kuò)大路徑法”擴(kuò)大這條路徑，設(shè)最后得到的“極大路徑”為易知若與相鄰,則為長度大于或等于4的圈。否則，由于因而除與上的相鄰?fù)?，還存在上的頂點(diǎn)()和與相鄰，則為一個(gè)圈且長度大于或等于4，見圖11.2.3。3811.2.2連通圖圖11.2.3例11.2.3示意圖定義11.2.7設(shè)圖，若存在，使得,而對于任意的，均有，則稱是G的邊割集，簡稱為割集。若為單元集，即,則稱為割邊或橋。3911.2.3二部圖11.2.3二部圖定義11.2.6

設(shè)為一個(gè)無向圖，若能將V分成和()，使得G中的每條邊的兩個(gè)端點(diǎn)都是一個(gè)屬于，另一個(gè)屬于，則稱G為二部圖(或稱二分圖，偶圖等)，稱和為互補(bǔ)頂點(diǎn)子集，常將二部圖G記為又若G是簡單的二部圖，中每個(gè)頂點(diǎn)均與中所有頂點(diǎn)相鄰，則稱G為完全二部圖，記為注意，階零圖為二部圖。在圖11.2.4中所示各圖都是二部圖，其中，(a),(b),(c)為的子圖，(c)為完全二部圖常將畫成與其同構(gòu)的(e)的形式，是下文中經(jīng)常遇到的圖。(d)是的子圖，它是完全二部圖常畫成(f)的形狀。4011.2.3二部圖圖11.2.4

二部圖概念示意圖例4111.2.3二部圖一個(gè)圖是否為二部圖，可由下面定理判別。定理11.2.5

一個(gè)無向圖是二部圖當(dāng)且僅當(dāng)G中無奇數(shù)長度的回路。證 必要性。若G中無回路，結(jié)論顯然成立。若G中有回路，只需證明G中無奇圈。設(shè)C為G中任意一圈，令，易知不妨設(shè)，則必有,而必為偶數(shù)，于是C為偶圈，由C的任意性可知結(jié)論成立。充分性，不妨設(shè)G為連通圖，否則可對每個(gè)連通分支進(jìn)行討論，設(shè)為G中任意一個(gè)頂點(diǎn)，令4211.2.3二部圖易知，。下面只要證明中任意兩頂點(diǎn)不相鄰，中任意兩頂點(diǎn)也不相鄰。若存在相鄰，令()=,設(shè)到的短程線分別為則它們的長度，都是偶數(shù)，于是中一定含有奇圈，這與已知矛盾，類似可證，中也不存在相鄰的頂點(diǎn)，于是G為二部圖。由定理11.2.5可知，圖11.2.4中各圖都是二部圖，這比用定義判斷更方便。4311.3圖的矩陣表示在學(xué)習(xí)中常常需要分析圖并在圖上執(zhí)行各種過程和算法，有時(shí)必須用計(jì)算機(jī)來執(zhí)行這些算法，因此必須把圖的結(jié)點(diǎn)和邊輸入給計(jì)算機(jī)，由于集合與圖形都不適合計(jì)算機(jī)處理，所以要找到一種新的表示圖的方法，這就是圖的矩陣表示。11.3.1關(guān)聯(lián)矩陣定義11.3.1

設(shè)無向圖令為頂點(diǎn)與邊的關(guān)聯(lián)次數(shù)，則稱()為G的關(guān)聯(lián)矩陣,記作。圖11.3.1圖例4411.3.1關(guān)聯(lián)矩陣圖11.3.1所示無向圖的關(guān)聯(lián)矩陣為

不難看出，關(guān)聯(lián)矩陣有以下性質(zhì)：4511.3.1關(guān)聯(lián)矩陣(1)即每列元素之和均為2，這正說明每條邊關(guān)聯(lián)兩個(gè)頂點(diǎn)(環(huán)所關(guān)聯(lián)的兩個(gè)端點(diǎn)重合)。(2)，即第i行元素之和為的度數(shù)，(3)這個(gè)結(jié)果正是握手定理的內(nèi)容，即各頂點(diǎn)的度數(shù)之和等于邊數(shù)的2倍。(4)第j列與第k列相同，當(dāng)且僅當(dāng)邊與是平行邊，(5)當(dāng)且僅當(dāng)是孤立點(diǎn)。4611.3.1關(guān)聯(lián)矩陣定義11.3.2

設(shè)有向圖中無環(huán)，令則稱()為D的關(guān)聯(lián)矩陣，記作圖11.3.2圖例4711.3.1關(guān)聯(lián)矩陣圖11.3.2所示圖D的關(guān)聯(lián)矩陣為有如下各條性質(zhì)：(1)從而這說明中所有元素之和為0。(2)中，負(fù)1的個(gè)數(shù)等于正1的個(gè)數(shù)，都等于邊數(shù)m，這正是有向圖握手定理的內(nèi)容。(3)第行中，正1的個(gè)數(shù)等于負(fù)1的個(gè)數(shù)等于。(4)平行邊所對應(yīng)的列相同。4811.3.2鄰接矩陣11.3.2鄰接矩陣定義11.3.3

設(shè)有向圖,令為定點(diǎn)鄰接到定點(diǎn)邊的條數(shù),稱為D的鄰接矩陣,記作或簡記為.A。圖11.3.3圖例4911.3.2鄰接矩陣圖11.3.3所示有向圖D的鄰接矩陣為有向圖的鄰接矩陣有以下性質(zhì)：(1)于是類似地，而這也正反映了有向圖握手定理的內(nèi)容。(2)由(1)不難看出，中所有元素之和為D中長度為1的通路數(shù)，而為D中長度為1的回路(環(huán))的個(gè)數(shù)?，F(xiàn)在要求討論的問題是，如何利用計(jì)算出D中長度為的通路數(shù)和回路數(shù)。在這里通路是定義意義下的概念，不同起點(diǎn)的通路都看成是不同的，并且回路看成是通路的特殊情況。為了解決提出的問題，要計(jì)算的冪，把次冪記作或簡記作。設(shè)其中元素則為頂點(diǎn)到長度為的通路數(shù)，當(dāng)時(shí)，即的主對角線上的元素)為到長度為的通路總數(shù)，其中，為D中的長度為的回路總數(shù)，從以上分析可得出下面定理和推論。5011.3.2鄰接矩陣定理11.3.1設(shè)A為有向圖D的鄰接矩陣，為D的頂點(diǎn)集，則A的次冪()中元素為D中到長度為的通路數(shù)，其中為到自身長度為的回路數(shù)，而為D中長度為的通路總數(shù)，其中為D中長度為的回路總數(shù)。推論11.3.1設(shè)，則中元素為D中長度小于或等于的通路數(shù)，其中為D中長度小于或等于的回路數(shù)5111.3.2鄰接矩陣前面已經(jīng)計(jì)算出圖11.3.3所示有向圖D的鄰接矩陣A，下面給出從不難看出，D中到長度為1，2，3，4的通路分別為0，1，1，2條。到自身長度為1，2，3，4的回路分別為1，2，3，5條，其中有復(fù)雜回路。D中長度小于或等于4的通路53條，其中有15條為回路。5211.3.3可達(dá)矩陣定義11.3.4

設(shè)為有向圖，，令5311.4圖的運(yùn)算5411.5歐拉圖定義11.5.1設(shè)是無孤立結(jié)點(diǎn)的圖，若存在一條通路（回路），經(jīng)過圖中所有邊一次且僅一次稱為歐拉通路（回路）。具有歐拉回路的圖稱為歐拉圖,具有歐拉通路而無歐拉回路的圖稱為半歐拉圖。在這里做個(gè)規(guī)定,即平凡圖是歐拉圖。5511.5.1歐拉通路和回路5611.5.1歐拉通路和回路在圖11.5.1所示各圖中,為(a)中的歐拉回路,所以(a)圖為歐拉圖。為(b)中的歐拉通路,但圖中不存在歐拉回路,所以(b)為半歐拉圖。(c)中既沒有歐拉回路,也沒有歐拉通路,所以(c)不是歐拉圖,也不是半歐拉圖。為(d)圖中的歐拉回路,所以(d)圖為歐拉圖。(e),(f)圖中都既沒有歐拉回路,又沒有歐拉通路。5711.5.2半歐拉圖和歐拉圖定理11.5.1無向圖G是歐拉圖當(dāng)且僅當(dāng)是G連通圖,且G中沒有奇度頂點(diǎn)。證若G為平凡圖,結(jié)論是顯然成立,下面設(shè)G為非平凡圖,設(shè)G是m條邊的n階無向圖.并設(shè)的頂點(diǎn)集。必要性。因?yàn)镚為歐拉圖,所以G中存在歐拉回路,設(shè)C為G中任意一條歐拉回路,都在C上,因而,連通,所以G為連通圖。又,在C上每出現(xiàn)一次獲得2度,若出現(xiàn)k次就獲得2k度,即,所以G中無奇度頂點(diǎn)。5811.5.2半歐拉圖和歐拉圖5911.5.2半歐拉圖和歐拉圖圖11.5.2圖例由定理11.5.1立刻可知,圖11.5.1中的三個(gè)無向圖中,只有（a）中無奇度頂點(diǎn),因而（a）是歐拉圖,而（b）,（c）都是奇度頂點(diǎn),因而它們都不是歐拉圖。6011.5.2半歐拉圖和歐拉圖定理11.5.2

無向圖G是半歐拉圖當(dāng)且僅當(dāng)是G連通的,且G中恰有兩個(gè)奇度頂點(diǎn)。證必要性。設(shè)G是m條邊的n階無向圖,因?yàn)闉榘霘W拉圖,因而G中存在歐拉通路（但不存在歐拉回路）,設(shè)為中一條歐拉通路,，,若不在的端點(diǎn)出現(xiàn),顯然為偶數(shù),若在端點(diǎn)出現(xiàn),則為奇數(shù),因?yàn)橹挥袃蓚€(gè)端點(diǎn)且不同,因而G中只有兩個(gè)奇度頂點(diǎn)。另外,G的連通性是顯然的。充分性。設(shè)G的兩個(gè)奇度頂點(diǎn)分別為和,對G加新邊,得,則是連通且無奇度頂點(diǎn)的圖,由定理11.5.1可知,為歐拉圖,因而存在歐拉回路,而為中一條歐拉通路,所以為半歐拉圖。由定理11.5.2立即可知,圖11.5.1中（b）是半歐拉圖,但(c)不是半歐拉圖。6111.5.2半歐拉圖和歐拉圖定理11.5.3

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

有向圖D半歐拉圖當(dāng)且僅當(dāng)D是單向連通的,且D中恰有兩個(gè)奇度頂點(diǎn),其中一個(gè)的入度比出度大1,另一個(gè)的出度比入度大1,而其余頂點(diǎn)的入度都等于出度。由定理11.5.3和11.5.4立即可知,圖11.5.1中所示三個(gè)有向圖中只有（d）是歐拉圖,沒有半歐拉圖.6211.5.2半歐拉圖和歐拉圖6311.5.2半歐拉圖和歐拉圖定理11.5.5G是非平凡的歐拉圖當(dāng)且僅當(dāng)G是連通的且為若干個(gè)邊不重的圈的并。本定理的證明可用歸納法。例11.5.1設(shè)G是非平凡的且非環(huán)的歐拉圖,證明：（1）≥2。（2）對于G中任意兩個(gè)不同頂點(diǎn),都存在簡單回路C含u和v。6411.5.2半歐拉圖和歐拉圖6511.5.2半歐拉圖和歐拉圖Fleury算法：（1）任取,令.（2）設(shè)已經(jīng)行遍,按下面方法來從中選取：（a）與先關(guān)聯(lián)；（b）除非無別的邊可供行遍,否則不應(yīng)該為中的橋。（3）當(dāng)（2）不能再進(jìn)行時(shí),算法停止?？梢宰C明,當(dāng)算法停止時(shí)所得簡單回路為G中一條歐拉回路。6611.5.2半歐拉圖和歐拉圖6711.5.2半歐拉圖和歐拉圖解此人行遍是犯了能不走橋就不走橋的錯誤,因而它沒行遍出歐拉回路。當(dāng)他走到時(shí),為圖11.5.4(b)所示.此時(shí)為該圖中的橋,而,均不是橋,他不應(yīng)該走,而應(yīng)該走或,他沒有走,所以犯了錯誤.注意此人在行遍中,在遇到橋處遇到過橋,但當(dāng)時(shí)除橋外他無別的邊可走,所以當(dāng)時(shí)均走了橋,這是不會犯錯誤的。通過以上討論,已經(jīng)看出了歐拉圖的一些特征。Fleury算法,反應(yīng)了歐拉圖能“一筆畫出”,這就是中國人早就稱“一筆畫”的問題。所以一個(gè)圖能一筆畫出,是指從圖某一點(diǎn)出發(fā),線可以相交但不能重合將圖畫完的問題（終點(diǎn)與始點(diǎn)重合的對應(yīng)歐拉圖,不重合的對應(yīng)半歐拉圖）。6811.5.3哥尼斯堡七橋問題18世紀(jì)中葉,當(dāng)時(shí)在歐洲普魯士境內(nèi)稱為哥尼斯堡城的城市有一條貫穿全市的普雷格爾河,河中有兩個(gè)小島,由七座橋相連接（如圖11.5.5中(a)所示）。當(dāng)時(shí)該城市中的人們熱衷于一個(gè)難題：一個(gè)人怎樣不重復(fù)地走完七橋,最后回到出發(fā)點(diǎn)？試驗(yàn)者都沒有解決這個(gè)難題。1736年,瑞士數(shù)學(xué)家歐拉(Euler)發(fā)表圖論的首篇論文,論證了該問題無解,他論證所用的圖為圖11.5.5中(b)所示。后人為了紀(jì)念數(shù)學(xué)家歐拉,將這個(gè)難題稱為“哥尼斯保七橋問題”,將其有經(jīng)過所有邊的簡單生成回路的圖稱為歐拉圖。6911.5.3哥尼斯堡七橋問題7011.6哈密頓圖1859年，數(shù)學(xué)家哈密頓(Hamilton)提出一個(gè)問題：能否在正十二面體圖（見11.6.4中的圖（a））上求一條初級回路,使它含圖中所有頂點(diǎn)？他形象地將每個(gè)頂點(diǎn)比作一個(gè)城市,連接兩個(gè)頂點(diǎn)之間的邊看作城市之間的交通線。于是原始問題就是變成了所謂的周游世界問題：能否從某個(gè)城市出發(fā)沿交通經(jīng)過每個(gè)城市一次并且僅一次,最后回到出發(fā)點(diǎn)？哈密頓自己做了肯定的回答。后人為了紀(jì)念這位數(shù)學(xué)家，將經(jīng)過圖中每個(gè)頂點(diǎn)一次且僅一次的回路稱為哈密頓回路,將有這種回路的圖形稱為哈密頓圖。7111.6.1哈密頓圖定義11.6.1經(jīng)過圖（有向圖和無向圖）中所有頂點(diǎn)一次且僅一次的通路(回路)稱為哈密頓通路(回路)。具有哈密頓回路的圖稱為哈密頓圖，具有哈密頓通路但不具有哈密頓回路的圖稱為半哈密頓圖，平凡圖是哈密頓圖。圖11.5.1中所示的三個(gè)無向圖都有哈密頓回路,所以都是哈密頓圖,有向圖中,（d）具有哈密頓回路,因而它是哈密頓圖。（e）只有哈密頓通路,但無哈密頓回路,因而它是半哈密頓圖,而（f）中既無哈密頓回路,也沒有哈密頓通路,因而不是哈密頓圖,也不是半哈密頓圖。從定義上可以看出,哈密頓通路是圖中生成的初級通路,而哈密頓回路是生成的初級回路.判斷一個(gè)圖是否為哈密頓圖,就是判斷能否將圖中所有頂點(diǎn)都放置在一個(gè)初級回路（圈）上，但這不是一件易事。與判斷一個(gè)圖是否為歐拉圖不一樣,到目前為止,人們還沒有找到哈密頓圖簡單的充分必要條件。下面給出的定理都是哈密頓通路（回路）的必要條件或充分條件。7211.6.1哈密頓圖定理11.6.1

設(shè)無向圖是哈密頓圖,對于任意且,均有其中,為的連通分支數(shù)。證設(shè)C為G中任意一條哈密頓回路,易知,當(dāng)中頂點(diǎn)在C上均不相鄰時(shí),達(dá)到最大值,而當(dāng)中頂點(diǎn)在C上有彼此相鄰的情況時(shí),均有＜,所以有≤。而C是G的生成子圖,所以,有≤≤。本定理的條件是哈密頓圖的必要條件,但不是充分條件.可以驗(yàn)證彼得松圖（圖11.6.1）滿足定理中的條件,但它不是哈密頓圖.當(dāng)然,若一個(gè)圖不滿足定理中的條件,它一定不是哈密頓圖。7311.6.1哈密頓圖7411.6.1哈密頓圖75第十一章圖的基本概念

7611.6.2哈密頓圖的充分條件下面給出一些哈密頓圖和半哈密頓圖的充分條件。定理11.6.2

設(shè)G是n階無向圖簡單圖,若對于G中任意不相鄰的頂點(diǎn)均有≥（11.6.1）則G中存在哈密頓通路。證首先證明是G連通圖.否則G至少有兩個(gè)連通分支,設(shè),是階數(shù)為的兩個(gè)連通分支,設(shè),,因?yàn)镚是簡單圖,所以≤≤這與（11.6.1）矛盾,所以G必為連通圖.7711.6.2哈密頓圖的充分條件下面證G中存在哈密頓通路。設(shè)為G中用“擴(kuò)大路徑法”得到的“極大路徑”,即的始點(diǎn)與終點(diǎn)不與外的頂點(diǎn)相鄰。顯然有≤n。（1）若=n,則為G中哈密頓通路。（2）若,這說明不是哈密頓通路,即G中還存在著外的頂點(diǎn)。但可以證明G中存在過上所有的頂點(diǎn)的圈。（a）若與相鄰,即,則為滿足要求的圈。7811.6.2哈密頓圖的充分條件7911.6.2哈密頓圖的充分條件8011.6.2哈密頓圖的充分條件推論11.6.2

設(shè)G為n(n≥3)階無向簡單圖,若對G于中任意兩個(gè)不相鄰的頂點(diǎn),均有≥n（11.6.2）則G中存在哈密頓回路,從而G為哈密頓圖。證由定理11.6.2可知,G中存在哈密頓通路,設(shè)為G中一條哈密頓通路,若與相鄰,設(shè)邊,則為G中哈密頓回路。若與不相鄰,應(yīng)用（11.6.2）,同定理11.6.2證明中的（2）類似,可證明存在過上各頂點(diǎn)的圈,此圈即為G中的哈密頓回路。8111.6.2哈密頓圖的充分條件定理11.6.3

設(shè)為n階無向簡單圖G中兩個(gè)不相鄰的頂點(diǎn),且≥n,則G為哈密頓圖當(dāng)且僅當(dāng)為哈密頓圖（是加的新邊）。本定理的證明留作習(xí)題.例11.6.2

在某次國際會議的預(yù)備會中,共有8人參加,他們來自不同的國家.已知他們中任何兩個(gè)無共同語言的人中的每一個(gè),與其余有共同語言的人數(shù)之和大于或等于8,問能否將這八個(gè)人排在圓桌旁,使其任何人都能與兩邊的人交談。8211.6.2哈密頓圖的充分條件8311.6.2哈密頓圖的充分條件8411.6.2哈密頓圖的充分條件8511.7帶權(quán)圖8611.8平面圖11.8.1平面圖的基本概念及性質(zhì)定義11.8.1

如果能把一個(gè)無向圖G的所有結(jié)點(diǎn)和邊畫在平面上,使得任何兩邊除公共結(jié)點(diǎn)外沒有其他交叉點(diǎn),則稱G為平面圖(planegraph),否則稱G為非平面圖(nonplanargraph)。應(yīng)當(dāng)注意,有些圖從表面上看他的某些邊是相交叉的,但是不能就此肯定它不是平面圖.有的圖進(jìn)行改畫之后,則可看出他是一個(gè)平面圖,這種圖形表示稱為平面圖的平面表示。有的無論如何改畫,除去結(jié)點(diǎn)外,總有邊相交叉。8711.8.1平面圖的基本概念及性質(zhì)（平凡圖）,都是平面圖,其中本身就已經(jīng)是平面嵌入,的平面嵌入為圖11.8.1中（d）所示。（刪除任意一條邊）也是平面圖,它的平面嵌入可表示為圖11.8.1中（e）.完全二部圖(n≥1),(n≥2)也都是平面圖,其中標(biāo)準(zhǔn)畫法畫出的已經(jīng)是平面嵌入,的平面嵌入可由圖11.8.1中（f）給出。圖11.8.1中（a）,（b）,（c）分別為,,的標(biāo)準(zhǔn)畫法。8811.8.1平面圖的基本概念及性質(zhì)8911.8.1平面圖的基本概念及性質(zhì)定理11.8.1

若圖G是平面圖,則G的任何子圖都是平面圖。由定理11.8.1立刻可知,(n≤4)和(n≥1)的所有子圖都是平面圖。定理11.8.2

若圖G是非平面圖,則G的任何母圖也都是非平面圖。推論11.8.1(n≥5)和(n≥3)都是非平面圖。本推論由,不是平面圖及定理11.8.1得證。還有一個(gè)明顯的事實(shí)也用定理給出。9011.8.1平面圖的基本概念及性質(zhì)定理11.8.3

設(shè)G是平面圖,則在G中加平行邊或環(huán)后所得圖還是平面圖.本定理說明平行邊和環(huán)不影響圖的平面性,因而在研究一個(gè)圖是否為平面圖時(shí)可不考慮平行邊和環(huán)。定義11.8.2

設(shè)G是平面圖（且已是平面嵌入）,由G的邊先將G所在的平面劃分成若干個(gè)區(qū)域,每個(gè)區(qū)域都稱為G的一個(gè)面。其中面積無限的面稱為無限面或外部面,面積有限的面積稱為有限面或內(nèi)部面,包圍每個(gè)面的所有邊組的回路組稱為該面的邊界,邊界的長度稱為該面的次數(shù)。9111.8.1平面圖的基本概念及性質(zhì)9211.8.1平面圖的基本概念及性質(zhì)定理11.8.4平面圖G中所有面的次數(shù)之和等于邊數(shù)m的兩倍,即其中r為G的面數(shù).證本定理中所說平面圖當(dāng)然是指平面嵌入。,若e為面和的公共邊界上的邊時(shí),在計(jì)算和的次數(shù)時(shí),e各提供1。而當(dāng)e只在某一個(gè)面的邊界上出現(xiàn)時(shí),如圖11.8.2中的邊i，則在計(jì)算該面的次數(shù)時(shí),e提供2。于是每條邊在計(jì)算總次數(shù)時(shí)都提供2，因而。9311.8.1平面圖的基本概念及性質(zhì)定義11.8.3

設(shè)G為簡單平面圖,若在G的任意不相鄰的頂點(diǎn)之間加邊,所得圖為非平面圖,則稱G為極大平面圖。從定義不難看出,（刪除任意一條邊）都是極大平面圖。還可以容易地證明下面兩個(gè)定理。定理11.8.5

極大平面圖是連通的。極大平面圖的最大特點(diǎn)由下面定理給出。9411.8.1平面圖的基本概念及性質(zhì)9511.8.2庫拉托夫基定理1930年波蘭數(shù)學(xué)家?guī)炖蟹蛩够?Kuratowski)給出了判斷平面圖的充要條件。定理11.8.7(庫拉托夫基定理)一個(gè)圖是平面圖的充分必要條件是它的任何子圖都不可能收縮為或者是的子圖。和也稱為庫拉托夫基圖。推論11.8.2

一個(gè)圖是非平面圖的充分必要條件是它存在一個(gè)能收縮為或的子圖。9611.8.2庫拉托夫基定理9711.8.3平面圖著色及應(yīng)用圖著色的問題的研究起源于“四色猜想”。所謂四色猜想問題，是要求證明這樣的問題：至多用四種不同顏色給平面或球面上的地圖著色，使相鄰的國家由不同的顏色區(qū)分，這個(gè)問題提出來已經(jīng)近150年了，但時(shí)至今日還沒有得到徹底解決。著色問題包含點(diǎn)著色,邊著色,平面圖的面著色等問題。定義11.8.4

對無環(huán)圖無向圖G的每個(gè)頂點(diǎn)涂上一種顏色,使相鄰的頂點(diǎn)涂不同的顏色,稱為對圖G的一種著色。若能用k種顏色給G的頂點(diǎn)著色,就稱對G進(jìn)行了k著色,也稱G是k–可著色的（k–colorable）。若Gk是–可著色的但不是（k-1）–可著色的,就稱G是k色圖,并稱這樣的k為G的色數(shù),記作,不混淆時(shí),色數(shù)也可簡記做。9811.8.3平面圖著色及應(yīng)用9911.8.3平面圖著色及應(yīng)用10011.8.3平面圖著色及應(yīng)用定義11.8.5

連通無橋平面圖的平面嵌入及其所有的面稱為平面地圖或地圖,地圖的面稱為“國家”。若兩個(gè)國家的邊界至少有一條公共邊,則稱這兩個(gè)國家是相鄰的。定義11.8.6

對地圖G的每個(gè)國家涂上一種顏色,使相鄰的國家涂不同的顏色,稱為對G的一種面著色,若能用k種顏色給G的面著色,就稱對G的面進(jìn)行了k著色,或稱G是k－面可著色的。若G是k－面可著色的,但不是（k–1）－面可著色的，就稱G的面色數(shù)為k,記作。10111.8.3平面圖著色及應(yīng)用研究地圖的著色可以轉(zhuǎn)化成對它的對偶圖的點(diǎn)著色,