圖論及其應(yīng)用ch12詳解課件

1、圖論及其應(yīng)用ch12詳解圖論及其應(yīng)用ch12詳解兩個(gè)有趣的問題1.任意一群人中（人數(shù)不小于2），總有兩人在該人群中認(rèn)識(shí)相同的朋友數(shù)。2.在一次象棋比賽中，任意兩名選手間至多下一盤，試證總存在兩名選手，他們下過的盤數(shù)相同。問題1：如何用學(xué)過的知識(shí)解答上述問題？問題2：上述問題的解答是否相同？若不同，區(qū)別在哪？9/9/20222Deren Chen, Zhejiang Univ.兩個(gè)有趣的問題1.任意一群人中（人數(shù)不小于2），總有兩人在該Key web/AMuseum/math/index.htm中國數(shù)字科技館，數(shù)學(xué)，信息科學(xué)等9/9/20223Deren Chen, Zhejiang Univ.

2、Key web1 圖的基本概念/1.1 圖論發(fā)展史 圖論是組合數(shù)學(xué)的一個(gè)分支，也是近幾十年來最活躍的數(shù)學(xué)分支之一.到目前為止，它已有二百六十多年的發(fā)展歷史.圖論的發(fā)展歷史大體可以分為三個(gè)階段：第一階段是圖論的萌芽階段，它從十八世紀(jì)中葉到十九世紀(jì)中葉.這時(shí)，圖論的多數(shù)問題是圍繞游戲而產(chǎn)生的，其代表性的工作就是Knigsberg七橋問題.1736年L.Euler發(fā)表了他著名的Knigsberg七橋問題的論文，這是圖論的第一篇文章.9/9/20224Deren Chen, Zhejiang Univ.1 圖的基本概念/1.1 圖論發(fā)展史 圖論是組合數(shù)學(xué)的第二階段從十九世紀(jì)中葉到二十世紀(jì)中葉.在此階段

3、，圖論問題大量出現(xiàn).如著名的四色問題、Hamilton問題以及圖的可平面問題等. 在第二個(gè)階段還應(yīng)該特別提到Cayley把樹應(yīng)用于化學(xué)領(lǐng)域，Kirchhoff用樹去研究電網(wǎng)絡(luò)的分析問題.在漫長(zhǎng)的300年中，圖論幾乎停留在數(shù)學(xué)游戲階段.雖然這階段里21歲的G.Kirchhoff在1847年從電網(wǎng)絡(luò)問題，A.Cayley在1857年從計(jì)算有機(jī)化學(xué)的同分異構(gòu)等不止一次地建立起圖論的基本概念，但是直到1936年D.Knig發(fā)表的經(jīng)典著作才有了圖論的第一本專著. 9/9/20225Deren Chen, Zhejiang Univ.第二階段從十九世紀(jì)中葉到二十世紀(jì)中葉.在此階段，圖論問題大量二十世紀(jì)中葉

4、以后是圖論發(fā)展的第三階段，即圖論的應(yīng)用階段.由于生產(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ā)展更加充滿活力.9/9/20226Deren Chen, Zhejiang Univ.二十世紀(jì)中葉以后是圖論發(fā)展的第三階段，即圖論的應(yīng)用階段.由于 幾個(gè)有趣的圖論問題

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

6、迅速地區(qū)分一個(gè)平面地圖或球面地圖上的各個(gè)國家（假設(shè)這些國家在地圖上都是連通的），需要用若干種顏色對(duì)這些國家著色，使得具有公共邊界的兩個(gè)國家涂染不同的顏色.那么，要保證每張地圖都能如此著色，最少需要多少種顏色？這個(gè)問題是1850年被一名剛畢業(yè)的大學(xué)生Francis Guthrie首先提出的，直到1976年，四色問題被美國Illinois大學(xué)的K.Appel和W.Haken用計(jì)算機(jī)證明是正確的，這個(gè)證明令數(shù)學(xué)界震驚，它用了1200多小時(shí)，作出100億個(gè)獨(dú)立的邏輯判斷.盡管有了這個(gè)機(jī)器證明，但它仍然是數(shù)學(xué)上未解決的問題之一 . 9/9/20229Deren Chen, Zhejiang Univ.四

