圖論及其應(yīng)用ch12

1、4/1/2024 12:05 AM,Li-Li Zhang,1,兩個(gè)有趣的問題,1.任意一群人中（人數(shù)不小于2），總有兩人在該人群中認(rèn)識(shí)相同的朋友數(shù)。2.在一次象棋比賽中，任意兩名選手間至多下一盤，試證總存在兩名選手，他們下過的盤數(shù)相同。問題1：如何用學(xué)過的知識(shí)解答上述問題？問題2：上述問題的解答是否相同？若不同，區(qū)別在哪？,4/1/2024 12:05 AM,Li-Li Zhang,2,Key web,http://amuseu

2、m.cdstm.cn/AMuseum/math/index.htm中國數(shù)字科技館，數(shù)學(xué)，信息科學(xué)等,4/1/2024 12:05 AM,Li-Li Zhang,3,1 圖的基本概念/1.1 圖論發(fā)展史,圖論是組合數(shù)學(xué)的一個(gè)分支，也是近幾十年來最活躍的數(shù)學(xué)分支之一.到目前為止，它已有二百六十多年的發(fā)展歷史.圖論的發(fā)展歷史大體可以分為三個(gè)階段：第一階段是圖論的萌芽階段，它從十八世紀(jì)中葉到十九世紀(jì)中葉.這時(shí)，圖論的多數(shù)問題是圍繞游戲而產(chǎn)

3、生的，其代表性的工作就是Königsberg七橋問題.1736年L.Euler發(fā)表了他著名的Königsberg七橋問題的論文，這是圖論的第一篇文章.,4/1/2024 12:05 AM,Li-Li Zhang,4,第二階段從十九世紀(jì)中葉到二十世紀(jì)中葉.在此階段，圖論問題大量出現(xiàn).如著名的四色問題、Hamilton問題以及圖的可平面問題等. 在第二個(gè)階段還應(yīng)該特別提到Cayley把樹應(yīng)用于化學(xué)領(lǐng)域，Kirchhoff

4、用樹去研究電網(wǎng)絡(luò)的分析問題.在漫長的300年中，圖論幾乎停留在數(shù)學(xué)游戲階段.雖然這階段里21歲的G.Kirchhoff在1847年從電網(wǎng)絡(luò)問題，A.Cayley在1857年從計(jì)算有機(jī)化學(xué)的同分異構(gòu)等不止一次地建立起圖論的基本概念，但是直到1936年D.König發(fā)表的經(jīng)典著作>才有了圖論的第一本專著.,4/1/2024 12:05 AM,Li-Li Zhang,5,二十世紀(jì)中葉以后是圖論發(fā)展的第三階段，即圖論的應(yīng)用階段.

5、由于生產(chǎn)管理、軍事、交通運(yùn)輸、計(jì)算機(jī)網(wǎng)絡(luò)、計(jì)算機(jī)科學(xué)、數(shù)字通訊、線性規(guī)劃、運(yùn)籌學(xué)等方面提出的實(shí)際問題的需要，特別是許多離散性問題的出現(xiàn)、刺激和推動(dòng)，以及由于有了大型電子計(jì)算機(jī)，而使大規(guī)模問題的求解成為可能，圖論及其應(yīng)用的研究得到了飛速的發(fā)展.這個(gè)階段的開創(chuàng)性工作是以Ford和Fulkerson建立的網(wǎng)絡(luò)流理論為代表的.圖論與其它學(xué)科的相互滲透，以及圖論在生產(chǎn)實(shí)際中廣泛地應(yīng)用，都使圖論的發(fā)展更加充滿活力.,4/1/2024 12:05 A

6、M,Li-Li Zhang,6,幾個(gè)有趣的圖論問題,Königsberg七橋背后的故事 Königsberg七橋位于前蘇聯(lián)的加里寧格勒，歷史上曾是德國東普魯士省的省會(huì)，霹雷格爾橫穿城堡，河中有兩個(gè)小島B與C，并有七座橋連接島與河岸及島與島（見圖）。是否存在一種走發(fā)，從四塊陸地中的任意一塊開始，通過每一座橋恰好一次再回到起點(diǎn)。這就是著名的Königsberg七橋問題，即一筆畫問題；也是圖論的起源。,4

7、/1/2024 12:05 AM,Li-Li Zhang,7,4/1/2024 12:05 AM,Li-Li Zhang,8,四色問題,為了能夠迅速地區(qū)分一個(gè)平面地圖或球面地圖上的各個(gè)國家（假設(shè)這些國家在地圖上都是連通的），需要用若干種顏色對(duì)這些國家著色，使得具有公共邊界的兩個(gè)國家涂染不同的顏色.那么，要保證每張地圖都能如此著色，最少需要多少種顏色？這個(gè)問題是1850年被一名剛畢業(yè)的大學(xué)生Francis Guthrie首先提出的，直到1

