1離散數學DiscreteMathematics

汪榮貴教授合肥工業大學軟件學院專用課件2011.06Chapter5graphtheory

§1引論－2

圖論——計算機問題求解的描述工具實際問題數學模型求解算法（算法）編程實現用大量數據驗證抽象求解測試

圖論是離散數學的分支：圖(graph)：是一個離散集和某些兩元素子集的集合。數學形象是：紙上畫幾個頂點，把其中一些點用曲線段或直線連起來。圖顯示的是點與點之間的二元關系。5CHAPTER5Graphs

5.1IntroductiontoGraphs圖的概述5.2GraphTerminology圖的術語5.3RepresentingGraphsandGraphIsomorphism圖的表示和圖的同構

5.4Connectivity連通性5.5EulerandHamiltonPaths歐拉通路和哈密頓通路5.6PlanarGraphsandGraphColoring平面圖與著色5.7Trees樹§1引論為什么要學習圖論？可以采用圖論的成果和方法；最重要的是：可以培養我們思考問題和解決問題的能力。什么是圖論？－1圖論誕生和孕育于民間游戲。創生：1736年瑞士數學家歐拉——圖論之父；進展：1936年，匈牙利數學家寇尼希(Konig)發表名著《有限圖和無限圖理論》；1930年，波蘭數學家庫拉托父斯基(Kulatowsky)證明了平面圖可以畫在平面上；其后，圖論在現代數學、計算機科學、工程技術、優化管理等領域有大用而得以大力發展。歐拉生平簡介

萊昂哈德·歐拉(LeonhardEuler，1707.4.5~1783.9.18)歷史上最偉大的兩位數學家之一（另一位是高斯）。歐拉出生于瑞士，他是一位數學神童。作為數學教授，他先后任教于圣彼得堡(1727-1741)和柏林，爾后再返圣彼得堡(1766)。歐拉的離世也很特別：據說當時正是下午茶時間，正在逗孫兒玩的時候，被一塊蛋糕卡在喉頭窒息而死。歐拉是第一個使用“函數”一詞來描述包含各種參數的表達式的人，例如：y=F(x)(函數的定義由萊布尼茲在1694年給出)。歐拉是有史以來最多產的數學家，他的全集共計75卷。歐拉實際上支配了18世紀的數學，對于當時新發明的微積分，他推導出了很多結果。在他生命的最后7年中，歐拉的雙目完全失明，盡管如此，他還是以驚人的速度產出了生平一半的著作。小行星歐拉2002是為了紀念歐拉而命名的。萊昂哈德·歐拉Konisberg七橋問題(Euler問題)柯尼斯堡七橋問題是圖論中的著名問題。

這個問題是基于一個現實生活中的事例:位于當時東普魯士柯尼斯堡(今日俄羅斯加里寧格勒)有一條河，河中心有兩個小島。小島與河的兩岸有七條橋連接。如何才能在所有橋都恰巧只走一遍的前提下，回到原出發點？一、Konisberg七橋問題(Euler問題)－1如何才能在所有橋都恰巧只走一遍的前提下，回到原出發點?一、Konisberg七橋問題(Euler問題)－2

不少數學家都嘗試去解析這個事例。而這些解析，最后發展成為了數學中的圖論。

萊昂哈德·歐拉(LeonhardEuler)在1736年圓滿地解決了這一問題，證明這種方法并不存在。他在圣彼得堡科學院發表了圖論史上第一篇重要文獻。歐拉把實際的問題抽象簡化為平面上的點與線組合，每一座橋視為一條線，橋所連接的地區視為點。這樣若從某點出發后最后再回到這點，則這一點的線數必須是偶數。

一、Konisberg七橋問題(Euler問題)－3ACBD如何才能在所有橋都恰巧只走一遍的前提下，回到原出發點?求從圖中任一點出發，通過每條邊一次，最后回到起點。ACBD橋所連接的地區視為點每一座橋視為一條線一、Konisberg七橋問題(Euler問題)－4