7、色問題為了能夠迅速地區(qū)分一個(gè)平面地圖或球面地圖上的各個(gè)國家Hamilton問題Hamilton問題是圖論中一直懸而未解的一大問題。它起源于1856年，當(dāng)時(shí)英國數(shù)學(xué)家Hamilton設(shè)計(jì)了一種名為周游世界的游戲。他在一個(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)與邊，就得到正十二面體圖。9/9/202210Deren Chen, Zhejiang Univ.Hamilton問題Hamilton問

8、題是圖論中一直懸而未解正十二面體 Peterson圖9/9/202211Deren Chen, Zhejiang Univ.正十二面體 Peterson圖9/4/202213旅行售貨員問題給出城市之間的距離，要求一位推銷員從某一城市出發(fā)，周游每個(gè)城市一次，然后回到出發(fā)的城市，并且選的路徑最短。這是一個(gè)圖論優(yōu)化問題，最早由美國數(shù)學(xué)家威特涅于1934年在普林斯頓一次討論班上提出。1954年幾位美國數(shù)學(xué)家寫了第一篇論文，用線性方程的方法解決了49個(gè)城市的旅行售貨員問題。后來也有不少論文討論這個(gè)問題，在理論和應(yīng)用上都很有價(jià)值。9/9/202212Deren Chen, Zhejiang Univ.旅行

9、售貨員問題給出城市之間的距離，要求一位推銷員從某一城市出生活中，人們常常需要考慮一些對(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：可直觀地表示離散對(duì)象之間的相互關(guān)系，研究它們的共性和特性，以便解決具體問題。1.2 圖的定義9/9/202213Deren Chen

10、, Zhejiang Univ.生活中，人們常常需要考慮一些對(duì)象之間的某種特定的關(guān)系.如某區(qū)無向圖（簡(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ū)闯捎行驅(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)有向9/9/20221

11、4Deren Chen, Zhejiang Univ.無向圖（簡(jiǎn)稱圖）: 一個(gè)圖是指一個(gè)有序三元組(V(G),E( 如果一個(gè)圖的頂點(diǎn)集和邊集都是有限集則稱該圖為有限圖,否則稱為無限圖.只有一個(gè)頂點(diǎn)所構(gòu)成的圖稱為平凡圖,其它的稱為非平凡圖.如果一個(gè)圖中沒有環(huán)也沒有重邊稱為簡(jiǎn)單圖。9/9/202215Deren Chen, Zhejiang Univ. 如果一個(gè)圖的頂點(diǎn)集和邊集都是有限集則稱該圖為有限圖,圖/graph; 有向圖/directed graph; 相鄰/adjacent，關(guān)聯(lián)/incident；頂點(diǎn)/vertex; 孤立的/isolated，環(huán)/loop。 在有向圖G中，若e=（，）

12、，即箭頭由到，稱相鄰到，或a關(guān)聯(lián)或聯(lián)結(jié)b。a稱為e的起點(diǎn)/initial vertex，b稱為e的終點(diǎn)/terminal or end vertex。9/9/202216Deren Chen, Zhejiang Univ.圖/graph; 有向圖/directed graph; 相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)有一條且

13、只有一條有向邊的非對(duì)稱圖。有向圖的種類：9/9/202217Deren Chen, Zhejiang Univ.1.嚴(yán)格有向圖：既無自回路又無平行邊的有向圖。有向圖的種類： 有向圖在成對(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è)分類實(shí)驗(yàn)時(shí)，對(duì)六種不同的狗食排名次。每天在六種食品中任選兩種喂狗。實(shí)驗(yàn)安排了

14、15天，所有可能配對(duì)的食物都被試過，在圖中，一條邊是從喜歡的食物引向比較不喜歡的食物，這樣的圖稱為優(yōu)化圖。9/9/202218Deren Chen, Zhejiang Univ. 有向圖在成對(duì)比較中的應(yīng)用 在很多實(shí)驗(yàn)中，特別在社會(huì) 有向圖在競(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)賽圖。按得分排名次：根據(jù)運(yùn)動(dòng)員得分排名次，得分是運(yùn)動(dòng)員在比賽中勝的局?jǐn)?shù)，反映在有向圖中是點(diǎn)的出度。9/9/202219Deren Chen, Zhejiang Univ. 有向圖在競(jìng)賽中的應(yīng)用在單循環(huán)賽

