組合與圖論1.1-1.2

1、授課教師：程績E-mail:Tel25680792022年6月26日參考文獻(xiàn)1. JA邦迪等.圖論及其應(yīng)用.吳望民等譯.北京:科學(xué)出版社.19842. F哈拉里.圖論.李慰萱譯.上海:上?？茖W(xué)技術(shù)出版社.19803. 盧開澄,盧華明.圖論及其應(yīng)用.第二版.北京:清華大學(xué)出版社.19954.Bela Bollobas. Moden Graph Theory.影印版.北京:科學(xué)出版社.20015. 徐俊明.圖論及其應(yīng)用.安徽：中國科學(xué)技術(shù)大學(xué)出版社.20046. 張先迪 李正良.圖論及其應(yīng)用.北京:高等教育出版社.20052022年6月26日說明本課程做為組合數(shù)學(xué)的后續(xù)

2、課程，繼續(xù)沿用教材組合數(shù)學(xué)與圖論。 從主要內(nèi)容上看，本課程主要分為兩部分：一是圖論初步；二是競賽數(shù)學(xué)中的圖論問題。2022年6月26日第一章圖的基本概念2022年6月26日1.1哥尼斯堡七橋問題一、圖論學(xué)科概況大家所熟知的一些問題，例如四色猜想，一筆畫問題，推銷員問題，郵路問題，哈米爾頓問題等都是一些經(jīng)典的圖論問題。圖論是一個新的數(shù)學(xué)分支，起源于18世紀(jì)，是一門很有應(yīng)用價值的學(xué)科。它在自然科學(xué)和社會科學(xué)等各領(lǐng)域有很多應(yīng)用。近年來隨著計算機科學(xué)蓬勃發(fā)展，圖論的發(fā)展也極其迅速，應(yīng)用范圍不斷拓廣，已滲透到語言學(xué)、心理學(xué)、邏輯學(xué)、物理學(xué)、2022年6月26日一、圖論學(xué)科概況化學(xué)、電訊工程、計算機科學(xué)以

3、及數(shù)學(xué)的其它分支中。特別在計算機科學(xué)的形式語言、數(shù)據(jù)結(jié)構(gòu)、分布式系統(tǒng)、操作系統(tǒng)等方面均扮演著重要的角色。歷史上，圖論曾經(jīng)被很多數(shù)學(xué)家各自獨立地建立過，因為圖論本身就是應(yīng)用數(shù)學(xué)的一部分，所以這種情況并不是偶然的巧合。事實上，提到這個主題的文字記載最早是出現(xiàn)在歐拉的著作中。2022年6月26日四色猜想（4CC）的表述 問題：問題： 在一個平面上的任何地圖，是否可以最多用四種顏色就能使相鄰的國家著不同的顏色。這里假設(shè)地圖上的國家都是單連通的區(qū)域。2022年6月26日四色猜想的背景背景：背景： 這個猜想的起源有點模糊。有些報告說Mbius（默比烏斯）在1840年就熟悉這個問題，但是，可以肯定的僅僅是該

4、問題約于1850年由Guthrie轉(zhuǎn)告給De Morgan。該猜想提出之后，許多人都試圖解決這個猜想，但都未成功。1879年，Kempe（肯普）給出了這個猜想的許多錯誤“證明”中的第一個“證明”。1890年，Heawood（希伍德）發(fā)現(xiàn)了它的一個錯誤，并指出若將“四”換成“五”猜想成立。2022年6月26日四色猜想的解決解決：解決： 這個猜想在數(shù)學(xué)上嚴(yán)格證明，經(jīng)歷了一個多世紀(jì)都未能成功。直到1976年才被K.Appel（阿佩爾）, W.Hakan（黑肯）, J.Koch（科赫）等三人借助于電子計算機所證明，證明了該猜想成立。他們的證明需要計算機計算1200小時，100億個分離的邏輯判定。202

