復(fù)習(xí)思考題15完全圖Kn(n3)都是歐拉圖。

()完全二部圖Kn,m(n,m1)都是哈密頓圖.()重新畫(huà)下圖的平面嵌入，使其外部面的次數(shù)分別為1，3，4。上圖是極大平面圖。()5階7條邊的連通平面圖共有______個(gè)面。設(shè)G為8階極大平面圖，則G的面數(shù)r=___R0R1R2R3第6章特殊的圖

6.1二部圖6.2歐拉圖6.3哈密頓圖6.4平面圖

歐拉公式：設(shè)G為

n階

m條邊

r個(gè)面的連通平面圖，則

nm+r=2歐拉公式的推廣設(shè)G為n階m條邊r個(gè)面有p(p2)個(gè)連通分支的平面圖,則

nm+r=p+1證

:設(shè)第i個(gè)連通分支有ni個(gè)頂點(diǎn),mi條邊和ri個(gè)面.對(duì)各連通分支用歐拉公式,

ni

mi+ri=2,i=1,2,…,p求和即注意到

即得

nm+r=p+1平面圖的性質(zhì)定理

設(shè)G是連通的平面圖，有n頂點(diǎn)、m條邊，每個(gè)面的次數(shù)至少為k(k≥3)，則證：設(shè)G中有r個(gè)面，由平面圖的面與次數(shù)定理

由歐拉公式nm+r=2，得2mkr=k(2+m-n)，整理得判斷一個(gè)圖是否是連通平面圖的必要條件平面圖的性質(zhì)定理

設(shè)G有p(p2)個(gè)連通分支的平面圖，有n個(gè)結(jié)點(diǎn)，m條邊，每個(gè)面的次數(shù)至少為k(k≥3)，推論

K5

和K3,3不是平面圖.證:

用反證法,假設(shè)它們是平面圖,則K5:n=5,m=10,k=3

矛盾！

K3,3

:n=6,m=9,k=4(二部圖)

矛盾！K5K3,3所以，K5

和K3,3不是平面圖.消去和插入

消去對(duì)度數(shù)為2的結(jié)點(diǎn)，去掉此結(jié)點(diǎn)，使它關(guān)聯(lián)的兩條邊變成一條邊，插入插入一個(gè)新的度數(shù)為2的結(jié)點(diǎn)，使一條邊分成兩條邊，消去v插入v同胚與收縮

G1與G2同胚

G1與G2同構(gòu),或經(jīng)過(guò)反復(fù)插入、或消去2度頂點(diǎn)后同構(gòu)收縮邊e庫(kù)拉圖斯基定理定理6.13

G中不含與K5同胚的子圖,

G是平面圖

G也不含與K3,3同胚的子圖.定理6.14

G中無(wú)可收縮為K5的子圖,G是平面圖

G也無(wú)可收縮為K3,3的子圖.

例：證明下圖均為非平面圖

證圖中紅色部分與K3,3同胚消去圖中紅色部分與K5同胚消去平面圖G=<V,E>的對(duì)偶圖G*=<V*,E*>的構(gòu)造方法

在G的每一個(gè)面Ri中任取一個(gè)點(diǎn)vi*作為G*的頂點(diǎn),

V*={vi*|i=1,2,…,r}.對(duì)G每一條邊ek,若ek在G的面Ri與Rj的公共邊界上,則作邊ek*=(vi*,vj*),且與ek相交;若ek為G中的橋且在面Ri的邊界上,則作環(huán)ek*=(vi*,vi*).

E*={ek*|k=1,2,…,m}.平面圖的對(duì)偶圖的實(shí)例例黑色實(shí)線為原平面圖,紅色虛線為其對(duì)偶圖

兩個(gè)原平面圖同構(gòu),但它們的對(duì)偶圖不同構(gòu)！

度數(shù)列:3,3,6度數(shù)列:3,4,5平面圖G的對(duì)偶圖G*的性質(zhì)G*是平面圖，而且是平面嵌入.G*是連通圖若邊e為G中的環(huán)，則G*與e對(duì)應(yīng)的邊e*為橋;若e為橋，則G*中與e對(duì)應(yīng)的邊e*為環(huán).在多數(shù)情況下，G*含有平行邊.G的對(duì)偶圖的對(duì)偶圖不一定與G同構(gòu)。同構(gòu)的平面圖的對(duì)偶圖不一定同構(gòu).設(shè)G*是任意連通圖的平面圖G的對(duì)偶圖，n*,m*,r*和n,m,r分別為G*和G的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)，(1)n*=r(2)m*=m(3)r*=n

