一些特殊的圖

§1二部圖二部圖(偶圖)：G=<V1,V2,E>完全二部圖(完全偶圖)：Kn,m，其中|V1|=n,|V2|=m.無向圖G是二部圖當且僅當G中無奇數(shù)長度的回路。8/12/20241第四部分：圖論（授課教師：向勝軍）匹配設G=<V,E>是簡單無向圖，E*

E，若E*中任意兩邊均不相鄰，則稱E*為G中的匹配(或邊獨立集)。若在E*上再加任意一條邊，就不再是匹配，則稱E*為極大匹配，邊數(shù)最多的極大匹配稱為最大匹配，其邊數(shù)稱為匹配數(shù)(或邊獨立數(shù))，記為

1(G)，簡記為

1

。若M是圖G中的一個匹配，對任意v

VG,若存在M中的邊與v關聯(lián)，則稱v為M飽和點，否則稱v為M非飽和點。若G中每個點都是M飽和點，則稱M是G中的完美匹配。8/12/20242第四部分：圖論（授課教師：向勝軍）完備匹配設G=<V1,V2,E>是二部圖，若G中的匹配M飽和V1或V2中所有頂點，則稱M為完備匹配。

注意：完備匹配一定是最大匹配，但僅當|V1|=|V2|才是完美匹配。

此圖無完備匹配V1到V2的完備匹配8/12/20243第四部分：圖論（授課教師：向勝軍）存在完備匹配的充分必要條件Hall定理：二部圖G=<V1,V2,E>,|V1||V2|,G中存在V1到V2的完備匹配當且僅當V1中任意k個頂點(k=1,2,…|V1|)至少鄰接V2中k個頂點。存在完備匹配的一個充分條件二部圖G=<V1,V2,E>，若V1中每個頂點至少關聯(lián)t條邊，而V2中每個頂點至多關聯(lián)t條邊，則G中存在V1到V2的完備匹配。證明：任取V1中的k(k=1,2,…|V1|)個頂點，他們關聯(lián)的邊至少為kt條，但V2中每個頂點至多為t度，所以這kt條邊至少關聯(lián)V2中的k個頂點。這滿足Hall定理要求的前提，所以，G中存在V1到V2的完備匹配。8/12/20244第四部分：圖論（授課教師：向勝軍）求最大匹配的一個例子x1x2x3x4x5y1y2y3y4y5已知5個職員x1,x2,

x3,

x4,

x5和5項工作y1,

y2,

y3,

y4,

y5的匹配如圖所示，求其最大匹配。求解過程：(1)取一初始匹配M.(2)分析M非飽和頂點，調(diào)整匹配方案。8/12/20245第四部分：圖論（授課教師：向勝軍）LeonhardEuler(1707-1783)Swissmathematician,whostudiedattheUniv.ofBaselundertheSwissmathematicianJohannBernoulli,obtaininghismaster’sdegreeattheageof16.HeworkedasamemberofthefacultyoftheAcademyofScienceinSaintPertersburg,Russiaformorethan30years.“歐拉計算毫不費力，就象人呼吸，或者鷹在風中保持平衡一樣”(阿拉戈語),這不是對歐拉無與倫比的數(shù)學才能的夸大，歐拉是歷史上著作最多的數(shù)學家，被他的同代人稱為“分析的化身”。甚至在他生命的最后十年中的完全失明，也沒有妨礙他的無與倫比的多產(chǎn)；事實上，失去視力有什么影響的話，那就是使歐拉對他想象中的內(nèi)部世界的洞察力更加敏銳。摘自貝爾：《數(shù)學精英》§2歐拉圖8/12/20246第四部分：圖論（授課教師：向勝軍）K?nigsberg七橋問題問題的抽象：用頂點表示對象-“地塊”用邊表示對象之間的關系-“有橋相連”能否從河岸或小島出發(fā)，通過每一座橋，而且僅僅通過一次回到原地。