8、976年，四色問題被美國Illinois大學(xué)的K.Appel和W.Haken用計(jì)算機(jī)證明是正確的，這個(gè)證明令數(shù)學(xué)界震驚，它用了1200多小時(shí)，作出100億個(gè)獨(dú)立的邏輯判斷.盡管有了這個(gè)機(jī)器證明，但它仍然是數(shù)學(xué)上未解決的問題之一 .,4/1/2024 12:05 AM,Li-Li Zhang,9,Hamilton問題,Hamilton問題是圖論中一直懸而未解的一大問題。它起源于1856年，當(dāng)時(shí)英國數(shù)學(xué)家Hamilton設(shè)計(jì)了一種名為周游世

9、界的游戲。他在一個(gè)實(shí)心的正十二面體的十二個(gè)頂點(diǎn)上標(biāo)以世界上著名的二十座城市的名字，要求游戲者沿十二面體的棱從一個(gè)城市出發(fā)，經(jīng)過每座城市恰好一次，然后返回到出發(fā)點(diǎn)，即“繞行世界”。正十二面體的頂點(diǎn)與棱的關(guān)系可以用平面上的圖表示，把正十二面體的頂點(diǎn)與棱分別對(duì)應(yīng)圖的頂點(diǎn)與邊，就得到正十二面體圖。,4/1/2024 12:05 AM,Li-Li Zhang,10,,正十二面體 Peterson圖,4/1/2024 12:05 AM,

10、Li-Li Zhang,11,旅行售貨員問題,給出城市之間的距離，要求一位推銷員從某一城市出發(fā)，周游每個(gè)城市一次，然后回到出發(fā)的城市，并且選的路徑最短。這是一個(gè)圖論優(yōu)化問題，最早由美國數(shù)學(xué)家威特涅于1934年在普林斯頓一次討論班上提出。1954年幾位美國數(shù)學(xué)家寫了第一篇論文，用線性方程的方法解決了49個(gè)城市的旅行售貨員問題。后來也有不少論文討論這個(gè)問題，在理論和應(yīng)用上都很有價(jià)值。,4/1/2024 12:05 AM,Li-Li Zha

11、ng,12,生活中，人們常常需要考慮一些對(duì)象之間的某種特定的關(guān)系.如某區(qū)域內(nèi)，兩城市之間有無交通線；一群人中，兩個(gè)人之間相識(shí)或不相識(shí)等等.這種關(guān)系是對(duì)稱的，即如果甲對(duì)于乙有某種關(guān)系，則乙對(duì)于甲也有這種關(guān)系.可以用一個(gè)圖形來描述給定對(duì)象之間的某個(gè)關(guān)系?：我們用平面上的點(diǎn)分別表示這些對(duì)象，若對(duì)象甲和乙有關(guān)系?，就用一條線連接表示甲和乙的兩個(gè)點(diǎn).這種由一些點(diǎn)與連接其中某些點(diǎn)對(duì)的線所構(gòu)成的圖形就是圖論中所研究的圖. 圖/Graph：可直觀地表

12、示離散對(duì)象之間的相互關(guān)系，研究它們的共性和特性，以便解決具體問題。,1.2 圖的定義,4/1/2024 12:05 AM,Li-Li Zhang,13,無向圖（簡(jiǎn)稱圖）: 一個(gè)圖是指一個(gè)有序三元組(V(G),E(G), ?),其中V(G)是一個(gè)非空有限集，Ｅ(G)是與Ｖ(G)不相交的有限集合,?是關(guān)聯(lián)函數(shù)，它使E(G)中每一元素對(duì)應(yīng)于V(G)中的無序元素對(duì)（可以相同）,幾個(gè)重要定義,有,A(D),有,實(shí)際上,有向圖即將無向圖中的無序?qū)?/p>

13、看成有序?qū)?其中有向圖對(duì)應(yīng)的無向圖稱為有向圖的基礎(chǔ)圖。其中V(G)稱為頂點(diǎn)集,E(G)稱為邊集（A(D)又稱為弧集）.令p(G)=|V(G)|,q(G)=|E(G)|, 分別稱為圖的階和邊數(shù)。舉例說明。,A(D),A(D),有向,4/1/2024 12:05 AM,Li-Li Zhang,14,如果一個(gè)圖的頂點(diǎn)集和邊集都是有限集則稱該圖為有限圖,否則稱為無限圖.只有一個(gè)頂點(diǎn)所構(gòu)成的圖稱為平凡圖,其它的稱為非平凡圖.如果一個(gè)圖中沒有環(huán)

14、也沒有重邊稱為簡(jiǎn)單圖。,4/1/2024 12:05 AM,Li-Li Zhang,15,圖/graph; 有向圖/directed graph; 相鄰/adjacent，關(guān)聯(lián)/incident；頂點(diǎn)/vertex; 孤立的/isolated，環(huán)/loop。 在有向圖G中，若e=（ａ，ｂ）∈Ｅ，即箭頭由ａ到ｂ，稱ａ相鄰到ｂ，或a關(guān)聯(lián)或聯(lián)結(jié)b。a稱為e的起點(diǎn)/initial vertex，b稱為e的終點(diǎn)/terminal o