右圖原圖中：n=5，m=6，r=3對(duì)偶圖中：n*=3，m*=6，r*=5平面圖與對(duì)偶圖的階數(shù)、邊數(shù)與面數(shù)之間的關(guān)系應(yīng)用實(shí)例下圖是一所房子的俯視圖G，設(shè)每一面墻都有一扇門(mén)，問(wèn)能否從某個(gè)房間開(kāi)始，過(guò)每扇門(mén)一次，最后返回。解題思路：作G的對(duì)偶圖G*，原問(wèn)題就轉(zhuǎn)化為：G*是否存在歐拉回路應(yīng)用實(shí)例下圖是一所房子的俯視圖G，設(shè)每一面墻都有一扇門(mén)，問(wèn)能否從某個(gè)房間開(kāi)始，過(guò)每扇門(mén)一次，最后返回。解題思路：作G的對(duì)偶圖G*，原問(wèn)題就轉(zhuǎn)化為：G*是否存在歐拉回路應(yīng)用實(shí)例下圖是一所房子的俯視圖G，設(shè)每一面墻都有一扇門(mén)，問(wèn)能否從某個(gè)房間開(kāi)始，過(guò)每扇門(mén)一次，最后返回。因?yàn)閷?duì)偶圖G*中有兩個(gè)節(jié)點(diǎn)的度數(shù)為奇數(shù)，因此G*中不存在歐拉回路，本題無(wú)解。圖的著色點(diǎn)著色設(shè)無(wú)向圖G無(wú)環(huán),

對(duì)G的每個(gè)頂點(diǎn)涂一種顏色，使相鄰的頂點(diǎn)涂不同的顏色，稱(chēng)為圖G的一種點(diǎn)著色,簡(jiǎn)稱(chēng)著色．k-可著色若能用k種顏色給G的頂點(diǎn)著色，則稱(chēng)G是k-可著色的．圖的著色問(wèn)題——

用盡可能少的顏色給圖著色.例121222111111222322221111311122234圖的著色舉例1122221112123213321232314對(duì)一個(gè)圖著色,通常是先畫(huà)出該圖的對(duì)偶圖,然后對(duì)對(duì)偶圖中的點(diǎn)著色.例圖著色問(wèn)題的應(yīng)用——有沖突情況下的分配資源有N項(xiàng)工作，每項(xiàng)工作需要一天的時(shí)間完成，有些工作由于需要相同的人員或設(shè)備而不能同時(shí)進(jìn)行，問(wèn)至少需要幾天才能完成所有的工作？用圖描述如下：用頂點(diǎn)表示工作，若兩項(xiàng)工作不能同時(shí)進(jìn)行，就用一條邊連接對(duì)應(yīng)的頂點(diǎn)。工作的時(shí)間安排對(duì)應(yīng)于這個(gè)圖的點(diǎn)著色：

著同一種顏色的頂點(diǎn)對(duì)應(yīng)的工作可以安

排在同一天，所需的最少天數(shù)正好是這個(gè)圖著色所需要的最少顏色數(shù)。圖的著色舉例學(xué)生會(huì)下設(shè)6個(gè)分會(huì),

每個(gè)月每個(gè)分會(huì)都要開(kāi)一次會(huì),為了確保每個(gè)人都能參加他所在的分會(huì)會(huì)議,這6個(gè)會(huì)議至少要安排在幾個(gè)不同時(shí)間段?用頂點(diǎn)v1~v6代表第一到六分會(huì)，當(dāng)兩個(gè)分會(huì)中有共同的人則兩個(gè)頂點(diǎn)間有一條邊頂點(diǎn)內(nèi)的數(shù)字代表顏色。數(shù)字相同表示可以在同一時(shí)間開(kāi)會(huì)v4v3v2v1v5v6123412至少要4個(gè)時(shí)段第1時(shí)段:一,四第2時(shí)段:二,五第3時(shí)段:三第4時(shí)段:六分會(huì)成員1張,李,王2李,趙,劉3張,劉,王4趙,劉,孫5張,王6李,劉,王地圖:是連通、無(wú)橋、平面圖的平面嵌入,每一個(gè)面是一個(gè)國(guó)家.若兩個(gè)國(guó)家有公共邊界,則稱(chēng)它們是相鄰的.地圖著色(面著色):對(duì)地圖的每個(gè)國(guó)家涂一種顏色，使相鄰的國(guó)家涂不同的顏色.地圖著色問(wèn)題——用盡可能少的顏色給地圖著色。地圖著色可以轉(zhuǎn)化成平面圖的點(diǎn)著色.