5、2年6月26日推銷員（TSP）問題問題：問題： 一個售貨員從他所在的城鎮(zhèn)出發(fā)，想去若干城鎮(zhèn)售貨，要求每個城鎮(zhèn)至少經(jīng)過一次，然后返回原地，問怎樣安排他的路線才會使通過的總路程最短？ 在數(shù)學(xué)建模中，有一個與抗洪巡視相關(guān)的問題，其中用到了TSP模型。2022年6月26日中國郵遞員問題問題：問題： 郵遞員的工作是：在郵局里選出郵件，遞送郵件，然后再返回郵局。自然，他必須走過他投遞范圍內(nèi)的每一條街道至少一次。在這個前提下，希望選擇一條盡可能短的路線。 這個問題是中國數(shù)學(xué)家管梅谷（1962）年研究的。 在數(shù)學(xué)建模中有一個鏟雪車的行駛問題用到了這個模型。2022年6月26日哈米爾頓圖 1859年，數(shù)學(xué)家威廉

6、哈米爾頓(Hamilton)爵士發(fā)明了一種周游世界的游戲：在一個12面體上的每個角點標(biāo)以有名的城市的名字，要求游戲者找一條沿著各邊通過每個頂點正好一次，最后回到出發(fā)地的路線。這個游戲在歐洲曾風(fēng)靡一時，哈米爾頓以25個金幣的高價把該項專利賣給了一個玩具商。然而，這是一筆滑頭的生意，因為這個游戲在經(jīng)濟上并不成功。 用圖論的語言來說，游戲的目的是在十二面體的圖中找一個生成圈。2022年6月26日2022年6月26日思考 推銷員問題、郵路問題和哈米爾頓所描述的是不是一類問題。 這是三個不同的問題。從圖論角度說，推銷員問題和哈米爾頓問題有密切的聯(lián)系，它們尋找的主要是基于哈米爾爾頓性質(zhì)的回路，而中國郵遞員

7、問題所尋找的主要是Euler圈。2022年6月26日二、哥尼斯堡七橋問題歐拉（Euler,17071782，瑞士）在1736年解決了一個當(dāng)時還沒有解決的著名問題，稱為哥尼斯堡七橋問題，從外表上看這是一個頗為無聊的問題，然而正是這個問題的解決，使歐拉成為了圖論和拓?fù)鋵W(xué)兩大學(xué)科的創(chuàng)始人。2022年6月26日哥尼斯堡七橋問題18世紀(jì)，東普魯士（現(xiàn)俄羅斯列寧格勒），哥尼斯堡（Knisberg），普雷格爾河畔（Pregel）。問題：問題：從河的南北兩岸或者兩個小島中任何一地出發(fā)，能否找到一條路線，做到每座橋恰好通過一次且最后返回出發(fā)地？2022年6月26日歐拉怎么做？問題：問題：能否找到一條路線，從圖中

8、任一點出發(fā)，經(jīng)過每條邊一次且僅一次，最后返回出發(fā)點？結(jié)論結(jié)論：所求線路不存在2022年6月26日問題的解決歐拉在1736年發(fā)表了哥尼斯堡七橋問題，給出了上述問題的否定回答，這成為圖論史上的第一篇論文。歐拉在此基礎(chǔ)上對此類問題進(jìn)行推廣，找到對于一般圖存在這樣的一條路線的充要條件。簡單地說，這就是一筆畫問題的一種表達(dá)方式。類似的，在習(xí)題中的“人、羊、狼、菜過河”問題，“8L、5L、3L容器的均分”問題、“10個人中或者必有3個人互相認(rèn)識，或者有4個人互相不認(rèn)識”等都是非常經(jīng)典的圖論問題。2022年6月26日1.2基本概念歐拉將哥尼斯堡七橋問題歸結(jié)為一些點與連接這些點的線之間的聯(lián)系，從而它可以用一個