15、r end vertex。,4/1/2024 12:05 AM,Li-Li Zhang,16,1.嚴(yán)格有向圖：既無自回路又無平行邊的有向圖。2.非對(duì)稱有向圖：在兩點(diǎn)間最多有一條有向邊，但允許有自回路的有向圖。3.對(duì)稱有向圖：對(duì)于圖中每一邊(a,b),總存在另一邊(b,a)的有向圖。4.完全有向圖:(1)完全對(duì)稱有向圖：一個(gè)從任一點(diǎn)到其他點(diǎn)有一條且僅有一條有向邊的簡(jiǎn)單圖；(2)完全非對(duì)稱有向圖：任何兩點(diǎn)有一條且只有一條有向邊的非對(duì)稱

16、圖。,有向圖的種類：,4/1/2024 12:05 AM,Li-Li Zhang,17,有向圖在成對(duì)比較中的應(yīng)用,在很多實(shí)驗(yàn)中，特別在社會(huì)科學(xué)領(lǐng)域，要求人們通過對(duì)事物的兩兩比較排出它們的名次。這種方法稱為成對(duì)比較法。例如，測(cè)定對(duì)音樂作品的個(gè)人愛好時(shí)，每一次對(duì)一個(gè)主題取出兩個(gè)作品，問一個(gè)人他喜歡哪一個(gè)。記錄了n個(gè)作品成對(duì)比較所有n(n-1)/2種可能的結(jié)果后，實(shí)驗(yàn)者就能根據(jù)某人的愛好排出n個(gè)作品的品次。Kendall在1948年做的一個(gè)

17、分類實(shí)驗(yàn)時(shí)，對(duì)六種不同的狗食排名次。每天在六種食品中任選兩種喂狗。實(shí)驗(yàn)安排了15天，所有可能配對(duì)的食物都被試過，在圖中，一條邊是從喜歡的食物引向比較不喜歡的食物，這樣的圖稱為優(yōu)化圖。,4/1/2024 12:05 AM,Li-Li Zhang,18,有向圖在競(jìng)賽中的應(yīng)用,在單循環(huán)賽中，每個(gè)運(yùn)動(dòng)員和所有其他運(yùn)動(dòng)員比賽，比賽結(jié)果可以用有向圖表示。圖中一條頂點(diǎn)a指向b的邊表示運(yùn)動(dòng)員a勝過運(yùn)動(dòng)員b。所以完全非對(duì)稱圖又稱為競(jìng)賽圖。按得分排名次：

18、根據(jù)運(yùn)動(dòng)員得分排名次，得分是運(yùn)動(dòng)員在比賽中勝的局?jǐn)?shù)，反映在有向圖中是點(diǎn)的出度。,4/1/2024 12:05 AM,Li-Li Zhang,19,1.3 頂點(diǎn)的度,頂點(diǎn)的度： 在無向圖G中,與a相鄰的頂點(diǎn)的數(shù)目稱為v的度/degree,記為d(v)。分別用 表示G中的最小度和最大度。度為零的頂點(diǎn)稱為孤立頂點(diǎn)。在有向圖G中,以v為終點(diǎn)的邊的條數(shù)稱為v的入度/in-degree,記為d–(v)。以v為起點(diǎn)的邊的條數(shù)稱為

19、v的出度/out-degree,記為d+(v)。 有向圖中，V的度數(shù)=d–(v)+ d+(v),,4/1/2024 12:05 AM,Li-Li Zhang,20,定理1.3.1 (Handshaking) 設(shè)無向圖G=（V，E）有e條邊，則G中所有頂點(diǎn)的度之和等于e的兩倍。證明思路：考慮每條邊在求和中的貢獻(xiàn)。定理1.3.2 無向圖中度為奇數(shù)的頂點(diǎn)個(gè)數(shù)恰有偶數(shù)個(gè)。證明思路：將圖中頂點(diǎn)的次分類，再利用定理1。定理1.3

