圖論及其應(yīng)用ch1-2

主講：張麗麗圖論及其應(yīng)用E-mail:lilzhang@2/7/20231DerenChen,ZhejiangUniv.兩個有趣的問題1.任意一群人中（人數(shù)不小于2），總有兩人在該人群中認(rèn)識相同的朋友數(shù)。2.在一次象棋比賽中，任意兩名選手間至多下一盤，試證總存在兩名選手，他們下過的盤數(shù)相同。問題1：如何用學(xué)過的知識解答上述問題？問題2：上述問題的解答是否相同？若不同，區(qū)別在哪？2/7/20232DerenChen,ZhejiangUniv.Keyweb/AMuseum/math/index.htm中國數(shù)字科技館，數(shù)學(xué)，信息科學(xué)等2/7/20233DerenChen,ZhejiangUniv.1圖的基本概念/1.1圖論發(fā)展史

圖論是組合數(shù)學(xué)的一個分支，也是近幾十年來最活躍的數(shù)學(xué)分支之一.到目前為止，它已有二百六十多年的發(fā)展歷史.圖論的發(fā)展歷史大體可以分為三個階段：第一階段是圖論的萌芽階段，它從十八世紀(jì)中葉到十九世紀(jì)中葉.這時(shí)，圖論的多數(shù)問題是圍繞游戲而產(chǎn)生的，其代表性的工作就是K?nigsberg七橋問題.1736年L.Euler發(fā)表了他著名的K?nigsberg七橋問題的論文，這是圖論的第一篇文章.2/7/20234DerenChen,ZhejiangUniv.第二階段從十九世紀(jì)中葉到二十世紀(jì)中葉.在此階段，圖論問題大量出現(xiàn).如著名的四色問題、Hamilton問題以及圖的可平面問題等.在第二個階段還應(yīng)該特別提到Cayley把樹應(yīng)用于化學(xué)領(lǐng)域，Kirchhoff用樹去研究電網(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)典著作<<有限圖與無限圖理論>>才有了圖論的第一本專著.

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