Euler(歐拉)1736年對這個問題，給出了否定的回答。將河岸和小島作為圖的頂點，七座橋為邊，構(gòu)成一個無向重圖，問題化為圖論中簡單通路的問題。8/12/20247第四部分：圖論（授課教師：向勝軍）歐拉通路和歐拉回路包含圖中每條邊的簡單通路稱為歐拉通路。包含圖中每條邊的簡單回路稱為歐拉回路。如果圖G中含歐拉回路，則圖G稱為歐拉圖。如果圖G中有歐拉通路，但沒有歐拉回路，則圖G稱為半歐拉圖。歐拉圖半歐拉圖無歐拉通路8/12/20248第四部分：圖論（授課教師：向勝軍）歐拉圖的判定連通無向圖G是歐拉圖當且僅當G中每個頂點的度均為偶數(shù)。連通無向圖G具有歐拉通路當且僅當G有零個或兩個奇度頂點。連通有向圖D是歐拉圖當且僅當D中每個頂點的入度等于出度。連通有向圖D具有歐拉通路當且僅當D中除了兩個頂點外，其余頂點的入度均等于出度。這兩個特殊的頂點中，一個頂點的入度比出度大1，另一個頂點的入度比出度小1。8/12/20249第四部分：圖論（授課教師：向勝軍）中國郵遞員問題(歐拉通路的應用)(加權(quán)圖)問題:

郵遞員從郵局出發(fā)，走遍投遞區(qū)域的所有街道，送完郵件后回到郵局，怎樣使所走的路線全程最短。若街道圖（街道的交叉口為頂點）存在歐拉通路，顯然此路是全程最短。8/12/202410第四部分：圖論（授課教師：向勝軍）每轉(zhuǎn)一個觸點，信號

1

2

3

4變成2

3

4

5，前者后三位決定了后者的前三位。因此，可把所有三位二進制數(shù)作頂點，從每一個頂點1

2

3到2

3

4引一條有向邊表示1

2

3

4這個4位二進制數(shù)，做出表示所有可能的碼變換的有向圖。于是問題轉(zhuǎn)化為在這個有向圖上求一條歐拉回路。該圖中的8個頂點的次數(shù)都為出度、入度均為2，由定理知，歐拉回路存在。求出一條歐拉回路對應的布魯英序列是：0111100101101000有向歐拉圖的例子一個模數(shù)轉(zhuǎn)換中的應用舉例：旋轉(zhuǎn)鼓設計：只需要16個物理觸點便可以表示0-15總共16個不同的狀態(tài)。如何安排這16個觸點使每轉(zhuǎn)過一個觸點都得到一個不同的二進制信號。（求布魯英序列）8/12/202411第四部分：圖論（授課教師：向勝軍）§3哈密爾頓圖1859年英國數(shù)學家哈密爾頓提出了一種名為“周游世界”的游戲：

用一個正十二面體的二十個頂點代表二十個大城市，

要求游戲者從某一城市出發(fā)，遍歷各城市一次，最后回到原地。這就是“繞行世界”問題。即找一條經(jīng)過所有頂點（城市）的基本通路（回路）。8/12/202412第四部分：圖論（授課教師：向勝軍）SirWilliamHamilton(1805-1865)愛爾蘭歷史上最偉大的科學家。關于哈密爾頓早期的才能的傳說，讀起來象一篇拙劣的虛構(gòu)的故事，但它是真實的。(例如，在十歲時，他差不多掌握了大多數(shù)主要東方語言)

哈密爾頓在進大學以前從未上過學…(他)輕而易舉地取得第一名，進入三一學院?！髮W生涯的結(jié)束，比它開始還要更令人驚奇；…都柏林大學理事會一致選舉當時22歲的大學生哈密爾頓為教授。在23歲時，他發(fā)表了他還是一個17歲的孩子時作出的“奇怪的發(fā)現(xiàn)”，…即《光線系統(tǒng)理論》第一部分，這是一篇偉大的杰作，它對于光學，就象拉格朗日的《分析力學》之于力學。哈密爾頓最深刻的悲劇既不是酒精，也不是他的婚姻，而是他頑固地相信，四元數(shù)是解決物質(zhì)宇宙的數(shù)學關鍵?！瓘膩頉]有一個偉大的數(shù)學家這樣毫無希望地錯誤過。摘自貝爾：《數(shù)學精英》“我長期以來欣賞托勒密對他偉大的天文學大師希巴克斯的描繪：‘一個熱愛勞動和熱愛真理的人’。但愿我的墓志銘也如此?！?威廉?哈密爾頓8/12/202413第四部分：圖論（授課教師：向勝軍）哈密爾頓回路和哈密爾頓通路經(jīng)過圖G中所有頂點的基本回路稱為哈密爾頓回路，若G中含哈密爾頓回路，則稱G為哈密爾頓圖。經(jīng)過圖G中所有頂點的基本通路稱為哈密爾頓通路，若G