20、.3 設(shè)有向圖G=（V，A）有e條邊，則G中所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和，也等于e。證明思路：考慮每條邊在求和中的情況。,即Σd(v)=2e,即Σd¯(v)= Σ d+(v)=e,記住了嗎？,幾個(gè)重要定理,4/1/2024 12:05 AM,Li-Li Zhang,21,推論,4/1/2024 12:05 AM,Li-Li Zhang,22,例1 證明任何一群人中，有偶數(shù)個(gè)人認(rèn)識(shí)其中奇數(shù)個(gè)人.(匈牙利數(shù)學(xué)競(jìng)賽試

21、題)[證] 用n個(gè)頂點(diǎn)表示n個(gè)人.如果兩個(gè)人相識(shí)，就用一條線把他們對(duì)應(yīng)的一對(duì)頂點(diǎn)連起來，這樣就得到了一個(gè)圖G.每一個(gè)人所認(rèn)識(shí)的人的數(shù)目就是他對(duì)應(yīng)的頂點(diǎn)的次，于是問題就轉(zhuǎn)化為證明圖G中奇點(diǎn)的個(gè)數(shù)為偶數(shù)，而這正是定理1.3.2的結(jié)論.,4/1/2024 12:05 AM,Li-Li Zhang,23,,例2 設(shè)是平面上n個(gè)點(diǎn)，其中任意兩點(diǎn)的距離至少是1，證明至多有3n對(duì)點(diǎn)，每對(duì)點(diǎn)的距離恰好是1.[證] 以這n個(gè)點(diǎn)為頂點(diǎn)作圖G，使得

22、與 相鄰當(dāng)且僅當(dāng) 與 的距離恰好是 .于是，距離恰為1的點(diǎn)對(duì)的數(shù)目就是G的邊數(shù)q.顯然，在G中的鄰點(diǎn)一定在以 為圓心，以1為半徑的圓周上.由于任一對(duì)點(diǎn)的距離至少是1,于是， 所以 即 .結(jié)論成立,,例2,4/1/2024 12:05 AM,Li-Li Zhang,24,例3,在一次圍棋擂臺(tái)賽中，雙方各出

23、n名選手。比賽的規(guī)則是雙方先各自排定一個(gè)次序，設(shè)甲方排定的次序?yàn)?乙方排定的次序?yàn)?4/1/2024 12:05 AM,Li-Li Zhang,25,1.4 子圖與圖的運(yùn)算,子圖：Ｇ＝(Ｖ,E)是圖,若Ｇ’=(Ｖ’,Ε’)也是圖且滿足:(1)Ｖ’?Ｖ；(2)Ｅ’?Ｅ；則稱Ｇ’為Ｇ的子圖/subgraph。生成子圖： 當(dāng)Ｖ’＝Ｖ時(shí),稱Ｇ’為Ｇ的生成子圖。真子圖:當(dāng)Ｅ’≠Ｅ或Ｖ’≠Ｖ時(shí),稱Ｇ’

24、為Ｇ的真子圖。導(dǎo)出子圖:設(shè)Ｖ’?Ｖ,由Ｖ’內(nèi)的所有頂點(diǎn)及其頂點(diǎn)之間的所有邊得到的子圖稱為G的導(dǎo)出子圖（由頂點(diǎn)確定）；邊導(dǎo)出子圖：設(shè)Ｅ’?Ｅ,由邊集E’的所有邊及其邊的頂點(diǎn)集得到的子圖稱為G的邊導(dǎo)出子圖(由邊確定）.舉例說明其區(qū)別。,4/1/2024 12:05 AM,Li-Li Zhang,26,相對(duì)補(bǔ)圖/complementary graph ：Ｇ＝（Ｖ，Ｅ）是圖，Ｇ’＝（Ｖ’，Ε’）是Ｇ的子圖，Ｅ”＝Ｅ－Ｅ’，Ｖ” ＝V－V’

25、或是Ｅ”中邊所關(guān)聯(lián)的所有頂點(diǎn)集合，則Ｇ”＝（Ｖ”，Ｅ”）稱為Ｇ’關(guān)于Ｇ的相對(duì)補(bǔ)圖。補(bǔ)圖： 關(guān)于完全圖的子圖的補(bǔ)圖稱為此子圖的絕對(duì)補(bǔ)圖，若子圖記為Ｇ，則補(bǔ)圖記為 。,4/1/2024 12:05 AM,Li-Li Zhang,27,圖的運(yùn)算,圖的并/union：Ｇ＝（Ｖ，Ｅ）和Ｇ’＝（Ｖ’，Ε’）是兩個(gè)簡(jiǎn)單無向圖，它們的并圖Ｇ?Ｇ’定義為 Ｇ?Ｇ’=（Ｖ’ ?Ｖ，Ｅ’ ?Ｅ）.圖的和：Ｇ＝（Ｖ，Ｅ）和Ｇ’＝（Ｖ’，Ε’）

26、是兩個(gè)不相交的簡(jiǎn)單無向圖，稱Ｇ+Ｇ’為G和G’的和，其中Ｇ+Ｇ’=（Ｖ’ ?Ｖ，Ｅ’ ?Ｅ?Ｅ’’).圖的交：Ｇ＝（Ｖ，Ｅ）和Ｇ’＝（Ｖ’，Ε’）是兩個(gè)簡(jiǎn)單無向圖，稱Ｇ Ｇ’為G和G’的交，其中Ｇ Ｇ’=（Ｖ’ Ｖ，Ｅ’ Ｅ).舉例說明。,4/1/2024 12:05 AM,Li-Li Zhang,28,1.5 特殊圖類,完全圖/complete graph：圖G中的每對(duì)不同頂點(diǎn)之間恰有一條邊?？?qǐng)D/empty graph