K?nigsberg七橋背后的故事K?nigsberg七橋位于前蘇聯(lián)的加里寧格勒，歷史上曾是德國東普魯士省的省會，霹雷格爾橫穿城堡，河中有兩個小島B與C，并有七座橋連接島與河岸及島與島（見圖）。是否存在一種走發(fā)，從四塊陸地中的任意一塊開始，通過每一座橋恰好一次再回到起點(diǎn)。這就是著名的K?nigsberg七橋問題，即一筆畫問題；也是圖論的起源。2/7/20237DerenChen,ZhejiangUniv.2/7/20238DerenChen,ZhejiangUniv.四色問題為了能夠迅速地區(qū)分一個平面地圖或球面地圖上的各個國家（假設(shè)這些國家在地圖上都是連通的），需要用若干種顏色對這些國家著色，使得具有公共邊界的兩個國家涂染不同的顏色.那么，要保證每張地圖都能如此著色，最少需要多少種顏色？這個問題是1850年被一名剛畢業(yè)的大學(xué)生FrancisGuthrie首先提出的，直到1976年，四色問題被美國Illinois大學(xué)的K.Appel和W.Haken用計(jì)算機(jī)證明是正確的，這個證明令數(shù)學(xué)界震驚，它用了1200多小時(shí)，作出100億個獨(dú)立的邏輯判斷.盡管有了這個機(jī)器證明，但它仍然是數(shù)學(xué)上未解決的問題之一.2/7/20239DerenChen,ZhejiangUniv.Hamilton問題Hamilton問題是圖論中一直懸而未解的一大問題。它起源于1856年，當(dāng)時(shí)英國數(shù)學(xué)家Hamilton設(shè)計(jì)了一種名為周游世界的游戲。他在一個實(shí)心的正十二面體的十二個頂點(diǎn)上標(biāo)以世界上著名的二十座城市的名字，要求游戲者沿十二面體的棱從一個城市出發(fā)，經(jīng)過每座城市恰好一次，然后返回到出發(fā)點(diǎn)，即“繞行世界”。正十二面體的頂點(diǎn)與棱的關(guān)系可以用平面上的圖表示，把正十二面體的頂點(diǎn)與棱分別對應(yīng)圖的頂點(diǎn)與邊，就得到正十二面體圖。2/7/202310DerenChen,ZhejiangUniv.正十二面體Peterson圖2/7/202311DerenChen,ZhejiangUniv.旅行售貨員問題給出城市之間的距離，要求一位推銷員從某一城市出發(fā)，周游每個城市一次，然后回到出發(fā)的城市，并且選的路徑最短。這是一個圖論優(yōu)化問題，最早由美國數(shù)學(xué)家威特涅于1934年在普林斯頓一次討論班上提出。1954年幾位美國數(shù)學(xué)家寫了第一篇論文，用線性方程的方法解決了49個城市的旅行售貨員問題。后來也有不少論文討論這個問題，在理論和應(yīng)用上都很有價(jià)值。2/7/202312DerenChen,ZhejiangUniv.生活中，人們常常需要考慮一些對象之間的某種特定的關(guān)系.如某區(qū)域內(nèi)，兩城市之間有無交通線；一群人中，兩個人之間相識或不相識等等.這種關(guān)系是對稱的，即如果甲對于乙有某種關(guān)系，則乙對于甲也有這種關(guān)系.可以用一個圖形來描述給定對象之間的某個關(guān)系：我們用平面上的點(diǎn)分別表示這些對象，若對象甲和乙有關(guān)系，就用一條線連接表示甲和乙的兩個點(diǎn).這種由一些點(diǎn)與連接其中某些點(diǎn)對的線所構(gòu)成的圖形就是圖論中所研究的圖.圖/Graph：可直觀地表示離散對象之間的相互關(guān)系，研究它們的共性和特性，以便解決具體問題。1.2圖的定義2/7/202313DerenChen,ZhejiangUniv.無向圖（簡稱圖）:一個圖是指一個有序三元組(V(G),E(G),),其中V(G)是一個非空有限集，Ｅ(G)是與Ｖ(G)不相交的有限集合,是關(guān)聯(lián)函數(shù)，它使E(G)中每一元素對應(yīng)于V(G)中的無序元素對（可以相同）幾個重要定義有A(D)有實(shí)際上,有向圖即將無向圖中的無序?qū)闯捎行驅(qū)?其中有向圖對應(yīng)的無向圖稱為有向圖的基礎(chǔ)圖。其中V(G)稱為頂點(diǎn)集,E(G)稱為邊集（A(D)又稱為弧集）.令p(G)=|V(G)|,q(G)=|E(G)|,分別稱為圖的階和邊數(shù)。舉例說明。A(D)A(D)有向2/7/202314DerenChen,ZhejiangUniv.如果一個圖的頂點(diǎn)集和邊集都是有限集則稱該圖為有限圖,否則稱為無限圖.只有一個頂點(diǎn)所構(gòu)成的圖稱為平凡圖,其它的稱為非平凡圖.如果一個圖中沒有環(huán)也沒有重邊稱為簡單圖。2/7/202315DerenChen,ZhejiangUniv.圖/graph;有向圖/directedgraph;相鄰/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)/initialvertex，b稱為e的終點(diǎn)/terminalorendvertex。2/7/202316DerenChen,ZhejiangUniv.1.嚴(yán)格有向圖：既無自回路又無平行邊的有向圖。2.非對稱有向圖：在兩點(diǎn)間最多有一條有向邊，但允許有自回路的有向圖。3.對稱有向圖：對于圖中每一邊(a,b),總存在另一邊(b,a)的有向圖。4.完全有向圖:(1)完全對稱有向圖：一個從任一點(diǎn)到其他點(diǎn)有一條且僅有一條有向邊的簡單圖；(2)完全非對稱有向圖：任何兩點(diǎn)有一條且只有一條有向邊的非對稱圖。有向圖的種類：2/7/202317DerenChen,ZhejiangUniv.有向圖在成對比較中的應(yīng)用