15、中，每個(gè)運(yùn)動(dòng)員和所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ù)稱為v的出度/out-degree,記為d+(v)。 有向圖中，V的度數(shù)=d(v)+ d+(v),9/9/202220Deren Chen, Zhejiang Univ.1.3 頂點(diǎn)的度頂點(diǎn)的度： 在無向圖G中,與a相鄰的頂點(diǎn)的數(shù)定理1.3.1 (Handshaking) 設(shè)無向圖G=（V，E）有e條邊，則G中所有頂

16、點(diǎn)的度之和等于e的兩倍。證明思路：考慮每條邊在求和中的貢獻(xiàn)。定理1.3.2 無向圖中度為奇數(shù)的頂點(diǎn)個(gè)數(shù)恰有偶數(shù)個(gè)。證明思路：將圖中頂點(diǎn)的次分類，再利用定理1。定理1.3.3 設(shè)有向圖G=（V，A）有e條邊，則G中所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和，也等于e。證明思路：考慮每條邊在求和中的情況。即d(v)=2e即d(v)= d+(v)=e記住了嗎？幾個(gè)重要定理9/9/202221Deren Chen, Zhejiang Univ.定理1.3.1 (Handshaking) 設(shè)無向圖G推論9/9/202222Deren Chen, Zhejiang Univ.推論9/4/202224Dere

17、n Chen, Zhejia例1 證明任何一群人中，有偶數(shù)個(gè)人認(rèn)識(shí)其中奇數(shù)個(gè)人.(匈牙利數(shù)學(xué)競(jìng)賽試題)證 用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é)論.9/9/202223Deren Chen, Zhejiang Univ.例1 證明任何一群人中，有偶數(shù)個(gè)人認(rèn)識(shí)其中奇數(shù)個(gè)人.(匈牙利例2 設(shè)是平面上n個(gè)點(diǎn)，其中任意兩點(diǎn)的距離至少是1，證明至多有3n對(duì)點(diǎn)，每對(duì)點(diǎn)的距離恰好是1.證 以這n個(gè)點(diǎn)為頂點(diǎn)作圖G，使得 與 相鄰當(dāng)且僅當(dāng)

18、 與 的距離恰好是 .于是，距離恰為1的點(diǎn)對(duì)的數(shù)目就是G的邊數(shù)q.顯然，在G中的鄰點(diǎn)一定在以 為圓心，以1為半徑的圓周上.由于任一對(duì)點(diǎn)的距離至少是1,于是， 所以 即 .結(jié)論成立例29/9/202224Deren Chen, Zhejiang Univ.例2 設(shè)是平面上n個(gè)點(diǎn)，其中任意兩點(diǎn)的距離至少是1，證明至多例3在一次圍棋擂臺(tái)賽中，雙方各出n名選手。比賽的規(guī)則是雙方先各自排定一個(gè)次序，設(shè)甲方排定的次序?yàn)?乙方排定的次序?yàn)?/9/202225Deren Chen, Zhejiang Univ.例3在一次圍棋擂臺(tái)賽中，雙方各出n名選手。比賽的規(guī)則是雙方先1.4 子圖與圖的運(yùn)算子圖：(,E)是圖