27、：邊集為空的圖。問題：完全圖的補(bǔ)圖是怎樣的圖？設(shè)G=(V,E)是p階圖,若V可以劃分為m個(gè)非空,4/1/2024 12:05 AM,Li-Li Zhang,29,補(bǔ)充特殊圖類,練習(xí)：畫出一個(gè)完全二部圖/bipartite graph。輪圖/wheel:由一個(gè)圈添加一個(gè)新頂點(diǎn),并且把這個(gè)頂點(diǎn)與圈的所有頂點(diǎn)相連得到的圖稱為輪，新的邊稱為輻。正則圖：每個(gè)頂點(diǎn)的度都等于k的圖。線圖（邊圖）/line graph：圖G的線圖是以為E(G

28、)頂點(diǎn)集的圖,其中兩個(gè)頂點(diǎn)相鄰當(dāng)且僅當(dāng)它們?cè)贕中是相鄰的邊。練習(xí):各類特殊圖所含邊數(shù)的情況如何？,4/1/2024 12:05 AM,Li-Li Zhang,30,1.6 圖的矩陣表示與同構(gòu),圖G表示的三種方法：（1）集合表示（2）鄰接表（adjacency list）表示（3）矩陣（ matrix）表示 1、鄰接矩陣（adjacency matrix）表示 2、關(guān)聯(lián)矩陣（inciden

29、ce matrix）表示,4/1/2024 12:05 AM,Li-Li Zhang,31,關(guān)聯(lián)矩陣及其舉例說明,關(guān)聯(lián)矩陣：設(shè)G=(V,E)的頂點(diǎn)集和邊集分別為,關(guān)聯(lián)矩陣的性質(zhì): (1) B(G)的每一列元素之和均為2；(2) B(G)的每一行元素之和等于對(duì)應(yīng)頂點(diǎn)的度數(shù)。舉例說明。,4/1/2024 12:05 AM,Li-Li Zhang,32,鄰接矩陣及同構(gòu),4/1/2024 12:05 AM,Li-Li Zhang,33,鄰

30、接矩陣的性質(zhì),(1)主對(duì)角線所有元素都是0圖中無回路;(2)若無環(huán),頂點(diǎn)的度等于M中對(duì)應(yīng)行或列中的1的個(gè)數(shù)。(3) M是對(duì)稱的,所以如果兩行交換位置，那末相應(yīng)的列也應(yīng)交換位置。(4)圖G是分離圖,且有兩個(gè)分支G1和G2 它的鄰接矩陣能劃分成分塊對(duì)角矩陣。(5)給出任何一個(gè)n階對(duì)稱（0，1）方陣Q,總能構(gòu)造一個(gè)具有n個(gè)頂點(diǎn)的圖G，使得Q是G的鄰接矩陣。,4/1/2024 12:05 AM,Li-Li Zhang,34,從定義可以看

31、出，兩個(gè)同構(gòu)圖必然具備下列性質(zhì)：（1）具有相同的頂點(diǎn)數(shù)；（2）具有相同的邊數(shù)；（3）對(duì)于一個(gè)給定的度數(shù)具有相同的頂點(diǎn)數(shù)。反之不成立。舉例說明。,同構(gòu)圖的性質(zhì),4/1/2024 12:05 AM,Li-Li Zhang,35,例1 下面兩個(gè)圖不同構(gòu).,,,4/1/2024 12:05 AM,Li-Li Zhang,36,例2 證明：圖G和圖H同構(gòu).,,,4/1/2024 12:05 AM,Li-Li Zhang,37,同構(gòu)判

32、定算法（用鄰接矩陣）1、根據(jù)圖確定其鄰接矩陣（I)2、計(jì)算行次：矩陣每行１的個(gè)數(shù)，（對(duì)應(yīng)于出次） 和列次：（對(duì)應(yīng)于入次）3、不考慮出現(xiàn)的次序不同，若行次與列次不同，則必不同構(gòu)，否則繼續(xù)4、同時(shí)交換其一矩陣的ｉ行和ｊ行，ｉ列和ｊ列。 若此矩陣能變成與另一矩陣相同，則同構(gòu)。對(duì)所有頂點(diǎn)的排列都試過，仍不相同，則不同構(gòu)。,4/1/2024 12:05 AM,Li-Li Zhang,38,性質(zhì)：兩個(gè)圖G與H是同構(gòu)的充要條件是存在一個(gè)置換矩