9、由若干個頂點和若干條邊所組成的圖形來表示，所以我們把一個頂點集合與一個邊的集合放在一起，稱之為“圖”。2022年6月26日圖論中圖的特點圖論中所說的圖是描述事物之間關(guān)系的一種手段。現(xiàn)實世界中，許多事物之間的關(guān)系可抽象成點及它們之間的連線，集合論中二元關(guān)系的關(guān)系圖就是圖論中“圖”的很好的例子。在集合論中二元關(guān)系的關(guān)系圖中，我們只關(guān)心點與點之間是否有邊，而不關(guān)心點及邊的位置，以及邊的曲直、長短，這就是圖論中的圖與一般幾何圖形的區(qū)別。2022年6月26日一、圖的定義定義定義1.2.1一個圖G定義為一個偶對:（V,E），且記作G=(V,E)，其中，V是一個集合，V中元素稱為頂點或端點；E表示邊的集合。

10、通常約定：用G(graph)表示圖，用v表示頂點(vertex)，e表示邊(edge)。2022年6月26日例1.2.1(P107) 北京、上海、杭州、南京、廣州、武漢、鄭州、重慶、西安等十個城市之間的航線構(gòu)成一個圖。其中：V=北京、上海、杭州、南京、廣州、武漢、鄭州、重慶、西安為頂點的集合。E=(北京，上海)，(南京，武漢)，(西安，鄭州)為邊的集合。2022年6月26日例1.2.2(P108)(教材標(biāo)圖有誤),4321vvvvV ,654321eeeeeeE 和書上的說法略有不同，現(xiàn)在圖論中比較通行的邊的表示方法是這樣的：設(shè)邊e的兩個端點是u,v，則記e=u,v，表明，u和v之間是無序的。

11、,326412211vvevvevve2022年6月26日圖的兩大特點1.描述一個圖的幾何圖形不是唯一的描述一個圖的幾何圖形不是唯一的，幾何圖形僅描繪出該圖的頂點與邊之間保持的相互關(guān)聯(lián)關(guān)系。至于各頂點的相關(guān)位置以及各邊的長、短、曲、直等都是無關(guān)緊要的。2.圖的本質(zhì)內(nèi)容是各頂點與邊之間的關(guān)聯(lián)關(guān)系，至于頂點和邊是否用平面上的幾何點和線段來表示，則不是必要的。換句話說，圖的概念可以高度的抽象化圖的概念可以高度的抽象化，它完全可以由一個抽象集合G=(V,E)來表示。2022年6月26日一些相關(guān)概念1V對于圖G=(V,E)中的頂點數(shù)，用 表示，一般也用n,表示；邊的數(shù)目用表示，一般也用m,表示，通常用（

12、n,m）或者(,)表示一個圖的大小（規(guī)模）。E若n,m均有限，稱G為有限圖；E=，n=1，稱G為平凡圖（只有一個孤立頂點的圖）；n=或m= ，稱G為無限圖；若G中任兩點之間有邊相連，則稱G為完全圖，記為Kn。2022年6月26日一些相關(guān)概念2在G中連接同一對頂點的邊數(shù)大于，則稱這樣的邊為多重邊，有時也稱其為平行邊，而連接同一對頂點的邊數(shù)稱為連接該對頂點的邊的重數(shù)。又若圖G=(V,E)中形如v,v的邊，即一條邊中的兩個端點重合為一點時，稱這樣的邊為環(huán)。稱沒有重邊，沒有環(huán)的圖為簡單圖。如無特別聲明，今后所討論的圖指簡單圖。2022年6月26日一個有趣的圖Graph Buster (小鬼圖)n=13