19、,若=(,)也是圖且滿足:(1)；(2)；則稱為的子圖/subgraph。生成子圖： 當(dāng)時(shí),稱為的生成子圖。真子圖:當(dāng)或時(shí),稱為的真子圖。導(dǎo)出子圖:設(shè),由內(nèi)的所有頂點(diǎn)及其頂點(diǎn)之間的所有邊得到的子圖稱為G的導(dǎo)出子圖（由頂點(diǎn)確定）；邊導(dǎo)出子圖：設(shè),由邊集E的所有邊及其邊的頂點(diǎn)集得到的子圖稱為G的邊導(dǎo)出子圖(由邊確定）.舉例說明其區(qū)別。9/9/202226Deren Chen, Zhejiang Univ.1.4 子圖與圖的運(yùn)算子圖：(,E)是圖,若=(相對(duì)補(bǔ)圖/complementary graph ：（，）是圖，（，）是的子圖，”，” VV或是”中邊所關(guān)聯(lián)的所有頂點(diǎn)集合，則”（”，”）稱為關(guān)于的

20、相對(duì)補(bǔ)圖。補(bǔ)圖： 關(guān)于完全圖的子圖的補(bǔ)圖稱為此子圖的絕對(duì)補(bǔ)圖，若子圖記為，則補(bǔ)圖記為 。9/9/202227Deren Chen, Zhejiang Univ.相對(duì)補(bǔ)圖/complementary graph ：（圖的運(yùn)算圖的并/union：（，）和（，）是兩個(gè)簡(jiǎn)單無向圖，它們的并圖定義為 =（ ， ）.圖的和：（，）和（，）是兩個(gè)不相交的簡(jiǎn)單無向圖，稱+為G和G的和，其中+=（ ， ).圖的交：（，）和（，）是兩個(gè)簡(jiǎn)單無向圖，稱 為G和G的交，其中 =（ ， ).舉例說明。9/9/202228Deren Chen, Zhejiang Univ.圖的運(yùn)算圖的并/union：（，）和（，1.5

21、特殊圖類完全圖/complete graph：圖G中的每對(duì)不同頂點(diǎn)之間恰有一條邊?？?qǐng)D/empty graph：邊集為空的圖。問題：完全圖的補(bǔ)圖是怎樣的圖？設(shè)G=(V,E)是p階圖,若V可以劃分為m個(gè)非空9/9/202229Deren Chen, Zhejiang Univ.1.5 特殊圖類完全圖/complete graph：圖G補(bǔ)充特殊圖類練習(xí)：畫出一個(gè)完全二部圖/bipartite graph。輪圖/wheel:由一個(gè)圈添加一個(gè)新頂點(diǎn),并且把這個(gè)頂點(diǎn)與圈的所有頂點(diǎn)相連得到的圖稱為輪，新的邊稱為輻。正則圖：每個(gè)頂點(diǎn)的度都等于k的圖。線圖（邊圖）/line graph：圖G的線圖是以為E(G

22、)頂點(diǎn)集的圖,其中兩個(gè)頂點(diǎn)相鄰當(dāng)且僅當(dāng)它們?cè)贕中是相鄰的邊。練習(xí):各類特殊圖所含邊數(shù)的情況如何？9/9/202230Deren Chen, Zhejiang Univ.補(bǔ)充特殊圖類練習(xí)：畫出一個(gè)完全二部圖/bipartite g1.6 圖的矩陣表示與同構(gòu)圖G表示的三種方法：（1）集合表示（2）鄰接表（adjacency list）表示（3）矩陣（ matrix）表示 1、鄰接矩陣（adjacency matrix）表示 2、關(guān)聯(lián)矩陣（incidence matrix）表示9/9/202231Deren Chen, Zhejiang Univ.1.6 圖的矩陣表示與同構(gòu)圖G表示的三種方法：9/4

23、/20關(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ù)。舉例說明。9/9/202232Deren Chen, Zhejiang Univ.關(guān)聯(lián)矩陣及其舉例說明關(guān)聯(lián)矩陣：設(shè)G=(V,E)的頂點(diǎn)集和邊集鄰接矩陣及同構(gòu)9/9/202233Deren Chen, Zhejiang Univ.鄰接矩陣及同構(gòu)9/4/202235Deren Chen, Z鄰接矩陣的性質(zhì)(1)主對(duì)角線所有元素都是0圖中無回路;(2)若無環(huán),頂點(diǎn)的度等于M中對(duì)應(yīng)行或列中的1的個(gè)數(shù)。(3) M是對(duì)稱的,所