33、陣P,使得M(G)=P'M(H)P.,4/1/2024 12:05 AM,Li-Li Zhang,39,作業(yè)：每人做一題，其中學(xué)號(hào)為1-15號(hào)對(duì)應(yīng)1-15題；其它學(xué)號(hào)的同學(xué)按照學(xué)號(hào)最后一位數(shù)字與題目最后一位數(shù)字對(duì)應(yīng)。注意：下次上課全部上交，作業(yè)寫在紙上，自己保管好。,4/1/2024 12:05 AM,Li-Li Zhang,40,2 圖的連通性/2.1 途徑、路和圈,途徑：Ｇ中相鄰邊的序列（Ｖ0,Ｖ1），（Ｖ1,Ｖ2），

34、…（Ｖk-1,Ｖk）稱為一條途徑.此途徑長度為ｋ.也可以（Ｖ0，Ｖ1，…，Ｖk）表示道路,Ｖ0為起點(diǎn)，Ｖk為終點(diǎn)，起點(diǎn)與終點(diǎn)相同時(shí)稱為閉途徑。跡/trace ：一條邊不重復(fù)出現(xiàn)的途徑稱為跡,當(dāng)Ｖ0=Ｖk時(shí)稱為閉跡。路/ Path :一條內(nèi)部頂點(diǎn)不重復(fù)出現(xiàn)的途徑稱為路；路所含的邊數(shù)稱為路的長度?；芈罚ㄈΓ?Cycle：一條內(nèi)部頂點(diǎn)不重復(fù)出現(xiàn)的閉路稱為圈。長度為奇數(shù)的圈稱奇圈，否則稱偶圈。,4/1/2024 12:05 AM,Li-

35、Li Zhang,41,其他概念,頂點(diǎn)間的距離：任意兩點(diǎn)u與v之間的最短路。圖的直徑:指G的兩個(gè)頂點(diǎn)之間的最大距離。完全圖的直徑是？其他特殊圖類呢？練習(xí)。圖的圍長：圖中最短圈的長度。圖的周長：圖中最長圈的長度。有向圖的相關(guān)概念可以類似定義。,4/1/2024 12:05 AM,Li-Li Zhang,42,相關(guān)定理及其證明,4/1/2024 12:05 AM,Li-Li Zhang,43,有向圖中路的應(yīng)用,例有A,B,C三個(gè)瓶

36、，分別能裝油8L,5L和3L.如果A裝滿油，B和C是空的，怎樣以最快的速度平分A中的油？[解法] 我們用三位數(shù)碼表示A,B,C三個(gè)瓶子裝油的情況，又因?yàn)槿粩?shù)碼之和不變，所以可以用后兩位數(shù)碼表示三個(gè)瓶子裝油的情況.例如：（0，0）表示初始狀態(tài).根據(jù)題意：共有十六種可能的狀態(tài)，用這16個(gè)狀態(tài)為頂點(diǎn)作圖G，使得兩個(gè)狀態(tài)相鄰當(dāng)且僅當(dāng)它們可以經(jīng)過一次倒油相互轉(zhuǎn)化.于是，問題就是要求從（0，0）到（4，0）的一條最短路.,4/1/2024 1

37、2:05 AM,Li-Li Zhang,44,容易作出圖G（如下圖）：,,4/1/2024 12:05 AM,Li-Li Zhang,45,通過觀察圖得知共有兩條從（0，0）到(4,0)的路：第一條: (0,0) ? (5,0)?(2,3) ? (2,0)?(0,2) ?(5,2) ?(4,3) ?(4,0);第二條: (0,0) ? (0,3)?(3,0) ? (3,3)?(5,1) ?(0,1) ?(1,0) ?(1,3) ?(

38、4,0);從而，最快的速度平分即是最短的路所對(duì)應(yīng)的過程，即第一條路的過程就是以最快的速度平分油的過程。,能說出具體操作嗎？,4/1/2024 12:05 AM,Li-Li Zhang,46,連通/connectivity:設(shè)Ｇ＝(Ｖ,Ｅ),若存在一條從Ｖ0，到Ｖk的一條道路，則稱Ｖ0到Ｖk連通。無向圖的連通性: 若圖Ｇ中任兩個(gè)不同頂點(diǎn)都連通，則稱此無向圖是連通的/connected,否則稱為非連通圖(分離圖)。連通分支/conn

39、ected components：圖Ｇ可分為幾個(gè)不相連通的子圖，每一子圖本身都是連通的。稱這幾個(gè)子圖為Ｇ的連通分支。,2.2 連通圖、非連通圖和成分,4/1/2024 12:05 AM,Li-Li Zhang,47,說明：對(duì)無向圖而言，若Ｖ0到Ｖk可達(dá)，則Ｖk到Ｖ0也可達(dá)。對(duì)有向圖而言則未必。有向圖的連通性：(1)弱連通：Ｇ＝（Ｖ，Ｅ）對(duì)應(yīng)的無向圖是連通圖，則稱Ｇ為弱連通/weakly connected。(2）強(qiáng)連通：若Ｇ＝（Ｖ

40、，Ｅ）中任兩點(diǎn)間都有路，即對(duì)ａ與ｂ，ａ到ｂ可達(dá)，ｂ到ａ可達(dá)，稱Ｇ為強(qiáng)連通/strongly connected。(3)單向連通：如果有向圖D的任何兩個(gè)頂點(diǎn)至少由一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)可達(dá),則稱D是單向連通的。,有向圖的連通性,4/1/2024 12:05 AM,Li-Li Zhang,48,例：用圖描述一臺(tái)自動(dòng)售貨機(jī)，只用５分，１０分二種硬幣，滿１５分后壓按鈕，選擇一塊巧克力，錢多了不找還。,4/1/2024 12:05 AM,Li-L

