7.1圖的概念/IntroductionofGraph7.2圖的術(shù)語(yǔ)/GraphTerminology7.3圖的表示與同構(gòu)/RepresentingGraphandGraphIsomorphism7.4連通性/Connectivity7.5歐拉道路與哈密爾頓道路/EulerandHamiltonPaths7.6最短道路問(wèn)題/ShortestPathProblem7.7平面圖/PlanarGraphs7.8圖的著色/GraphColoring第一頁(yè)，共三十二頁(yè)。5/15/20231DerenChen,ZhejiangUniv.7.5EulerandHamiltonPathKonigsberg(哥尼斯堡)七橋問(wèn)題問(wèn)題：能否從河岸或小島出發(fā)，通過(guò)每一座橋，而且僅僅通過(guò)一次回到原地。第二頁(yè)，共三十二頁(yè)。5/15/20232DerenChen,ZhejiangUniv.

Euler(歐拉)1736年對(duì)這個(gè)問(wèn)題，給出了否定的回答。將河岸和小島作為圖的頂點(diǎn)，七座橋?yàn)檫叄瑯?gòu)成一個(gè)無(wú)向重圖，問(wèn)題化為圖論中簡(jiǎn)單道路的問(wèn)題：[定義]歐拉道路（回路）：Ｇ＝（Ｖ，Ｅ），稱包含Ｅ中所有邊的簡(jiǎn)單道路為歐拉道路/EulerPath/E道路。包含Ｅ中所有邊的簡(jiǎn)單回路為歐拉回路/EulerCircuit/E回路。第三頁(yè)，共三十二頁(yè)。5/15/20233DerenChen,ZhejiangUniv.[定理1]（歐拉定理）：沒(méi)有次為０的孤立頂點(diǎn)的無(wú)向圖存在歐拉道路的充要條件是：(1)圖是連通的；(2)圖中奇次頂點(diǎn)個(gè)數(shù)是０個(gè)或2個(gè)。第四頁(yè)，共三十二頁(yè)。5/15/20234DerenChen,ZhejiangUniv.證明：必要性：若存在歐拉道路，且沒(méi)有０次頂點(diǎn)，則每個(gè)頂點(diǎn)都有邊關(guān)聯(lián)，而邊又全在歐拉道路上，故所有頂點(diǎn)都連通。除了起點(diǎn)，終點(diǎn)外，歐拉道路每經(jīng)過(guò)一個(gè)頂點(diǎn)，使頂點(diǎn)的次增加２，故只有起點(diǎn)和終點(diǎn)才可能成為奇次頂點(diǎn)，而一個(gè)奇次頂點(diǎn)是不可能的，當(dāng)無(wú)奇次頂點(diǎn)時(shí)，是歐拉回路。充分性：若(1），(2)成立,構(gòu)造歐拉道路.第五頁(yè)，共三十二頁(yè)。5/15/20235DerenChen,ZhejiangUniv.

若圖Ｇ存在奇次頂點(diǎn)，任取一個(gè)作為起點(diǎn)，若不存在，則任取一個(gè)頂點(diǎn)作為起點(diǎn)。若此圖有ｎ條邊，總次為２ｎ。每進(jìn)入或離開(kāi)一個(gè)頂點(diǎn)，讓此頂點(diǎn)的次減１，由于除了兩個(gè)（或沒(méi)有）奇次頂點(diǎn)外，其余頂點(diǎn)次為偶數(shù)，只要進(jìn)得去，一定出得來(lái)，直至進(jìn)入另一個(gè)奇次頂點(diǎn)（或起點(diǎn)）作為終點(diǎn)。這樣構(gòu)造的是簡(jiǎn)單道路，如果經(jīng)過(guò)所有的邊，即得到一條歐拉道路。

不然，記走過(guò)的簡(jiǎn)單道路為ｐ1，ｐ1上頂點(diǎn)集Ｖ1，邊集Ｅ1，Ｇ1＝（Ｖ1，Ｅ1）是Ｇ的子圖。第六頁(yè)，共三十二頁(yè)。5/15/20236DerenChen,ZhejiangUniv.

若Ｇ2＝（Ｖ2，Ｅ2）是Ｇ1的關(guān)于Ｇ的余圖，Ｅ2＝Ｅ－Ｅ1，但Ｖ1∩Ｖ2≠φ，否則Ｇ不連通，設(shè)Ｃ∈Ｖ1∩Ｖ2，從Ｃ出發(fā)，用上面方法作Ｇ2的簡(jiǎn)單回路ｐ2回到Ｃ,這能做到。因?yàn)樽骱茫?后，留下頂點(diǎn)的次都是偶次。若ｐ1∪ｐ2經(jīng)過(guò)所有邊，則歐拉道路是ｐ1走到Ｃ時(shí)，先把ｐ2走完，最后走完ｐ1的余下道路。若ｐ1∪ｐ2仍未經(jīng)過(guò)所有邊，將ｐ1∪ｐ2視為ｐ1重復(fù)上述過(guò)程，由于Ｅ邊有限，故存在歐拉道路。第七頁(yè)，共三十二頁(yè)。5/15/20237DerenChen,ZhejiangUniv.例1：（1）頂點(diǎn)的次：A(3),B(2),C(4),D(2),E(6),F(2),G(6),H(2),I(4),J(3）。其中奇次頂點(diǎn)A，J（2）從A出發(fā)，走一條道路（A,C,E,A,B,C,D,E,G,J）第八頁(yè)，共三十二頁(yè)。5/15/20238DerenChen,ZhejiangUniv.（3）Ｇ1＝（Ｖ1，Ｅ1）Ｖ1＝{A，B，C，D，E，G，J}Ｅ1＝{（A，B），（B，C），（A，C），（C，D），（C，E），（D，E），（E，G），（G，J）}Ｇ2＝（Ｖ2，Ｅ2）Ｅ2＝{（E，F(xiàn)），（F，G），（E，J），（G，H），（G，I），（I，J），（H，I）}Ｖ2＝{E，F(xiàn)，G，H，I，J}E∈（Ｖ1Ｖ2）第九頁(yè)，共三十二頁(yè)。5/15/20239DerenChen,ZhejiangUniv.（4）從E出發(fā)回到E的回路（E，F(xiàn)，G，I，J，E），加入到P1中

Ｐ1＝（A，C，E，F(xiàn)，G，I，J，E，A，B，C，D，G，J）（5）還有未經(jīng)過(guò)的邊，重復(fù)上述過(guò)程，從G出發(fā)，（G，H，I，G），再加入即得歐拉道路。第十頁(yè)，共三十二頁(yè)。5/15/202310DerenChen,ZhejiangUniv.說(shuō)明：哥尼斯堡七橋問(wèn)題，由于四個(gè)頂點(diǎn)都是齊次的，不可能有歐拉道路。應(yīng)用與推廣：（1）一筆畫(huà)問(wèn)題；

（2）如果齊次頂點(diǎn)個(gè)數(shù)為2K個(gè)，此問(wèn)題是K筆畫(huà)問(wèn)題。

第十一頁(yè)，共三十二頁(yè)。5/15/202311DerenChen,ZhejiangUniv.例８?jìng)€(gè)頂點(diǎn)均為3次，至少要４筆。第十二頁(yè)，共三十二頁(yè)。5/15/202312DerenChen,ZhejiangUniv.[推論]（歐拉定理）：沒(méi)有次為０的孤立頂點(diǎn)的無(wú)向圖存在歐拉回路的充要條件是：(1)圖是連通的；(2)圖中沒(méi)有奇次頂點(diǎn)。第十三頁(yè)，共三十二頁(yè)。5/15/202313DerenChen,ZhejiangUniv.定理2（有向圖的歐拉定理）：不含出/入次為０的孤立頂點(diǎn)的有向圖具有歐拉道路的充要條件是：(1）弱連通；(2)除了可能有２個(gè)頂點(diǎn)，一個(gè)入次比出次大１，一個(gè)出次比入次大１，其余頂點(diǎn)出次等于入次。推論不含出/入次為０的孤立頂點(diǎn)的有向圖具有歐拉回路的充要條件是：（1）弱連通；（2）所有頂點(diǎn)出次等于入次。第十四頁(yè)，共三十二頁(yè)。5/15/202314DerenChen,ZhejiangUniv.Hamilton(哈密頓)道路問(wèn)題：

１８５９年發(fā)明的一種游戲。在一個(gè)實(shí)心的正十二面體，20個(gè)頂點(diǎn)標(biāo)上世界著名大城市的名字，要求游戲者從某一城市出發(fā)，遍歷各城市一次，最后回到原地。這就是“繞行世界”問(wèn)題。即找一條經(jīng)過(guò)所有頂點(diǎn)（城市）的基本道路（回路）。第十五頁(yè)，共三十二頁(yè)。5/15/202315DerenChen,ZhejiangUniv.[定義]哈密頓道路/回路：Ｇ＝（Ｖ，Ｅ），G中經(jīng)過(guò)Ｖ中所有頂點(diǎn)的基本道路稱為哈密頓道路/HamiltonPath，簡(jiǎn)稱Ｈ道路。Ｇ＝（Ｖ，Ｅ），G中經(jīng)過(guò)Ｖ中所有頂點(diǎn)的基本回路稱為哈密頓回路/HamiltonCircuit，簡(jiǎn)稱Ｈ回路。第十六頁(yè)，共三十二頁(yè)。5/15/202316DerenChen,ZhejiangUniv.圖Ａ每個(gè)頂點(diǎn)都是奇次的，不存在歐拉道路，但有Ｈ道路。圖Ｂ存在歐拉道路，不存在Ｈ道路。第十七頁(yè)，共三十二頁(yè)。5/15/202317DerenChen,ZhejiangUniv.[定理3]：設(shè)Ｇ＝（Ｖ，Ｅ）是ｎ個(gè)頂點(diǎn)的簡(jiǎn)單圖，如果任何一對(duì)頂點(diǎn)的次之和≥ｎ－１，則Ｇ中一定有Ｈ道路（n>=2）。證明：1、Ｇ一定連通，否則Ｇ分為二個(gè)不連通的分圖Ｇ1，Ｇ2，其中Ｇ1有ｎ1個(gè)頂點(diǎn)，Ｇ2有ｎ2個(gè)頂點(diǎn)，Ｇ1中每個(gè)頂點(diǎn)次≤ｎ1－１，Ｇ2中每個(gè)頂點(diǎn)次≤ｎ2－１，從Ｇ1中取一個(gè)頂點(diǎn)，Ｇ2中取一個(gè)頂點(diǎn)，這一對(duì)頂點(diǎn)之和≤ｎ1－１＋ｎ2－１＝ｎ1＋ｎ2－２＝ｎ－２＜ｎ－１，與定理的假設(shè)矛盾。第十八頁(yè)，共三十二頁(yè)。5/15/202318DerenChen,ZhejiangUniv.2、用歸納法證明Ｇ中存在Ｈ道路：(1)任取一條邊（Ｖ1，Ｖ2），是含２個(gè)頂點(diǎn)的基本道路。(2)如果已有ｐ個(gè)頂點(diǎn)的基本道路（Ｖ1，Ｖ2，…，Ｖp），（ｐ≤ｎ－１）必能構(gòu)造ｐ＋１個(gè)頂點(diǎn)的基本道路。ａ）如果在Ｖ－｛Ｖ1，Ｖ2，…Ｖp｝中存在與Ｖ1或Ｖp相鄰的頂點(diǎn)，則基本道路自然可以擴(kuò)充一個(gè)頂點(diǎn)。ｂ）如果Ｖ1，Ｖp僅與｛Ｖ1，Ｖ2，…，Ｖp｝中頂點(diǎn)相鄰，則｛Ｖ1，Ｖ2，…，Ｖp｝必可適當(dāng)排列，形成回路。第十九頁(yè)，共三十二頁(yè)。5/15/202319DerenChen,ZhejiangUniv.

如果Ｖ1與Ｖp相鄰，顯然成了環(huán)。不然，由于Ｖ1，Ｖp僅與｛Ｖ1，Ｖ2，…，Ｖp｝中頂點(diǎn)相鄰，Ｖ1，Ｖp的次≤ｐ－１。不妨設(shè)Ｖ1的次為ｋ≤ｐ－１，分別記相鄰頂點(diǎn)為Ｖi1，Ｖi2，…，Ｖik，它們前面的頂點(diǎn)（指在基本道路｛Ｖ1，Ｖ2，…，Ｖp｝中的序）為，Ｖp必與中某頂點(diǎn)相鄰，否則Ｖp的次≤ｐ－１－ｋ，Ｖ1與Ｖp的次之和≤ｋ＋ｐ－１－ｋ＝ｐ－１＜ｎ－１，與任一對(duì)頂點(diǎn)次之和≥ｎ－１矛盾。不妨Ｖp與Ｖj-1相鄰，Ｖ1與Ｖj相鄰。將Ｖ1與Ｖj連起來(lái)，Ｖp與Ｖj-1連起來(lái)，并將Ｖj-1到Ｖj的邊去掉，就形成一個(gè)環(huán)，如下圖所示。第二十頁(yè)，共三十二頁(yè)。5/15/202320DerenChen,ZhejiangUniv.

又由Ｇ的連通性，總可在Ｖ－｛Ｖ1，Ｖ2，…，Ｖp｝中找到一個(gè)點(diǎn)Ｖx，與｛Ｖ1，Ｖ2，…，Ｖp｝中某一頂相鄰，不妨與Ｖk相鄰，Ｖk≠Ｖ1，Ｖk≠Ｖp，連上Ｖx與Ｖk的邊，去掉Ｖk-1到Ｖk的邊，可以從Ｖk-1為起點(diǎn)，一直走到Ｖk，再到Ｖx，這是一條ｐ＋１個(gè)頂點(diǎn)的基本道路。第二十一頁(yè)，共三十二頁(yè)。5/15/202321DerenChen,ZhejiangUniv.

如果ｐ＋１＜ｎ，仍繼續(xù)擴(kuò)充基本道路內(nèi)的頂點(diǎn)，直至達(dá)到ｎ。注意:此定理?xiàng)l件顯然不是必要條件，如ｎ≥６的ｎ邊形，二個(gè)頂點(diǎn)次之和＝４，４＜ｎ－１，而ｎ邊形顯然有Ｈ道路。[推論]：Ｇ＝（Ｖ，Ｅ）是ｎ≥３的簡(jiǎn)單圖，若任何一對(duì)頂點(diǎn)的次之和≥ｎ，則Ｇ必有哈密頓回路。第二十二頁(yè)，共三十二頁(yè)。5/15/202322DerenChen,ZhejiangUniv.