24、以如果兩行交換位置，那末相應(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的鄰接矩陣。9/9/202234Deren Chen, Zhejiang Univ.鄰接矩陣的性質(zhì)(1)主對(duì)角線所有元素都是0圖中無回路;從定義可以看出，兩個(gè)同構(gòu)圖必然具備下列性質(zhì)：（1）具有相同的頂點(diǎn)數(shù)；（2）具有相同的邊數(shù)；（3）對(duì)于一個(gè)給定的度數(shù)具有相同的頂點(diǎn)數(shù)。反之不成立。舉例說明。同構(gòu)圖的性質(zhì)9/9/202235Deren Chen, Zhejiang Univ.從定義可以看出

25、，兩個(gè)同構(gòu)圖必然具備下列性質(zhì)：同構(gòu)圖的性質(zhì)9/例1 下面兩個(gè)圖不同構(gòu).9/9/202236Deren Chen, Zhejiang Univ.例1 下面兩個(gè)圖不同構(gòu).9/4/202238Deren C例2 證明：圖G和圖H同構(gòu).9/9/202237Deren Chen, Zhejiang Univ.例2 證明：圖G和圖H同構(gòu).9/4/202239Deren同構(gòu)判定算法（用鄰接矩陣）1、根據(jù)圖確定其鄰接矩陣（I)2、計(jì)算行次：矩陣每行的個(gè)數(shù)，（對(duì)應(yīng)于出次） 和列次：（對(duì)應(yīng)于入次）3、不考慮出現(xiàn)的次序不同，若行次與列次不同，則必不同構(gòu)，否則繼續(xù)4、同時(shí)交換其一矩陣的行和行，列和列。 若此矩陣能變成

26、與另一矩陣相同，則同構(gòu)。對(duì)所有頂點(diǎn)的排列都試過，仍不相同，則不同構(gòu)。9/9/202238Deren Chen, Zhejiang Univ.同構(gòu)判定算法（用鄰接矩陣）9/4/202240Deren C性質(zhì)：兩個(gè)圖G與H是同構(gòu)的充要條件是存在一個(gè)置換矩陣P,使得M(G)=PM(H)P.9/9/202239Deren Chen, Zhejiang Univ.性質(zhì)：兩個(gè)圖G與H是同構(gòu)的充要條件是存在一個(gè)置換矩陣P,使得作業(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è)寫在紙上，自己保管好。9/9/202240D

27、eren Chen, Zhejiang Univ.作業(yè)：每人做一題，其中學(xué)號(hào)為1-15號(hào)對(duì)應(yīng)1-15題；9/42 圖的連通性/2.1 途徑、路和圈途徑：中相鄰邊的序列（0,1），（1,2），（k-1,k）稱為一條途徑.此途徑長(zhǎng)度為.也可以（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ù)稱為路的長(zhǎng)度。回路（圈）/Cycle：一條內(nèi)部頂點(diǎn)不重復(fù)出現(xiàn)的閉路稱為圈。長(zhǎng)度為奇數(shù)的圈稱奇圈，否則稱偶圈。9/9/202241Deren Chen, Zh

28、ejiang Univ.2 圖的連通性/2.1 途徑、路和圈途徑：中相鄰邊的序列（ 其他概念頂點(diǎn)間的距離：任意兩點(diǎn)u與v之間的最短路。圖的直徑:指G的兩個(gè)頂點(diǎn)之間的最大距離。完全圖的直徑是？其他特殊圖類呢？練習(xí)。圖的圍長(zhǎng)：圖中最短圈的長(zhǎng)度。圖的周長(zhǎng)：圖中最長(zhǎng)圈的長(zhǎng)度。有向圖的相關(guān)概念可以類似定義。9/9/202242Deren Chen, Zhejiang Univ. 其他概念頂點(diǎn)間的距離：任意兩 相關(guān)定理及其證明9/9/202243Deren Chen, Zhejiang Univ. 相關(guān)定理及其證明9/4/202有向圖中路的應(yīng)用例有A,B,C三個(gè)瓶，分別能裝油8L,5L和3L.如果A裝滿油