41、i Zhang,49,頂點(diǎn):ａ：０ 分邊： ５：投５分 ｂ：５分 １０：投１０分 ｃ：１０分 ｐ：壓按扭動(dòng)作 ｄ：≥１５分 表示已投入錢的狀態(tài) 表示一種動(dòng)作自動(dòng)售貨機(jī)：有向加權(quán)圖描繪得很清楚（1）錢數(shù)不夠，壓按扭，不起作用（2）錢數(shù)夠了,壓按扭,給過糖果回到０分狀態(tài) （3）錢超過１５分，再加錢白加,4/1/2024

42、 12:05 AM,Li-Li Zhang,50,一個(gè)簡(jiǎn)單定理的應(yīng)用,定理2.2.1:設(shè)G是p階簡(jiǎn)單圖,每個(gè)頂點(diǎn)的度至少是[p/2],則G是連通圖。例1: 用一些圓面覆蓋平面上取定的2n個(gè)點(diǎn)。試證：若每個(gè)圓面至少覆蓋n+1個(gè)點(diǎn)則任兩個(gè)點(diǎn)能由平面上的一條折線所連接，而這條折線整個(gè)地被某些圓面覆蓋。證明：構(gòu)造相應(yīng)的圖，得到頂點(diǎn)的最小度，應(yīng)用定理即可證明。,4/1/2024 12:05 AM,Li-Li Zhang,51,附加定理,定理2

43、 如果一個(gè)圖只有兩點(diǎn)的度數(shù)是奇數(shù)，那末這兩點(diǎn)間必有一條通路。,4/1/2024 12:05 AM,Li-Li Zhang,52,定理2.2.2：一個(gè)有n個(gè)頂點(diǎn)和k個(gè)成分的簡(jiǎn)單圖最多有(n-k)(n-k+1)/2條邊.,4/1/2024 12:05 AM,Li-Li Zhang,53,在鄰接矩陣中，若ａij＝１，表明Ｖi到Ｖj有一條邊，即Ｖi到Ｖj可達(dá)；若ａij＝０說明Ｖi到Ｖj沒有道路.若通過其他點(diǎn)中轉(zhuǎn)，也有可能連通。作鄰接矩陣的普通

44、矩陣乘法：,用鄰接矩陣討論連通性,4/1/2024 12:05 AM,Li-Li Zhang,54,ｂij的值表示Ｖi到Ｖj長為２的途徑的條數(shù);一般地，就有：Ａm的元素ｍij表示Ｖi到Ｖj長為ｍ的途徑的條數(shù)。,定理2.2.3:設(shè)M(G)是G的鄰接矩陣，則G中連接Ｖi到Ｖj長為ｍ的途徑的條數(shù)等于Ａm的元素ｍij，其中Ａm是矩陣A自身作m次乘法得到的矩陣。,推論:若G是簡(jiǎn)單圖，則對(duì)每一個(gè)頂點(diǎn)vi,i=1,2,…,p有dG(vi)=aii(

45、2)，即矩陣A自身作2次乘法得到的矩陣的對(duì)角線元素。,4/1/2024 12:05 AM,Li-Li Zhang,55,鄰接矩陣與連通性,定理2.2.4:階至少為3的圖G是連通的充要條件為R(G)中的每個(gè)元素都不等于零，其中R(G)=M(G)+M2(G)+…+ Mp-1(G)。定理2.2.5：設(shè)D是連通的有向圖，則D是強(qiáng)連通的當(dāng)且僅當(dāng)D的每條弧都含在一個(gè)有向回路中。（了解）,4/1/2024 12:05 AM,Li-Li Zhang

46、,56,頂點(diǎn)割:若V的子集V’使得G-V’不連通,則V’稱為G的頂點(diǎn)割.k頂點(diǎn)割是指有k個(gè)元素的頂點(diǎn)割. 連通度:若G不是完全圖,則G所有頂點(diǎn)割中的最小的k,稱為G的連通度,記為 ;否則定義 為v-1. 若 ,則稱G為k連通的.,2.3 連通度,4/1/2024 12:05 AM,Li-Li Zhang,57,邊割:若E(G)的子集E’使得G-E’不連通,則E’稱為G的邊割.