13、m=212022年6月26日關(guān)于有向圖有向圖的概念教材上有所提及，這里不做為教學(xué)內(nèi)容。 簡單地說，有向邊就是它的兩個端點有先后順序，有所指向的邊。有向邊構(gòu)成的圖稱為有向圖(圖1.2.2)，無向邊構(gòu)成的圖稱為無向圖。若一個圖既有有向邊，又有無向邊，則稱其為混合圖。如大城市的交通系統(tǒng)就是一個混合圖結(jié)構(gòu)。2022年6月26日鄰接與關(guān)聯(lián)Vvu,定義定義1.2.2在圖G=(V,E)中，若v是e的一個端點，則稱邊e和頂點v是相關(guān)聯(lián)的；若，且有，則稱頂點u和v鄰接；若兩條邊有共同的頂點，則稱這兩條邊是鄰接的。Evue,2022年6月26日子圖與導(dǎo)出子圖),(111EVG EEVV11且1G定義定義1.2.3

14、設(shè)G=(V,E)和，若滿足，則稱圖是圖G的一個子圖；若，則稱是G的一個真子圖。特別地，當(dāng)時，稱是G的一個生成子圖（支撐子圖）。EEVV11或1GVV 12022年6月26日子圖與導(dǎo)出子圖11VVV且1V1VG設(shè)，以為頂點集，兩個端點都在中的邊為邊集的G的子圖，稱為G的由頂點集導(dǎo)出的子圖，記為。1V1V設(shè)，以為邊集，的端點集為頂點集的圖G的子圖，稱為G的由邊集導(dǎo)出的子圖，記為。11EEE且1E1EG1E1E舉例說明2022年6月26日圖的運算),(),(222111EVGEVG),(212121EEVVGG圖的并121212,G GGGGG特別地 當(dāng)?shù)狞c不交時 則有121212,G GGGGG特

15、別地,當(dāng)?shù)倪叢唤粫r 則有2022年6月26日圖的運算121212(,)GGVV EE圖的交),(),(222111EVGEVG定義交圖時，兩圖至少要有一個公共頂點。2022年6月26日圖的運算),(),(222111EVGEVG。GGGGGG中的邊組成的圖中去掉是由的差212121,21GG 21GG2022年6月26日圖的運算),(),(222111EVGEVG的交所得的圖的并中去掉是的對稱差圖21212121,GGGGGGGG)()()()(1221212121GGGGGGGGGG2022年6月26日圖的運算21212121,GG，GGGGGG記為到的圖稱為聯(lián)圖的每個頂點連接起來得的每個頂

16、點和把中的并圖和在不相交的3342516532541,KKKKKKKKKKKKK2022年6月26日圖的運算.)()(),(),(),(),(212111222211212121222111GGG，GGGvu，adjvuvuadjvuvuvvvuuuVVVEVGEVG記為的積圖和稱為連接起來所得到的圖和就把時和或和當(dāng)和點中的任意兩個對點集設(shè)u1v1u2v2w2(u1,u2)(u1,v2)(u1,w2)(v1,u2)(v1,v2)(v1,w2)2022年6月26日二、握手定理及推論定義定義1.2.4設(shè)G=(V,E)是一個無向圖。對于V中每一個頂點v，稱以v作為邊的端點的次數(shù)之和為度數(shù)，或簡稱為v

17、的度。一般記為。所有頂點度中的最小值記為，最大值記為。)()(vdvdG或思考思考：環(huán)上的頂點的度怎么計算？答：答：設(shè)環(huán)e以v為頂點，則d(v)=2。（舉例說明）2022年6月26日握手定理VvEvd2)(證明證明：因每條邊都與兩個頂點相關(guān)聯(lián)，每出現(xiàn)一條邊就增加2，所以總次數(shù)。定理定理1.2.1對于任意有限圖G，恒有其中V為頂點集合，E為邊集合。VvEvd2)(2022年6月26日握手定理的推論推論推論：任圖G=(V,E)，度數(shù)為奇數(shù)的頂點的個數(shù)為偶數(shù)。EvdvdvdVvVvVv2)()()(211)(Vvvd2)(Vvvd證明證明：設(shè)V1和V2分別表示圖中奇次頂點和偶次頂點的集合。則為偶數(shù)。又是偶數(shù)，因此也是偶數(shù)，從而奇次頂點的總數(shù)為偶數(shù)。1V2022年6月26日握手定理的應(yīng)用嘗試自己建立圖論模型解釋下述三個命題：(1) 在一群人中，和奇數(shù)個人握手的人的個數(shù)一定是偶數(shù)；(2) 設(shè)A是正整