如果通奇數座橋的地方不止兩個，那麼滿足要求的路線便不存在了。如果只有兩個地方通奇數座橋，則可從其中一地出發可找到經過所有橋的路線。若沒有一個地方通奇數座橋，則從任何一地出發，所求的路線都能實現。

142023/5/245.1IntroductiontoGraphsTypesofGraphs

圖的種類UndirectedGraphs無向圖Simplegraph簡單圖Multigraph多重圖Pseudograph偽圖152023/5/245.1IntroductiontoGraphs

【Definition】

Asimplegraph

G=(V,E)consistsofvertices,V,andedges,E,connectingdistinctelementsofV.簡單圖G=(V,E)是由非空頂點集V和邊集E所組成的，V的不同元素的無序對稱為邊。

-noloops沒環

-can‘thavemultipleedgesjoiningvertices兩個頂點間最多只有一條邊Amultigraph

allowsmultipleedgesfortwovertices.多重圖允許頂點對之間有多重邊A

pseudograph

isamultigraphwhichpermitsloops.偽圖也是多重圖，它可以存在環。Forexample,abcdabcdabcdabcd1620盜23關/5軋/1壯85.頭1In郊tr稀od脫uc慢ti筍on輝t燦o領Gr咱ap姓hsTh講e葬re盾la枝ti鋒on得s竹of提d逃if嗚fe碧re爺nt響u探nd升ir癢ec禾te描d搞gr拜ap惰hs各種己無向四圖之閱間的真關系Pseudographs偽圖Multigraphs多重圖SimpleGraphs簡單圖1720捉23釣/5雪/1開8Di湯re倍ct產ed患G拘ra礦ph陰:In精adi瓜re使ct夢ed捎g脅ra縫ph有向簡圖G摘=頌(V武,作E)th坐e柴ed糕ge信s票ar扁eor處de遵re婆d住pa姥ir健s（有握序對歇）of悉(篩no癥t春ne我ce遷ss柏ar厭il鏟y器di猶st兵in善ct篩)固ve先rt酬ic尚es往.有向屬圖(V蒙,E姐)是由鮮非空書頂點野集V、邊里集E所組牙成的孔，邊V中元斷素的吹有序狂對。吃允許罩有環(即相懶同元曲素的妻有序杰對)，但兄不允饑許在悠兩個樣頂點毫之間呀有同且向的惡多重削邊。In傾adi祝re分ct晨edmu殿lt離ig墳ra索ph有向圍多重菜圖G步=莖(V曬,昆E)th敞e感ed庸ge溉s悲ar擾e遠or貫de森re仆d書pa蜘ir藍s壺of塌(北no極t握ne滔ce托ss傲ar凱il批y款di功st病in覽ct靠)滔ve邊rt霞ic晃es妻,像an煤d押in扔a渡dd布it禮io但n諸th柄er窮e津ma組y驕be沉m云ul良ti透pl方e第ed靜ge恰s.有向繪多重紙圖G=輸(V墻,E茂)是由卸非空捏頂點革集V、邊違集E以及陽從E到{(u,稍v)盆|u珠,v∈V}的函鐵數f所組今成的嬌。若醬則骨邊e1和邊e2是多片重邊竹。5.霸1In兵tr怖od倒uc太ti陪on慢t尺o湊Gr些ap出hs1820菜23舉/5痰/1窄85.后1In壓tr詢od磁uc嗎ti棗on沸t質o探Gr土ap大hsTy抵pe灑s章of廢G占ra唇ph互s呆an兩d江Th遵ei釀r程Pr州op款er稍ti私es圖的懶類型煮及其桶性質類型Ty怒pe邊Ed古ge鼻s允許喜多重壩邊Mu臨lt踩ip般le擾E深dg舒es殃?允許括環Lo萌op康s?si代mp透le踐g劑ra襯ph簡單垮圖Un顫di捧re甚ct膛ed無向No否No否Mu險lt街ig誰ra挽ph多重乒圖Un斷di姐re策ct蘭ed無向Ye柿s是No否Ps帽eu曠do哄gr凝ap陣h偽圖Un鍛di撇re寬ct壁ed無向Ye盟s是Ye稍s是di非re寒ct店ed改g墳ra昂ph有向長圖di陶re首ct歲ed有向no否Ye裳s是di串r.Mu械lt弟ig紛ra腸ph有向秀多重堪圖Di若re墳ct礙ed有向Ye繳s是Ye劑s是1920貧23憂/5籌/1吼85.顛1In孩tr翠od儀uc辛ti援on擋t或o備Gr格ap蔑hsGr吐ap爽h仰Mo接de妹ls圖模士型見教州材p4浙4720CH何AP菊TE防R里5閱Gr恐ap啞hs5.端1孩I肚nt揉ro率du再ct荷io巨n蝴to甚G庭ra似ph涉s圖的混概述5.襲2幕G坡ra歷ph盡T班er盲mi肉no估lo轟gy圖的桃術語5.加3勸R郵ep渾re童se銀nt獅in帖g像Gr饞ap節hs囑a穗nd讀G鎮ra飲ph價I罪so意mo脈rp考hi姥sm圖的初表示究和圖情的同險構5.塊4冤C明on掙ne蠻ct獸iv剝it夸y連通宗性5.頁5脖E厲ul射er飽a訓nd拆H晌am催il伸to突n糧Pa栗th擦s歐拉計通路軍和哈按密頓泳通路5.扎6旬P趴la赤na倆r壟Gr航ap近hs燥a稱nd賠G濾ra濤ph筆C劉ol指or禽in洗g平面團圖與儉著色5.攀7畢T順re謙es樹2120莖23落/5柿/1妥85.快2Gr擠ap窯h憐Te改rm揚in勒ol熟og后yBa獅si化c埋Te賠rm煌in脾ol騙og釣y基本紹術語Un外di闖re稱ct煩ed享G呢ra鍬ph儉sG=(V,E)無向蚊圖Ve瘋rt頃ex貍,侍e許dg摘eTw陸o陸ve辛rt忠ic死es披,uan軌dvin折a反n些un么di斗re索ct民ed殊g伸ra油phGar撫e齒ca宵ll連edad貓ja醉ce姑nt(o圓rne誓ig籃hb飯or階s)inG,訴if敗{u,v}突is罵a掙n呆ed汽ge叛o圖fG.若{u,名v}是無敏向圖G的邊效，則蔥兩個簡頂點u和v稱為途在G里鄰霉接(或相構鄰)。An妻e駱dg勸e號e印co扎nn徒ec負ti艷nguan劈燕dvis英c矛al浪le良din腦ci加de不nt者w串it烤h別ve果rt獨ic觀es雖u認a啟nd辮v,or悶i千s悶sa流id懲t摘o莊co辰nn敏ec叛tuan批dv.邊e稱為沿關聯白點u和v，也珍可以撲說邊e連接u和vTh下e揀ve沙rt朝ic湊esuan驅dvar大e政ca且ll跳eden粘dp腰oi萌nt況sof過e暑dg斗e毯{u,v}.頂點u和v稱為童邊{u,v}的端吵點abcdfeg2220你23社/5半/1濤8Th耽ede建gr挽ee揚o錢f攏a傘ve經rt般ex（頂例點的悔度）in杠a威n牽un玻di井re農ct找ed想g證ra農ph刪i塘s科th傍e旅nu菊mb蜜er帖o晴f跟ed歇ge練s抽in坡ci禿de凳nt狡w笑it林h知it厘,止ex濫ce占pt沸t映ha企t歷a轟lo籍op遷a宴t梯a正ve叛rt重ex跟c愧on多tr眠ib行ut輸es咱t負wi然ce蛙t尖o劃th充e北de描gr柴ee剃o算f猜th堅at瞎v視er注te傘x在無純向圖炕里頂板點的爪度是陰與該慮頂點縱關聯牢的邊腦的數殺目，蓮例外關的情民形是馳，頂燦點上潔的環它為頂慰點的艇度做孫出雙炊倍貢趨獻。No杏ta勤ti恨on授:de客g(v)Ifde浩g(v)擁=別0,vis姥c搏al遍le列dis散ol灑at響ed.孤立芹的Ifde忽g(v)哭=道1,vis王c緩al喝le綠dpe泡nd絮an帥t.懸掛削的5.繩2Gr啟ap疑h芬Te車rm搭in坐ol蘋og喊y2320盼23潔/5姻/1赴85.很2Gr烤ap范h舅Te倦rm胸in其ol片og塞y【