由于推論條件也必滿足定理3條件，存在Ｈ道路，可類似于定理一的方法找到一條回路。[定理4]：有向完全圖一定存在Ｈ道路。第二十三頁(yè)，共三十二頁(yè)。5/15/202323DerenChen,ZhejiangUniv.小結(jié)1、E圖：簡(jiǎn)單道路+所有邊2、H圖：基本道路+所有頂點(diǎn)第二十四頁(yè)，共三十二頁(yè)。5/15/202324DerenChen,ZhejiangUniv.進(jìn)一步的思考1、E圖/H圖的應(yīng)用2、E圖/H圖的判定第二十五頁(yè)，共三十二頁(yè)。5/15/202325DerenChen,ZhejiangUniv.

要判別一個(gè)圖不存在Ｈ道路，Ｈ回路，也不是很容易的，只能對(duì)無(wú)向圖給出一些必要條件：（1）Ｈ道路存在必要條件：１）連通２）至多只能有二個(gè)頂點(diǎn)的次＜２，其余頂點(diǎn)的次≥２。bcda第二十六頁(yè)，共三十二頁(yè)。5/15/202326DerenChen,ZhejiangUniv.（2）Ｈ回路存在必要條件：對(duì)Ｖ的任一非空真子集Ｓ，Ｇ－Ｓ的連通分圖個(gè)數(shù)≤|Ｓ|。第二十七頁(yè)，共三十二頁(yè)。5/15/202327DerenChen,ZhejiangUniv.解：取Ｓ＝｛A1，A2｝第二十八頁(yè)，共三十二頁(yè)。5/15/202328DerenChen,ZhejiangUniv.G－Ｓ存在3個(gè)