在很多實(shí)驗(yàn)中，特別在社會科學(xué)領(lǐng)域，要求人們通過對事物的兩兩比較排出它們的名次。這種方法稱為成對比較法。例如，測定對音樂作品的個人愛好時(shí)，每一次對一個主題取出兩個作品，問一個人他喜歡哪一個。記錄了n個作品成對比較所有n(n-1)/2種可能的結(jié)果后，實(shí)驗(yàn)者就能根據(jù)某人的愛好排出n個作品的品次。Kendall在1948年做的一個分類實(shí)驗(yàn)時(shí)，對六種不同的狗食排名次。每天在六種食品中任選兩種喂狗。實(shí)驗(yàn)安排了15天，所有可能配對的食物都被試過，在圖中，一條邊是從喜歡的食物引向比較不喜歡的食物，這樣的圖稱為優(yōu)化圖。2/7/202318DerenChen,ZhejiangUniv.

有向圖在競賽中的應(yīng)用在單循環(huán)賽中，每個運(yùn)動員和所有其他運(yùn)動員比賽，比賽結(jié)果可以用有向圖表示。圖中一條頂點(diǎn)a指向b的邊表示運(yùn)動員a勝過運(yùn)動員b。所以完全非對稱圖又稱為競賽圖。按得分排名次：根據(jù)運(yùn)動員得分排名次，得分是運(yùn)動員在比賽中勝的局?jǐn)?shù)，反映在有向圖中是點(diǎn)的出度。2/7/202319DerenChen,ZhejiangUniv.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),2/7/202320DerenChen,ZhejiangUniv.定理1.3.1(Handshaking)設(shè)無向圖G=（V，E）有e條邊，則G中所有頂點(diǎn)的度之和等于e的兩倍。證明思路：考慮每條邊在求和中的貢獻(xiàn)。定理1.3.2無向圖中度為奇數(shù)的頂點(diǎn)個數(shù)恰有偶數(shù)個。證明思路：將圖中頂點(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記住了嗎？幾個重要定理2/7/202321DerenChen,ZhejiangUniv.推論2/7/202322DerenChen,ZhejiangUniv.例1證明任何一群人中，有偶數(shù)個人認(rèn)識其中奇數(shù)個人.(匈牙利數(shù)學(xué)競賽試題)[證]用n個頂點(diǎn)表示n個人.如果兩個人相識，就用一條線把他們對應(yīng)的一對頂點(diǎn)連起來，這樣就得到了一個圖G.每一個人所認(rèn)識的人的數(shù)目就是他對應(yīng)的頂點(diǎn)的次，于是問題就轉(zhuǎn)化為證明圖G中奇點(diǎn)的個數(shù)為偶數(shù)，而這正是定理1.3.2的結(jié)論.2/7/202323DerenChen,ZhejiangUniv.例2設(shè)是平面上n個點(diǎn)，其中任意兩點(diǎn)的距離至少是1，證明至多有3n對點(diǎn)，每對點(diǎn)的距離恰好是1.[證]以這n個點(diǎn)為頂點(diǎn)作圖G，使得與相鄰當(dāng)且僅當(dāng)與的距離恰好是.于是，距離恰為1的點(diǎn)對的數(shù)目就是G的邊數(shù)q.顯然，在G中的鄰點(diǎn)一定在以為圓心，以1為半徑的圓周上.由于任一對點(diǎn)的距離至少是1,于是，所以即.結(jié)論成立例22/7/202324DerenChen,ZhejiangUniv.例3在一次圍棋擂臺賽中，雙方各出n名選手。比賽的規(guī)則是雙方先各自排定一個次序，設(shè)甲方排定的次序?yàn)橐曳脚哦ǖ拇涡驗(yàn)?/7/202325DerenChen,ZhejiangUniv.1.4子圖與圖的運(yùn)算子圖：Ｇ＝(Ｖ,E)是圖,若Ｇ’=(Ｖ’,Ε’)也是圖且滿足:(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ū)別。2/7/202326DerenChen,ZhejiangUniv.相對補(bǔ)圖/complementarygraph：Ｇ＝（Ｖ，Ｅ）是圖，Ｇ’＝（Ｖ’，Ε’）是Ｇ的子圖，Ｅ”＝Ｅ－Ｅ’，Ｖ”＝V－V’或是Ｅ”中邊所關(guān)聯(lián)的所有頂點(diǎn)集合，則Ｇ”＝（Ｖ”，Ｅ”）稱為Ｇ’關(guān)于Ｇ的相對補(bǔ)圖。補(bǔ)圖：關(guān)于完全圖的子圖的補(bǔ)圖稱為此子圖的絕對補(bǔ)圖，若子圖記為Ｇ，則補(bǔ)圖記為。2/7/202327DerenChen,ZhejiangUniv.圖的運(yùn)算圖的并/union：Ｇ＝（Ｖ，Ｅ）和Ｇ’＝（Ｖ’，Ε’）是兩個簡單無向圖，它們的并圖ＧＧ’定義為ＧＧ’=（Ｖ’Ｖ，Ｅ’Ｅ）.圖的和：Ｇ＝（Ｖ，Ｅ）和Ｇ’＝（Ｖ’，Ε’）是兩個不相交的簡單無向圖，稱Ｇ+Ｇ’為G和G’的和，其中Ｇ+Ｇ’=（Ｖ’Ｖ，Ｅ’ＥＥ’’).圖的交：Ｇ＝（Ｖ，Ｅ）和Ｇ’＝（Ｖ’，Ε’）是兩個簡單無向圖，稱ＧＧ’為G和G’的交，其中ＧＧ’=（Ｖ’Ｖ，Ｅ’Ｅ).舉例說明。2/7/202328DerenChen,ZhejiangUniv.1.5特殊圖類完全圖/completegraph：圖G中的每對不同頂點(diǎn)之間恰有一條邊?？請D/emptygraph：邊集為空的圖。問題：完全圖的補(bǔ)圖是怎樣的圖？設(shè)G=(V,E)是p階圖,若V可以劃分為m個非空2/7/202329DerenChen,ZhejiangUniv.補(bǔ)充特殊圖類練習(xí)：畫出一個完全二部圖/bipartitegraph。輪圖/wheel:由一個圈添加一個新頂點(diǎn),并且把這個頂點(diǎn)與圈的所有頂點(diǎn)相連得到的圖稱為輪，新的邊稱為輻。正則圖：每個頂點(diǎn)的度都等于k的圖。線圖（邊圖）/linegraph：圖G的線圖是以為E(G)頂點(diǎn)集的圖,其中兩個頂點(diǎn)相鄰當(dāng)且僅當(dāng)它們在G中是相鄰的邊。練習(xí):各類特殊圖所含邊數(shù)的情況如何？2/7/202330DerenChen,ZhejiangUniv.1.6圖的矩陣表示與同構(gòu)圖G表示的三種方法：（1）集合表示（2）鄰接表（adjacencylist）表示（3）矩陣（matrix）表示1、鄰接矩陣（adjacencymatrix）表示2、關(guān)聯(lián)矩陣（incidencematrix）表示2/7/202331DerenChen,ZhejiangUniv.關(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)的每一行元素之和等于對應(yīng)頂點(diǎn)的度數(shù)。舉例說明。2/7/202332DerenChen,ZhejiangUniv.鄰接矩陣及同構(gòu)2/7/202333DerenChen,ZhejiangUniv.鄰接矩陣的性質(zhì)(1)主對角線所有元素都是0<=>圖中無回路;(2)若無環(huán),頂點(diǎn)的度等于M中對應(yīng)行或列中的1的個數(shù)。(3)M是對稱的,所以如果兩行交換位置，那末相應(yīng)的列也應(yīng)交換位置。(4)圖G是分離圖,且有兩個分支G1和G2<=>它的鄰接矩陣能劃分成分塊對角矩陣。(5)給出任何一個n階對稱（0，1）方陣Q,總能構(gòu)造一個具有n個頂點(diǎn)的圖G，使得Q是G的鄰接矩陣。2/7/202334DerenChen,ZhejiangUniv.從定義可以看出，兩個同構(gòu)圖必然具備下列性質(zhì)：（1）具有相同的頂點(diǎn)數(shù)；（2）具有相同的邊數(shù)；（3）對于一個給定的度數(shù)具有相同的頂點(diǎn)數(shù)。反之不成立。舉例說明。同構(gòu)圖的性質(zhì)2/7/202335DerenChen,ZhejiangUniv.例1下面兩個圖不同構(gòu).2/7/202336DerenChen,ZhejiangUniv.例2證明：圖G和圖H同構(gòu).2/7/202337DerenChen,ZhejiangUniv.同構(gòu)判定算法（用鄰接矩陣）1、根據(jù)圖確定其鄰接矩陣（I)2、計(jì)算行次：矩陣每行１的個數(shù)，（對應(yīng)于出次）和列次：（對應(yīng)于入次）3、不考慮出現(xiàn)的次序不同，若行次與列次不同，則必不同構(gòu)，否則繼續(xù)4、同時(shí)交換其一矩陣的ｉ行和ｊ行，ｉ列和ｊ列。若此矩陣能變成與另一矩陣相同，則同構(gòu)。對所有頂點(diǎn)的排列都試過，仍不相同，則不同構(gòu)。2/7/202338DerenChen,ZhejiangUniv.性質(zhì)：兩個圖G與H是同構(gòu)的充要條件是存在一個置換矩陣P,使得M(G)=P'M(H)P.2/7/202339DerenChen,ZhejiangUniv.作業(yè)：每人做一題，其中學(xué)號為1-15號對應(yīng)1-15題；其它學(xué)號的同學(xué)按照學(xué)號最后一位數(shù)字與題目最后一位數(shù)字對應(yīng)。注意：下次上課全部上交，作業(yè)寫在紙上，自己保管好。2/7/202340DerenChen,ZhejiangUniv.2圖的連通性/2.1途徑、路和圈途徑：Ｇ中相鄰邊的序列（Ｖ0,Ｖ1），（Ｖ1,Ｖ2），…（Ｖ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ù)的圈稱奇圈，否則稱偶圈。2/7/202341DerenChen,ZhejiangUniv.其他概念頂點(diǎn)間的距離：任意兩點(diǎn)u與v之間的最短路。圖的直徑:指G的兩個頂點(diǎn)之間的最大距離。完全圖的直徑是？其他特殊圖類呢？練習(xí)。圖的圍長：圖中最短圈的長度。圖的周長：圖中最長圈的長度。有向圖的相關(guān)概念可以類似定義。2/7/202342DerenChen,ZhejiangUniv.相關(guān)定理及其證明2/7/202343DerenChen,ZhejiangUniv.有向圖中路的應(yīng)用例有A,B,C三個瓶，分別能裝油8L,5L和3L.如果A裝滿油，B和C是空的，怎樣以最快的速度平分A中的油？[解法]我們用三位數(shù)碼表示A,B,C三個瓶子裝油的情況，又因?yàn)槿粩?shù)碼之和不變，所以可以用后兩位數(shù)碼表示三個瓶子裝油的情況.例如：（0，0）表示初始狀態(tài).根據(jù)題意：共有十六種可能的狀態(tài)，用這16個狀態(tài)為頂點(diǎn)作圖G，使得兩個狀態(tài)相鄰當(dāng)且僅當(dāng)它們可以經(jīng)過一次倒油相互轉(zhuǎn)化.于是，問題就是要求從（0，0）到（4，0）的一條最短路.2/7/202344DerenChen,ZhejiangUniv.容易作出圖G（如下圖）：2/7/202345DerenChen,ZhejiangUniv.通過觀察圖得知共有兩條從（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);從而，最快的速度平分即是最短的路所對應(yīng)的過程，即第一條路的過程就是以最快的速度平分油的過程。能說出具體操作嗎？2/7/202346DerenChen,ZhejiangUniv.連通/connectivity:設(shè)Ｇ＝(Ｖ,Ｅ),若存在一條從Ｖ0，到Ｖk的一條道路，則稱Ｖ0到Ｖk連通。無向圖的連通性:若圖Ｇ中任兩個不同頂點(diǎn)都連通，則稱此無向圖是連通的/connected,否則稱為非連通圖(分離圖)。連通分支/connectedcomponents：圖Ｇ可分為幾個不相連通的子圖，每一子圖本身都是連通的。稱這幾個子圖為Ｇ的連通分支。