當(dāng)G中無(wú)橋時(shí),G*中無(wú)環(huán).G的面與G*的頂點(diǎn)對(duì)應(yīng),

且G的兩個(gè)面相鄰當(dāng)且僅當(dāng)G*對(duì)應(yīng)的兩個(gè)頂點(diǎn)相鄰,

從而G的面著色等同于G*的點(diǎn)著色.地圖著色四色問(wèn)題（1852）

格思里(FrancisGuthrie)注意到美國(guó)地圖可以用4種顏色染色，使得相鄰區(qū)域(有一段公共邊界，不只是有一個(gè)公共點(diǎn))有不同顏色，提出四色猜想。四色猜想——

任何地圖都可以用4種顏色著色,即任何平面圖都是4-可著色的.四色定理五色定理——任何平面圖都是5-可著色的.（1890年已被證明）四色定理——任何平面圖都是4-可著色的.1976年兩位美國(guó)數(shù)學(xué)家證明,如果四色猜想不成立,則存在一個(gè)反例,這個(gè)反例大約有2000種可能(后來(lái)有人簡(jiǎn)化到600多種),該問(wèn)題的證明破天荒地使用了的計(jì)算機(jī)，數(shù)學(xué)家們用了一百多億次邏輯判斷，花了1200多機(jī)時(shí)給出了四色猜想的證明，證明的正確性如不借助于計(jì)算機(jī)就無(wú)法檢驗(yàn)。他們用計(jì)算機(jī)分析了所有這些可能,都沒(méi)有導(dǎo)致反例.至今還沒(méi)有找到能用“紙和筆”給出的證明。第7章樹(shù)7.1無(wú)向樹(shù)及生成樹(shù)7.2根樹(shù)及其應(yīng)用引例樹(shù)是一類(lèi)既簡(jiǎn)單而又非常重要的圖，它是計(jì)算機(jī)中一種基本的數(shù)據(jù)結(jié)構(gòu)和表示方法。在輸電網(wǎng)絡(luò)分析、有機(jī)化學(xué)、最短連接及渠道設(shè)計(jì)等領(lǐng)域也都有廣泛的應(yīng)用，如：某地區(qū)有若干個(gè)主要城市，擬修建高速公路把這些城市連接起來(lái)，為使任何兩個(gè)城市都可以直接或間接到達(dá)，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最??？

____最小生成樹(shù)問(wèn)題

7.1

無(wú)向樹(shù)及生成樹(shù)無(wú)向樹(shù):連通無(wú)回路的無(wú)向圖。樹(shù)葉:樹(shù)中度數(shù)為1的頂點(diǎn)。分支點(diǎn):樹(shù)中度數(shù)2的頂點(diǎn)。規(guī)定：平凡圖也是樹(shù)，叫平凡樹(shù)。森林:每個(gè)連通分支都是樹(shù)的非連通的無(wú)向圖。聲明:本章中所討論的回路均指簡(jiǎn)單回路或初級(jí)回路。(a)樹(shù)(b)森林無(wú)向樹(shù)的幾個(gè)等價(jià)定義定理7.1

設(shè)G=<V,E>是n階m條邊的無(wú)向圖，則下面各命題是等價(jià)的：（1）G是樹(shù)(連通、無(wú)回路);（2）G中每對(duì)頂點(diǎn)之間具有惟一的一條路徑;（3）G中無(wú)回路且m=n1;（4）G是連通的且m=n1;（5）G是連通的且G中任何邊均為橋;（6）G中無(wú)回路,但在任兩個(gè)不相鄰的頂點(diǎn)之間加一條新邊后所得圖中有惟一的一個(gè)含新邊的回路.