29、，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）的一條最短路.9/9/202244Deren Chen, Zhejiang Univ.有向圖中路的應(yīng)用例有A,B,C三個(gè)瓶，分別能裝油8L,5L和容易作出圖G（如下圖）：9/9/202245Deren Chen, Zhejiang Univ.容易

30、作出圖G（如下圖）：9/4/202247Deren Ch通過觀察圖得知共有兩條從（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) (4,0);從而，最快的速度平分即是最短的路所對(duì)應(yīng)的過程，即第一條路的過程就是以最快的速度平分油的過程。能說出具體操作嗎？9/9/202246Deren Chen, Zhejiang Univ.通過觀察圖得知共有兩條從（0，0）到(4,0)的路：能說出具連通/connectivity:設(shè)

31、(,),若存在一條從0，到k的一條道路，則稱0到k連通。無向圖的連通性: 若圖中任兩個(gè)不同頂點(diǎn)都連通，則稱此無向圖是連通的/connected,否則稱為非連通圖(分離圖)。連通分支/connected components：圖可分為幾個(gè)不相連通的子圖，每一子圖本身都是連通的。稱這幾個(gè)子圖為的連通分支。 2.2 連通圖、非連通圖和成分 9/9/202247Deren Chen, Zhejiang Univ.連通/connectivity:設(shè)(,),若存在一條說明：對(duì)無向圖而言，若0到k可達(dá)，則k到0也可達(dá)。對(duì)有向圖而言則未必。有向圖的連通性：(1)弱連通：（，）對(duì)應(yīng)的無向圖是連通圖，則稱為弱連通

32、/weakly connected。(2）強(qiáng)連通：若（，）中任兩點(diǎn)間都有路，即對(duì)與，到可達(dá)，到可達(dá)，稱為強(qiáng)連通/strongly connected。(3)單向連通：如果有向圖D的任何兩個(gè)頂點(diǎn)至少由一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)可達(dá),則稱D是單向連通的。 有向圖的連通性 9/9/202248Deren Chen, Zhejiang Univ.說明：對(duì)無向圖而言，若0到k可達(dá)，則k到0也可達(dá)。對(duì)例：用圖描述一臺(tái)自動(dòng)售貨機(jī)，只用分，分二種硬幣，滿分后壓按鈕，選擇一塊巧克力，錢多了不找還。9/9/202249Deren Chen, Zhejiang Univ.例：用圖描述一臺(tái)自動(dòng)售貨機(jī)，只用分，分二種硬幣，滿

33、 頂點(diǎn):： 分邊： ：投分 ：分 ：投分 ：分 ：壓按扭動(dòng)作 ：分 表示已投入錢的狀態(tài) 表示一種動(dòng)作自動(dòng)售貨機(jī)：有向加權(quán)圖描繪得很清楚（1）錢數(shù)不夠，壓按扭，不起作用（2）錢數(shù)夠了,壓按扭,給過糖果回到分狀態(tài) （3）錢超過分，再加錢白加9/9/202250Deren Chen, Zhejiang Univ. 頂點(diǎn):： 分邊： ：投分 9/一個(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)的圖，