47、K邊割是指有k個(gè)元素的邊割.邊連通度 :G的所有k邊割中最小的k. 若G是平凡的,則 定義為0. 若 ,則稱G為k邊連通的.,邊連通度,4/1/2024 12:05 AM,Li-Li Zhang,58,連通度和邊連通度的等價(jià)定義（更實(shí)用）,等價(jià)定義1：圖G是k連通的當(dāng)且僅當(dāng)對(duì)任意一個(gè)點(diǎn)數(shù)不超過k-1的頂點(diǎn)子集V'，G-V'仍然連通。等價(jià)定義2.1：圖G

48、是k邊連通的當(dāng)且僅當(dāng)對(duì)任意一個(gè)邊數(shù)不超過k-1的邊子集E' ，G-E'仍然連通。等價(jià)定義2.2：圖G是k邊連通的當(dāng)且僅當(dāng)對(duì)任一非空真子集S,均有|[S,?]| ≥k，其中[S,?]表示一個(gè)頂點(diǎn)在S中一個(gè)頂點(diǎn)在?中的所有邊集, ?是S的補(bǔ)集 。,4/1/2024 12:05 AM,Li-Li Zhang,59,幾者之間的聯(lián)系,4/1/2024 12:05 AM,Li-Li Zhang,60,幾者之間的聯(lián)系,定理2.3.1

49、: 對(duì)任意簡(jiǎn)單圖，有（定理證明無需掌握,要記熟三者之間的關(guān)系）問題：怎樣的圖可以取到等號(hào)呢？設(shè)G是p階簡(jiǎn)單連通圖，若對(duì)于G的任意四個(gè)頂點(diǎn)u,v,x,y,若|[{u,v},{x,y}]|=0就有d(u)+d(v)+d(x)+d(y) ≥2p-3,則事實(shí)上，還有很多圖類滿足第一個(gè)不等式中的等號(hào)關(guān)系，你能自己找到嗎？(課后自己練習(xí)),4/1/2024 12:05 AM,Li-Li Zhang,61,幾個(gè)重要定理,G中一族路稱為內(nèi)部不相

50、交的:如果G中任意兩條路除起點(diǎn)和終點(diǎn)外沒有公共頂點(diǎn)。定理2.3.2 一個(gè)階不小于3的圖是2連通的,當(dāng)且僅當(dāng)G的任意兩個(gè)頂點(diǎn)至少被兩條內(nèi)部不相交的路所連.推論1 若G是2連通圖,則G的任意兩個(gè)頂點(diǎn)（或任意兩條邊）都位于同一個(gè)圈上.邊e稱為被剖分,是指刪去它并換上一條連接它的兩個(gè)端點(diǎn)而長為2的路.,4/1/2024 12:05 AM,Li-Li Zhang,62,4/1/2024 12:05 AM,Li-Li Zhang,

51、63,定理2.3.3:一個(gè)圖是2邊連通的當(dāng)且僅當(dāng)任意兩個(gè)頂點(diǎn)至少由兩條邊不重的路所連.推論：連通圖G是2邊連通的充分必要條件是G的任意一條邊含在某個(gè)圈上。定理的推廣：圖G是k邊連通的當(dāng)且僅當(dāng)G的任意兩個(gè)相異頂點(diǎn)至少由k條邊不重的路所連.,4/1/2024 12:05 AM,Li-Li Zhang,64,2.4 最短路問題,最短路問題:在賦權(quán)圖中求某點(diǎn)到另一點(diǎn)的權(quán)值最小的路稱為最短路問題。Dijkstra算法：,練習(xí)25題,4/1/

52、2024 12:05 AM,Li-Li Zhang,65,應(yīng)用（一）,某企業(yè)使用一臺(tái)設(shè)備，每年年初，企業(yè)領(lǐng)導(dǎo)總要考慮是購買新設(shè)備還是繼續(xù)使用舊設(shè)備。若購新設(shè)備就要支付購買費(fèi)若使用舊的，就要支付一筆維修費(fèi)。具體需多少根據(jù)該設(shè)備使用的年數(shù)決定。問題：如何制定一個(gè)幾年之內(nèi)的設(shè)備更新計(jì)劃使得支付的費(fèi)用最少。,4/1/2024 12:05 AM,Li-Li Zhang,66,具體數(shù)據(jù)(單位：萬元),對(duì)應(yīng)圖論怎樣的問題？如何轉(zhuǎn)化？,4/1/2024

53、 12:05 AM,Li-Li Zhang,67,應(yīng)用（二）,某建筑公司簽訂了一項(xiàng)合同要為一家制造公司建造一座新的工廠。合同規(guī)定工廠的完工期限為12個(gè)月。要是工廠不能在一年內(nèi)完工，就要賠款，因此建筑公司的管理處要制定合理的安排表實(shí)際上屬于項(xiàng)目管理。,4/1/2024 12:05 AM,Li-Li Zhang,68,具體數(shù)據(jù)（建筑工序表）,精品課件！,精品課件！,4/1/2024 12:05 AM,Li-Li Zhang,71,2.5