中含哈密爾頓通路，但不含

哈密爾頓回路，則稱G為

半哈密爾頓圖。半哈密爾頓圖8/12/202414第四部分：圖論（授課教師：向勝軍）哈密爾頓圖的必要條件注意：任何一個哈密爾頓圖都可以看成是一個基本回路再加上連接該回路上頂點對的其他若干條邊。從一個基本回路上刪除k個頂點，最多形成k個連通分支。向一個圖中已有的頂點之間加邊不會增加連通分支。因此：若G是哈密爾頓圖，則對VG的任意非空真子集V1，p(G-V1)≤|V1|。8/12/202415第四部分：圖論（授課教師：向勝軍）必要條件的應用必要條件一般只能判定一個圖不是哈密爾頓圖。如右圖(Petersen圖)滿足上述必要條件。但Petersen圖不是哈密爾頓圖。均不滿足必要條件，所以都不是哈密爾頓圖。8/12/202416第四部分：圖論（授課教師：向勝軍）半哈密爾頓圖的充分條件設G是n(n≥3)階無向簡單圖，若G中任意不相鄰的頂點對u,v均滿足：

d(u)+d(v)≥n-1

則G是半哈密爾頓圖。注意:

此定理條件顯然不是必要條件，如n≥6的n邊形，對于任意不相鄰的頂點u,v,d(u)+d(v)=4，4<n-1，而n邊形顯然有哈密爾頓通路。8/12/202417第四部分：圖論（授課教師：向勝軍）哈密爾頓圖的充分條件設G是n(n≥3)階無向簡單圖，若G中任意不相鄰的頂點對u,v均滿足：

d(u)+d(v)≥n

則G是哈密爾頓圖。n(n≥3)階完全圖是哈密爾頓圖。8/12/202418第四部分：圖論（授課教師：向勝軍）判定定理的盲區(qū)8/12/202419第四部分：圖論（授課教師：向勝軍）在平面上畫出一個圖G的圖形，若該圖形中任意兩邊均不在當中相交，則稱該圖形是G的一個平面嵌入，又稱為平面(Planar)。若圖G存在平面嵌入，則G稱為平面圖。

圖G是否平面圖，與其某一個圖形表示無關。

注意：無回路的圖一定是平面圖。若G的某個子圖是非平面圖，G也是。非連通圖可以對連通分支分別討論。改畫成平面圖§4平面圖8/12/202420第四部分：圖論（授課教師：向勝軍）一個平面圖的例子同構(gòu)變換lkihgfedcbajabcdjklfegihlbacdjfkegih8/12/202421第四部分：圖論（授課教師：向勝軍）典型的非平面圖Jordan定理：平面上一條封閉曲線J將平面分為“內(nèi)部”和“外部”兩部分，分別位于內(nèi)部和外部的兩個頂點之間的連線必然與J相交。

K5K3,3不管這第5個頂點加在何處，都出現(xiàn)Jordan條件8/12/202422第四部分：圖論（授課教師：向勝軍）[定義]面(face)

被平面圖中回路分割成互不重疊的連通塊，這些塊稱為面(face)或區(qū)域(Region)。(1)如果不存在回路，整個平面只有一個面。如圖，分為四個面。(2)有限面與無限面：面積有限的區(qū)域稱為有限面(或內(nèi)部面)，否則為無限面(或外部面)。上圖中，面4是無限面。8/12/202423第四部分：圖論（授課教師：向勝軍）(3)面的次數(shù)等于面邊界的邊數(shù)(注意：懸掛邊算2次)，記為deg(R).(4)平面圖中面的次數(shù)之和等于邊數(shù)m的兩倍，即其中，r為面數(shù)。7(無限區(qū)域)2115108/12/202424第四部分：圖論（授課教師：向勝軍）平面圖的一個必要條件歐拉公式：若G是連通平面圖，則有n-m+r=2,