2.2連通圖、非連通圖和成分

2/7/202347DerenChen,ZhejiangUniv.說明：對無向圖而言，若Ｖ0到Ｖk可達(dá)，則Ｖk到Ｖ0也可達(dá)。對有向圖而言則未必。有向圖的連通性：(1)弱連通：Ｇ＝（Ｖ，Ｅ）對應(yīng)的無向圖是連通圖，則稱Ｇ為弱連通/weaklyconnected。(2）強(qiáng)連通：若Ｇ＝（Ｖ，Ｅ）中任兩點(diǎn)間都有路，即對ａ與ｂ，ａ到ｂ可達(dá)，ｂ到ａ可達(dá)，稱Ｇ為強(qiáng)連通/stronglyconnected。(3)單向連通：如果有向圖D的任何兩個頂點(diǎn)至少由一個頂點(diǎn)到另一個頂點(diǎn)可達(dá),則稱D是單向連通的。

有向圖的連通性

2/7/202348DerenChen,ZhejiangUniv.例：用圖描述一臺自動售貨機(jī)，只用５分，１０分二種硬幣，滿１５分后壓按鈕，選擇一塊巧克力，錢多了不找還。2/7/202349DerenChen,ZhejiangUniv.

頂點(diǎn):ａ：０分邊：５：投５分ｂ：５分１０：投１０分ｃ：１０分ｐ：壓按扭動作ｄ：≥１５分表示已投入錢的狀態(tài)表示一種動作自動售貨機(jī)：有向加權(quán)圖描繪得很清楚（1）錢數(shù)不夠，壓按扭，不起作用（2）錢數(shù)夠了,壓按扭,給過糖果回到０分狀態(tài)（3）錢超過１５分，再加錢白加2/7/202350DerenChen,ZhejiangUniv.一個簡單定理的應(yīng)用定理2.2.1:設(shè)G是p階簡單圖,每個頂點(diǎn)的度至少是[p/2],則G是連通圖。例1:用一些圓面覆蓋平面上取定的2n個點(diǎn)。試證：若每個圓面至少覆蓋n+1個點(diǎn)則任兩個點(diǎn)能由平面上的一條折線所連接，而這條折線整個地被某些圓面覆蓋。證明：構(gòu)造相應(yīng)的圖，得到頂點(diǎn)的最小度，應(yīng)用定理即可證明。2/7/202351DerenChen,ZhejiangUniv.附加定理定理2如果一個圖只有兩點(diǎn)的度數(shù)是奇數(shù)，那末這兩點(diǎn)間必有一條通路。2/7/202352DerenChen,ZhejiangUniv.定理2.2.2：一個有n個頂點(diǎn)和k個成分的簡單圖最多有(n-k)(n-k+1)/2條邊.2/7/202353DerenChen,ZhejiangUniv.

在鄰接矩陣中，若ａij＝１，表明Ｖi到Ｖj有一條邊，即Ｖi到Ｖj可達(dá)；若ａij＝０說明Ｖi到Ｖj沒有道路.若通過其他點(diǎn)中轉(zhuǎn)，也有可能連通。作鄰接矩陣的普通矩陣乘法：用鄰接矩陣討論連通性2/7/202354DerenChen,ZhejiangUniv.

ｂ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是簡單圖，則對每一個頂點(diǎn)vi,i=1,2,…,p有dG(vi)=aii(2)，即矩陣A自身作2次乘法得到的矩陣的對角線元素。2/7/202355DerenChen,ZhejiangUniv.鄰接矩陣與連通性定理2.2.4:階至少為3的圖G是連通的充要條件為R(G)中的每個元素都不等于零，其中R(G)=M(G)+M2(G)+…+Mp-1(G)。定理2.2.5：設(shè)D是連通的有向圖，則D是強(qiáng)連通的當(dāng)且僅當(dāng)D的每條弧都含在一個有向回路中。（了解）2/7/202356DerenChen,ZhejiangUniv.頂點(diǎn)割:若V的子集V’使得G-V’不連通,則V’稱為G的頂點(diǎn)割.k頂點(diǎn)割是指有k個元素的頂點(diǎn)割.

連通度:若G不是完全圖,則G所有頂點(diǎn)割中的最小的k,稱為G的連通度,記為;否則定義為v-1.若 ,則稱G為k連通的.2.3連通度2/7/202357DerenChen,ZhejiangUniv.邊割:若E(G)的子集E’使得G-E’不連通,則E’稱為G的邊割.K邊割是指有k個元素的邊割.邊連通度:G的所有k邊割中最小的k.若G是平凡的,則定義為0.若 ,則稱G為k邊連通的.邊連通度2/7/202358DerenChen,ZhejiangUniv.連通度和邊連通度的等價(jià)定義（更實(shí)用）等價(jià)定義1：圖G是k連通的當(dāng)且僅當(dāng)對任意一個點(diǎn)數(shù)不超過k-1的頂點(diǎn)子集V'，G-V'仍然連通。等價(jià)定義2.1：圖G是k邊連通的當(dāng)且僅當(dāng)對任意一個邊數(shù)不超過k-1的邊子集E'，G-E'仍然連通。等價(jià)定義2.2：圖G是k邊連通的當(dāng)且僅當(dāng)對任一非空真子集S,均有|[S,?]|≥k，其中[S,?]表示一個頂點(diǎn)在S中一個頂點(diǎn)在?中的所有邊集,?是S的補(bǔ)集。2/7/202359DerenChen,ZhejiangUniv.幾者之間的聯(lián)系2/7/202360DerenChen,ZhejiangUniv.幾者之間的聯(lián)系定理2.3.1:對任意簡單圖，有（定理證明無需掌握,要記熟三者之間的關(guān)系）問題：怎樣的圖可以取到等號呢？設(shè)G是p階簡單連通圖，若對于G的任意四個頂點(diǎn)u,v,x,y,若|[{u,v},{x,y}]|=0就有d(u)+d(v)+d(x)+d(y)≥2p-3,則事實(shí)上，還有很多圖類滿足第一個不等式中的等號關(guān)系，你能自己找到嗎？(課后自己練習(xí))2/7/202361DerenChen,ZhejiangUniv.幾個重要定理G中一族路稱為內(nèi)部不相交的:如果G中任意兩條路除起點(diǎn)和終點(diǎn)外沒有公共頂點(diǎn)。定理2.3.2

一個階不小于3的圖是2連通的,當(dāng)且僅當(dāng)G的任意兩個頂點(diǎn)至少被兩條內(nèi)部不相交的路所連.推論1若G是2連通圖