Theorem1】

TheHandshakingTheorem握手理論

LetG=(V,E)beanundirectedgraphGwitheedges.Then設G=(V,E)是e條邊的無向圖，則Pr巨oo悅f:Ea億ch受e轟dg醬e岡re附pr蟲es灶en原ts左c如on后tr繞ib您ut蛙es誦t趴wi眠ce冤t縫o批th蠢e帖de誦gr屠ee憶c哀ou我nt笨o虛f蝦al笑l皺ve布rt歌ic嗎es鐮.每條凡邊都泰為頂拾點的撤度之判和貢揉獻2No雀te罵:Th滅is觸a送pp詠li尼es速e深ve饞n篇if決m惹ul連ti暑pl駱e負ed訴ge沾s石an誓d呀lo癢op怠s反ar彼e籍pr螺es鴨en護t.注意咳即使掠出現魚多重皺邊和暑環，爺這個躲式子品也仍井然成耐立2420質23界/5繁/1絕8Ap昨pl救ic隊at護io谷n:Th基e噸su粒m,鼠o就ve結r毛th縣e焰se才t案of葛p擁eo謎pl道e么at都a錦p霸ar司ty沈,告of險t剛he腰n宜um陵be貼r筋of院p寄eo犁pl賭e奪a片pe畝rs毫on短h杠as賓s克ha撒ke溪n山ha蕩nd細s綢wi屈th旨,纏is導e羨ve前n.5.高2Gr晴ap奶h薪Te死rm橫in渣ol駱og級yQu露se爽ti駛on:If冠a曠g顫ra真ph緒h名as帽5礎v洋er舅ti陪ce斯s,居c搭an舒e牙ac暢h繭ve序rt補ex播h丹av辜e甚de券gr侍ee叮3怖?全4?Th憑e睬su扔m幸is盆3覽?5豬=拔1翠5演wh爭ic旁h焰is后a稈n浪od窗d術nu際mb選er鞠.No嘗t映po攪ss殺ib慌le路.Th堂e謠su大m禿is拖2釣0減=緞2躁|E|提an商d儲20獄/2是=盾1趁0.Ma碑y桂be俯p執os脊si啞bl恰e.2520慣23裹/5濾/1乏85.嫁2Gr果ap障h抱Te碌rm院in獨ol販og洽y【Th萄eo縣re皆m廣2】An稠u改nd某ir仁ec偏te貞d數gr堪ap么h截ha架s塞an飼e妄ve背n種nu許mb壤er驚o宴fve塘rt便ic漁es偽o妖f伴od天d兄de殼gr我ee乒.無向騰圖有悉偶數捉個奇新數度忠頂點Pr均oo姑f:Letbethesetofverticesofevendegreeandthesetofverticesofodddegree,respectively.設v1和v2分別是偶數度頂點和奇數度頂點的集合，于是Qu盟se夾ti皂on:Isit摘p療os可si陡bl塘e置to孕h度av捐e沈a穿gr敘ap填h工wi揉th足3脈v罵er幻玉ti香ce繪s坡ea淘ch某o療f除wh遷ic箱h遠ha壘s崇de粗gr尿ee晝3慣?2620爆23向/5丟/1就85.互2Gr擁ap映h必Te冒rm起in挪ol杰og晌yDi牢re驢ct拳ed突G和ra暮ph揮sG=(V,E)Le東t語(u,喘v)be猴a促n及ed笑ge羊i嬌nG.勇Th侍enuis炸a差nin澡it中ia理l摔ve滅rt蛛ex起點an喊d幅isad壺ja裕ce狀nt歌t鑄ovan繳dvis呼ate蔬rm澆in拾al狹v擊er伶te蕩x終點an肚d赤isad緞ja郵ce切nt這f終ro化mu.Th懶ein侍d歉eg追re籮e入度of宰a鳳v彈er沸te趁xv,槳de漆no土te宵d袍de藍g-格(v)倆is凳t挖he幟n統um劣be括r探of歇e代dg貸es斜w勿hi犯ch淋t嫁er非mi瓜na旺te瞇a叫tv.頂點v的入方度是裹以v作為鐮終點幕的邊疊數。Si毫mi叔la貞rl逼y,窯t堪heou倍t猶de削gr劍ee出度ofv,而de逝no墊te等dde躬g+鍛(v),洲i松s滔th圈e承nu床mb恩er躍o斧f凝ed步ge逆s槍wh磨ic姜h艙in率it斬ia童te望a同tv.頂點v的出哲度是女以v作為征起點服的邊社數un紋de這rl歌yi隆ng勁u澡nd遷ir劍ec濤te呼d活gr犯ap泉habcdf2720讀23麗/5糖/1詳8【Th芝eo撞re差m詠3】Le萌tG免=扭(V冊,丹E)be姜a帶g抖ra如ph汪w趣it球h澇di戲re拜ct療e教dg距es謀.Th奏en在帶舅有向殿邊的縣圖里名，所恢有頂棵點的勿入度幫之和醫等于績出度脅之和龜。這兩燃個和擔都等赤于圖蠟的邊姻數。2820睛23定/5謎/1扛85.究2Gr勺ap篩h澆Te討rm刃in置ol習og珍ySo籠me堅S秧pe普ci霜al急S尸im細pl聽e永Gr機ap破hs一些剪特殊乞的簡寄單圖(1贈)Co金mp泉le孤te江G誰ra濁ph仿s完全賞圖-Kn:th蠻e賴si迎mp宵le射g從ra勺ph擾w逐it雙h-nve跨rt協ic博es-垮ex叮ac懸tl個y報on伯e歡ed朗ge緊b報et振we冒en所e戶ve慌ry駐p手ai督r莫of升d差is竭ti需nc須t鐘ve黎rt杏ic訊es少.Th大e泥gr蠢ap盜hsKnfo注rn=1朋,2糾,3妹,4襖,5率.n個頂將點的泛完全癢圖是椅在每扭對不記同頂庫點之嗚間都差恰有擱一條香邊的現簡單凡圖。K1K2K3K4K5Qu廳se匆ti斥on:Th準e庸nu濃mb越er啄o性f甚ed姜ge教s告inKn?2920宋23執/5盜/1蛇85.代2Gr豪ap荷h村Te顫rm蔬in什ol疤og敬y(2扁)洗Cy價cl顏es圈圖Cn(n>2讓)Cnis扶a語nnve狠rt潛ex白g吃ra乳ph護w荒hi伙ch宰i猛s記a撤cy稿cl選e.C3C4C5C63020頌23樹/5睡/1奏85.慘2Gr晚ap理h晝Te砍rm眠in竿ol將og摧y(3仁)縫Wh汪ee帝ls輪圖Wn(n>2敵)Ad弓d宋on洋e釘ad腸di柏ti維on煎al壯v項er剛te棵x頃to撲t罷he凝c秤yc覆leCnan壇d系ad耀d咳an鼠e沾dg遠e應fr可om懸e久ac安h爸ve碼rt無ex模t滔o夢th西e霉ne冷w切ve爬rt蘇ex壩t棄o跌pr忌od且uc獵eWn.當給箏圈圖尺添加靈另一鳥個頂偽點，橫而且笨把這峰個頂瘡點與距圈圖影里n個頂貨點逐診個連裂接時晝，就鈴得出蘭輪圖亦。W3W4W5W63120夏23深/5刺/1怨85.市2Gr鈴ap突h際Te搭rm看in手ol含og言y(4候)n-溝Cu戚be慎sQn(n>0緒)崗n立方致體Qnis形t界he籮g凱ra勁ph乳w唉it末h納2nve塑rt穩ic爸es疲r紡ep甘re郊se黑nt奔in境g逝bi芽t抗st圈ri詠ng冊s室of天l沒en旁gt花hn.上An既e乓dg緊e推ex樂is能ts跳b議et悶we撫en戀t克wo給v貝er嚷ti誤ce膨s紀th箏at股d限if僵fe蝦r臘by估o豪ne德b貿itpo損si滔ti刻on暈.n立方師體圖虧是用索頂點流表示爹個長杠度為n的位起串的蹦圖。漠兩個映頂點危相鄰瓜，當離且僅辟當他習們所率表示裂的位鍛串恰開恰相唱差一葬位。Q1Q2Q301000111100000011011000100111111103220帆23化/5掘/1宴85.歪2Gr勵ap蒜h辜Te汗rm匆in尼ol發og蟲y(5懼)糊Bi盼pa鳳rt猶it皂e蚊Gr胖ap簽hs偶圖潔（二危分圖王）A祝si扎mp佳le捧g捏ra貢phGisbi柄pa媽rt朽it鳥eifVca抄n智be序p忙ar潑ti似ti爺on扯ed或i晨nt蠶o夾tw羊o增di沿sj粒oi善nt棚s箭ub舟se辜tsV1an欣dV2su成ch嘗t換ha粥t失ev揮er獲y禾ed忘ge慕c石on街ne漸ct窗s桑a明ve丈rt綠ex明i隊nV1an掌d薄a貸ve促rt枝ex滲i芹nV2.若把靈簡單登圖G的頂熟點集姿分成濃兩個濱不相英交的臉非空沃集合V1和V2，使賓得圖幻玉里的千每一睛條邊探都連蕉接著V1里的芬一個屠頂點情與V2里的歷一個廉頂點辛，則G稱為姐偶圖No數te叉:Th奸er穿e絕ar王e熄no乘e么dg鄉豐es喬w服hi詠ch骨c針on壺ne珠ct茫v拋er氣ti呀ce備s老inV1or浸i殿nV2.Fo預r屢ex坦am優pl取e,3320舉23惠/5蜘/1豬85.龜2Gr阻ap眠h目Te多rm現in曲ol舅og價y〖Ex狼am咱pl敘e穴1〗IsC3bi殲pa宴rt草it張e?v1v2v3No最.3420揉23撿/5閱/1王85.過2Gr慮ap虛h著Te勤rm毯in剃ol握og道y〖Ex風am側pl臂e貫2〗IsC6bi陷pa侵rt變it克e?Ye乎s.Be很ca針us太e腳we占c媽an額d帽is攝pl惱ayC6li鉛ke占t剩hi縱s:v5v1v2v3v4v6v1v6v2v5v3v43520現23砌/5籌/1銳85.薦2Gr松ap栗h懸Te抖rm等in塌ol散og競yTh凳eco修mp旗le顯te絡b尤ip罵ar哨ti敵te裹g題ra篇phis碌t寒he管s瞎im邪pl劃e邀gr微ap獲h畏th匪at環h槳as曲i酬ts湊v面er衰te工x介se弄t鋸pa坊rt爛it神io犬ne仁d委in陣to淚t康wo朵s遼ub現se毫tsV1an留dV2wi騾th刪m慨a暈ndnve秘rt僻ic僻es宰,凳re鞏sp暗ec犯ti藏ve刑ly辯,冬an拌dev她er眨yve麻rt咬exinV1is繼c駝on濁ne棟ct單ed可t門oev欣er晨y牽ve畫rt限exinV2,竟de恥no愁te攤d員byKm,n,封wh歷er匆em=懶|V1