其中，n為G中頂點數(shù)，m為邊數(shù)，r為面數(shù)(包括無限面)。證明：對m進行歸納。初始化：當m=0,G是平凡圖：n=1,r=1。當m=1,必為下列兩中情況之一：G=K2,n=2,r=1。G是一個環(huán)，n=1,r=2。假設當m=k-1時結(jié)論成立。當m=k時:I.若G中含1次頂點v,令G'=G-v,顯然：n'=n-1,m'=m-1,r'=r，因此：n-m+r=(n'+1)-(m'+1)+r'=n'-m'-1+1+r'=n'-m'+r'=2.II.若G中無1次頂點，G中必含回路，設e是回路上任一邊，令G'=G-e,顯然：n'=n,m'=m-1,r'=r-1，因此：n-m+r=n'+(r'+1)-(m'+1)=n'-m'-1+r'+1=n'-m'+r'=2.8/12/202425第四部分：圖論（授課教師：向勝軍）簡單連通平面圖的必要條件

(實際上，當平面圖畫不出時，歐拉公式很難直接使用)歐拉公式的推論：若G是簡單連通平面圖(n

3),則m

3n-6。證明：至少3個頂點的簡單圖G中，面的最小度數(shù)是3，所以面的總次數(shù)至少為3r，而根據(jù)定理，面的總次數(shù)等于2m，

3r

2m，即r2m/3.根據(jù)歐拉公式：

2=n-m+rn-m+2m/3,

63n-3m+2m,即：m

3n-6。K5不是平面圖：在K5中，n=5,m=10,3n-6=9。另一個推論：若G是簡單連通平面圖(n

3),且G是二部圖，則m

2n-4。證明：與上面類似，只需注意，簡單連通二部圖(n

3)中，最小面次數(shù)是4。K3,3不是平面圖：在K3,3中，n=6,m=9,2n-4=8。

(注意：K3,3滿足m

3n-6)。

8/12/202426第四部分：圖論（授課教師：向勝軍）極大平面圖定義：設G是簡單平面圖，若在G中任意不相鄰頂點之間加一條邊，所得圖是非平面圖，則G稱為極大平面圖。極大平面圖的連通性極大平面圖是連通圖。(顯然兩個連通分支之間加一條邊不影響原來圖的可平面性)n3的極大平面圖不含割點和割邊。割邊割點8/12/202427第四部分：圖論（授課教師：向勝軍）極大平面圖的特征設G是n

3的簡單連通平面圖，則G是極大平面圖當且僅當

G的每個面均為3次。

假設G是極大平面圖，顯然G中不可能有小于3次的面。假設存在一個面Ri,滿足d(Ri)>3,設該面的邊界上頂點依次是v1,v2,v3,v4,…,vt(t

4)，必有v1v3

EG,v2v4

EG，且v1v3,v2v4只能在Ri以外(否則在該面內(nèi)部加一條邊，仍舊是平面圖，與G的極大性矛盾)，而此時這兩邊必相交，與G是平面圖矛盾。

不存在次數(shù)大于3的面。

假設G中每個面均是3次，則2m=3r(這里m是G中邊數(shù)，r是面數(shù))，

G連通，可以將上述等式代入歐拉公式n-m+r=2(n是G中頂點數(shù))，得：m=3n-6。假設G不是極大平面圖，一定可以找到一對不相鄰的頂點u,v,使得G'=G+uv仍是簡單平面圖，但在G'中：m'>3n'-6，這與歐拉公式的推論矛盾，

G是極大平面圖。

v1v3v2vtv4Ri面的邊界內(nèi)部沒有邊8/12/202428第四部分：圖論（授課教師：向勝軍）同胚圖基本動作：二次頂點的插入和消去如果圖G1和G2經(jīng)過反復的插入和消去二次頂點，可達到同構(gòu)，則G1和G2是同胚圖(homeomorphicGraph)