34、得到頂點(diǎn)的最小度，應(yīng)用定理即可證明。9/9/202251Deren Chen, Zhejiang Univ.一個(gè)簡(jiǎn)單定理的應(yīng)用定理2.2.1:設(shè)G是p階簡(jiǎn)單圖,每個(gè)頂點(diǎn)附加定理定理2 如果一個(gè)圖只有兩點(diǎn)的度數(shù)是奇數(shù)，那末這兩點(diǎn)間必有一條通路。9/9/202252Deren Chen, Zhejiang Univ.附加定理定理2 如果一個(gè)圖只有兩點(diǎn)的度數(shù)是奇數(shù)，那末這兩點(diǎn)定理2.2.2：一個(gè)有n個(gè)頂點(diǎn)和k個(gè)成分的簡(jiǎn)單圖最多有(n-k)(n-k+1)/2條邊.9/9/202253Deren Chen, Zhejiang Univ.定理2.2.2：一個(gè)有n個(gè)頂點(diǎn)和k個(gè)成分的簡(jiǎn)單圖最多有(n- 在鄰接

35、矩陣中，若ij，表明i到j(luò)有一條邊，即i到j(luò)可達(dá)；若ij說明i到j(luò)沒有道路.若通過其他點(diǎn)中轉(zhuǎn)，也有可能連通。作鄰接矩陣的普通矩陣乘法：用鄰接矩陣討論連通性9/9/202254Deren Chen, Zhejiang Univ. 在鄰接矩陣中，若ij，表明i到j(luò)有一條邊，即i ij的值表示i到j(luò)長(zhǎng)為的途徑的條數(shù);一般地，就有：m的元素ij表示i到j(luò)長(zhǎng)為的途徑的條數(shù)。定理2.2.3:設(shè)M(G)是G的鄰接矩陣，則G中連接i到j(luò)長(zhǎng)為的途徑的條數(shù)等于m的元素ij，其中m是矩陣A自身作m次乘法得到的矩陣。推論:若G是簡(jiǎn)單圖，則對(duì)每一個(gè)頂點(diǎn)vi,i=1,2,p有dG(vi)=aii(2)，即矩陣A自身作2次

36、乘法得到的矩陣的對(duì)角線元素。9/9/202255Deren Chen, Zhejiang Univ. ij的值表示i到j(luò)長(zhǎng)為的途徑的條數(shù);一般地，鄰接矩陣與連通性定理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è)有向回路中。（了解）9/9/202256Deren Chen, Zhejiang Univ.鄰接矩陣與連通性定理2.2.4:階至少為3的圖G是連通的充要頂點(diǎn)割:若V的子集V使得G-V不連通,則V稱為G的頂點(diǎn)割.k頂點(diǎn)割是指有

37、k個(gè)元素的頂點(diǎn)割. 連通度:若G不是完全圖,則G所有頂點(diǎn)割中的最小的k,稱為G的連通度,記為 ;否則定義 為v-1. 若 ,則稱G為k連通的.2.3 連通度9/9/202257Deren Chen, Zhejiang Univ.頂點(diǎn)割:若V的子集V使得G-V不連通,則V2.3 連通邊割:若E(G)的子集E使得G-E不連通,則E稱為G的邊割.K邊割是指有k個(gè)元素的邊割.邊連通度 :G的所有k邊割中最小的k. 若G是平凡的,則 定義為0. 若 ,則稱G為k邊連通的.邊連通度9/9/202258Deren Chen, Zhejiang Univ.邊割:若E(G)的子集E使得G-E不連通,則E稱為G的

38、連通度和邊連通度的等價(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是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ǔ)集 。9/9/202259Deren Chen, Zhejiang Univ.連通度和邊連通度的等價(jià)定義（更實(shí)用）等價(jià)定義1：圖G是k連通幾者之間的聯(lián)系9/9/202260Deren Chen, Zhejiang Univ.幾者之間的聯(lián)系9

39、/4/202262Deren Chen, Z幾者之間的聯(lián)系定理2.3.1: 對(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í))9/9/202261Deren Chen, Zhejiang Univ.幾者之間的聯(lián)系定理2.3.1: 對(duì)任意簡(jiǎn)單圖，有9/4/20幾個(gè)重要定理G中一族路稱為內(nèi)部不相交的:如果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)而長(zhǎng)為2的路.9/9/202262Deren Chen, Zhejiang Univ.幾個(gè)重要定理G中一族路稱為內(nèi)部不相