第6章圖的基本概念

運(yùn)籌帷幄之中決勝千里之外圖與網(wǎng)絡(luò)分析GraphTheoryandNetworkAnalysis第六章圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的基本知識(shí)中國(guó)郵路問(wèn)題最短路問(wèn)題最大流問(wèn)題本章主要內(nèi)容：圖的基本知識(shí)圖論起源——哥尼斯堡七橋問(wèn)題問(wèn)題：一個(gè)散步者能否從任一塊陸地出發(fā)，走過(guò)七座橋，且每座橋只走過(guò)一次，最后回到出發(fā)點(diǎn)？結(jié)論：不能。每個(gè)結(jié)點(diǎn)關(guān)聯(lián)的邊數(shù)要均為偶數(shù)。BDACABCD一筆畫問(wèn)題圖的基本知識(shí)環(huán)球旅行問(wèn)題：圖的基本知識(shí)環(huán)球旅行問(wèn)題的解另一個(gè)著名的問(wèn)題:中國(guó)郵路問(wèn)題圖論中圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。一般情況下圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長(zhǎng)短曲直，對(duì)于反映對(duì)象之間的關(guān)系并不是重要的。圖的定義： 若用點(diǎn)表示研究的對(duì)象，用邊表示這些對(duì)象之間的聯(lián)系，則圖G可以定義為點(diǎn)(頂點(diǎn))和邊的集合，記作：其中:V——點(diǎn)集E——邊集※

圖G區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個(gè)點(diǎn)以及哪些點(diǎn)之間有連線。圖的基本知識(shí)(v1)趙(v2)錢孫(v3)李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5可見圖論中的圖與幾何圖、工程圖是不一樣的。例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來(lái)表示。圖的基本知識(shí)定義:圖中的點(diǎn)用v表示，邊用e表示。對(duì)每條邊可用它所連接的點(diǎn)表示，記作：e1=[v1,v1];e2=[v1,v2];v3e7e4e8e5e6e1e2e3v1v2v4v5

端點(diǎn),關(guān)聯(lián)邊,相鄰若有邊e可表示為e=[vi,vj]，稱vi和vj是邊e的端點(diǎn)，反之稱邊e為點(diǎn)vi或vj的關(guān)聯(lián)邊。若點(diǎn)vi、vj與同一條邊關(guān)聯(lián)，稱點(diǎn)vi和vj相鄰；若邊ei和ej具有公共的端點(diǎn)，稱邊ei和ej相鄰。V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6,e7,e8}，圖的基本知識(shí)邊數(shù)：m(G)=|E|=m頂點(diǎn)數(shù)：n(G)=|V|=n無(wú)向邊與無(wú)向圖：若圖中任一條邊的端點(diǎn)無(wú)序，即(vi,vj)與(vj,vi)是同一條邊，則稱它為無(wú)向邊，此時(shí)圖稱為無(wú)向圖。有向圖：若圖中邊(vi,vj)的端點(diǎn)是有序的，則稱它是有向邊（或?。?，vi與vj分別稱為這條有向邊的始點(diǎn)和終點(diǎn)，相應(yīng)的圖稱為有向圖。有向圖無(wú)向圖圖的基本知識(shí)無(wú)向圖,有向圖

環(huán),多重邊,簡(jiǎn)單圖如果邊e的兩個(gè)端點(diǎn)相重，稱該邊為環(huán)。如右圖中邊e1為環(huán)。如果兩個(gè)點(diǎn)之間多于一條，稱為多重邊，如右圖中的e4和e5，對(duì)無(wú)環(huán)、無(wú)多重邊的圖稱作簡(jiǎn)單圖。含多重邊的圖稱為多重圖。v3e7e4e8e5e6e1e2e3v1v2v4v5簡(jiǎn)單圖多重圖圖的基本知識(shí)環(huán)多重邊

完全圖圖的基本知識(shí)每一對(duì)頂點(diǎn)間都有邊相連的無(wú)向簡(jiǎn)單圖稱為無(wú)向完全圖；有向完全圖是指每一對(duì)頂點(diǎn)間有且僅有一條有向邊的簡(jiǎn)單圖。完全圖頂點(diǎn)數(shù)n與邊數(shù)m間成立如下關(guān)系:m=n(n-1)/2

二部圖（偶圖）圖G=(V,E)的點(diǎn)集V可以分為兩各非空子集X，Y，集X∪Y=V,X∩Y=?,使得同一集合中任意兩個(gè)頂點(diǎn)均不相鄰，稱這樣的圖為二部圖（偶圖）。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明顯為二部圖，(b)也是二部圖，但不明顯，改畫為(c)時(shí)可以清楚看出。圖的基本知識(shí)

度，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn)與某一個(gè)點(diǎn)vi相關(guān)聯(lián)的邊的數(shù)目稱為點(diǎn)vi的度（也叫做次），記作d(vi)。右圖中d(v1)=4,d(v3)=5,d(v5)=1。度數(shù)為奇數(shù)的點(diǎn)稱作奇點(diǎn)，度數(shù)為偶數(shù)的點(diǎn)稱作偶點(diǎn)，度數(shù)為1的點(diǎn)稱為懸掛點(diǎn)，度數(shù)為0的點(diǎn)稱作孤立點(diǎn)。v3e7e4e8e5e6e1e2e3v1v2v4v5圖的度:

一個(gè)圖的度等于各點(diǎn)的度數(shù)之和，且圖的基本知識(shí)圖的基本知識(shí)v2v1v5v3v4e2e1e3e4e5e6d(v1)=4d(v2)=3懸掛點(diǎn)孤立點(diǎn)懸掛邊偶點(diǎn)奇點(diǎn)圖的基本知識(shí)圖中頂點(diǎn)度的性質(zhì)定理1任何圖中頂點(diǎn)度數(shù)的總和等于邊數(shù)的2倍，即定理2任何圖中度數(shù)為奇數(shù)的頂點(diǎn)必有偶數(shù)個(gè)。定義

在有向圖中，以頂點(diǎn)v為始點(diǎn)的邊數(shù)稱為頂點(diǎn)v的出度，記為d+(v)；以v為終點(diǎn)的邊數(shù)稱為v的入度，記為

d-(v)。頂點(diǎn)v的出度與入度的和稱為點(diǎn)v的度。

子圖，生成子圖(支撐子圖)v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（圖G）圖的基本知識(shí)定義

圖G=(V,E),若E'是E的子集，若V'是V的子集，且E'中的邊僅與V'中的頂點(diǎn)相關(guān)聯(lián)，則稱G'=(V',E')為圖G的一個(gè)子圖，特別地，若V'=V,則稱G'為G的一個(gè)生成子圖（支撐子圖）。

網(wǎng)絡(luò)（賦權(quán)圖）設(shè)圖G＝（V，E），對(duì)G的每一條邊(vi,vj)相應(yīng)賦予數(shù)量指標(biāo)wij，wij稱為邊(vi,vj)的權(quán)，賦予權(quán)的圖G稱為網(wǎng)絡(luò)(或賦權(quán)圖）。權(quán)可以代表距離、費(fèi)用、通過(guò)能力(容量)等等。端點(diǎn)無(wú)序的賦權(quán)圖稱為無(wú)向網(wǎng)絡(luò)，端點(diǎn)有序的賦權(quán)圖稱為有向網(wǎng)絡(luò)。①②③④⑤⑥910201571419256圖的基本知識(shí)

路徑，圈，連通圖定義

無(wú)向圖中一個(gè)點(diǎn)、邊交錯(cuò)的序列，序列中的第一個(gè)和最后一個(gè)元素都是點(diǎn)，若其中每條邊以序列中位于它之前和之后的點(diǎn)為端點(diǎn)，則稱這個(gè)點(diǎn)邊序列為圖中連接其第一個(gè)點(diǎn)與最后一個(gè)點(diǎn)的鏈（途徑）。鏈中所含的邊數(shù)稱為鏈長(zhǎng)。圖的基本知識(shí)鏈，但只是跡而非路跡：沒(méi)有重復(fù)邊；路徑：既無(wú)重復(fù)邊也無(wú)重復(fù)點(diǎn)。對(duì)有向圖可類似定義鏈（各邊方向一致）。路徑，圈，連通圖定義

若在無(wú)向圖中，一條鏈的第一個(gè)點(diǎn)與最后一個(gè)點(diǎn)重合，則稱這條鏈為閉鏈。只有重復(fù)點(diǎn)而無(wú)重復(fù)邊的閉鏈為閉跡（或回路），既無(wú)重復(fù)點(diǎn)又無(wú)重復(fù)邊的閉鏈為圈。圖的基本知識(shí)圈閉鏈圖的基本知識(shí)鏈（途徑,walk）閉鏈跡（trail）閉跡（回路）路徑（path）圈有向圖：道路(邊的方向一致)

連通圖圖的基本知識(shí)定義

一個(gè)圖中任意兩點(diǎn)間至少有一條鏈相連（或等價(jià)的說(shuō)有一條路相連），則稱此圖為連通圖。任何一個(gè)不連通圖總可以分為若干個(gè)連通子圖，每個(gè)連通子圖稱為原圖的一個(gè)分圖（連通分支）。連通圖非連通圖圖的基本知識(shí)圖的矩陣表示：如何在計(jì)算機(jī)中存儲(chǔ)一個(gè)圖呢？現(xiàn)在已有很多存儲(chǔ)的方法，但最基本的方法就是采用矩陣來(lái)表示一個(gè)圖，圖的矩陣表示也根據(jù)所關(guān)心的問(wèn)題不同而有：鄰接矩陣、關(guān)聯(lián)矩陣、權(quán)矩陣等。1.鄰接矩陣 對(duì)于圖G=（V，E），|V|=n，|E|=m，有nn階方矩陣A=(aij)nn，其中圖的基本知識(shí)v5v1v2v3v4v64332256437例6.1下圖所表示的圖可以構(gòu)造鄰接矩陣A如下對(duì)于賦權(quán)圖G=(V,E)，其中邊有權(quán),構(gòu)造矩陣B=(bij)nn

其中：圖的基本知識(shí)2.關(guān)聯(lián)矩陣對(duì)于圖G=(V,E),|V|=n,|E|=m,有nm矩陣M=(mij)nm，其中:3.權(quán)矩陣圖的基本知識(shí)101000000000110010000000010001110000000000001001001111000000000000001100000000000111000100110000v1v2v3v4v5v6v7v8e1e2e3e4e5e6e7e8e9e10e11e12v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4例6.2下圖所表示的圖可以構(gòu)造鄰接矩陣M如下:M=（mij）=圖的基本知識(shí)v5v1v2v3v4v64332256437例6.3下圖所表示的圖可以構(gòu)造權(quán)矩陣B如下:歐拉回路定義

連通圖G中，若存在一條跡，經(jīng)過(guò)每邊一次且僅一次，則稱這條道路為歐拉跡。若存在一條回路經(jīng)過(guò)每邊一次也僅一次，則稱這條回路為歐拉回路。具有歐拉回路的圖稱為歐拉圖（E圖）。歐拉回路推論1無(wú)向連通圖G為歐拉圖，當(dāng)且僅當(dāng)G的邊集可以劃分為若干個(gè)圈。推論2無(wú)向連通圖G中有歐拉跡，當(dāng)且僅當(dāng)G中恰好有兩個(gè)奇點(diǎn)。定理3無(wú)向連通圖G是歐拉圖，當(dāng)且僅當(dāng)G中無(wú)奇點(diǎn)。圖的同構(gòu)圖的同構(gòu)例：例：圖的同構(gòu)例：圖的同構(gòu)有向圖例：abcde2(a)1(b)3(d)4(c)5(e)圖的同構(gòu)例：(1)畫出4個(gè)頂點(diǎn)3條邊的所有可能非同構(gòu)的無(wú)向簡(jiǎn)單圖。(2)畫出3個(gè)頂點(diǎn)2條邊的所有可能非同構(gòu)的有向簡(jiǎn)單圖。?

(1)(2)圖的同構(gòu)中國(guó)郵路問(wèn)題一個(gè)郵遞員，負(fù)責(zé)某一地區(qū)的信件投遞，他每天要走郵局出發(fā)，走遍該地區(qū)所有街道，再返回郵局，問(wèn)應(yīng)如何安排送信的路線可以使所走的總路程最短？用圖論的語(yǔ)言描述就是：給定一個(gè)連通圖G，每邊有非負(fù)權(quán)l(xiāng)(e)，要求一條閉鏈過(guò)每邊至少一次，且滿足總權(quán)最小。中國(guó)郵路問(wèn)題解法（1）若G是歐拉圖，則按歐拉回路走，就是滿足要求的經(jīng)過(guò)每邊至少一次且總權(quán)最小的走法。abcdef若G中有奇點(diǎn)，則G不是歐拉圖，因此要連續(xù)地走過(guò)每邊至少一次，則必然有某些邊不止一次走過(guò)。這相當(dāng)于在G中添加一些重復(fù)的邊，使得到的新圖G*沒(méi)有奇點(diǎn)且滿足總路程最短。中國(guó)郵路問(wèn)題解法（2）abcdefabcdef對(duì)增加了重復(fù)邊后得到的新圖G*，很明顯其總權(quán)的大小取決于增加的重復(fù)邊權(quán)的大小。因此中國(guó)郵路問(wèn)題轉(zhuǎn)化為如下問(wèn)題：在連通圖G=(V,E)中，求一個(gè)邊的集合E1E，將E1中所有邊都變成重復(fù)邊得到新圖G*，使得G*中無(wú)奇點(diǎn)，且最小中國(guó)郵路問(wèn)題解法（3）上述問(wèn)題的解決依賴于以下結(jié)果：定理4已知圖G*=G+E1無(wú)奇點(diǎn)，則最小的充分必要條件為：（1）每條邊最多重復(fù)一次；（2）對(duì)圖G中的每個(gè)圈來(lái)說(shuō)，重復(fù)邊的長(zhǎng)度不超過(guò)圈長(zhǎng)的一半。中國(guó)郵路問(wèn)題解法（4）下面直觀地說(shuō)明，若定理5的條件不成立，則可以得到總權(quán)比E1的更小的重復(fù)邊集。122254122254重復(fù)兩次或以上的去掉其中兩條將原來(lái)的重復(fù)邊變成非重復(fù)邊，原來(lái)的非重復(fù)邊變成重復(fù)邊中國(guó)郵路問(wèn)題解法（5）解法第一步：確定初始可行方案。若圖中沒(méi)有奇點(diǎn)，則它已經(jīng)是歐拉圖，按歐拉回路走即可。否則，若有奇點(diǎn)，奇點(diǎn)必有偶數(shù)個(gè)，將奇點(diǎn)兩兩配對(duì)，然后找出每對(duì)奇點(diǎn)間的一條道路，將此道路中的每條邊都變成重復(fù)邊。524363459444l12+2l23+2l36+l89+2l78+l69+l14+2l47=51中國(guó)郵路問(wèn)題解法（6）524363459444第二步：調(diào)整可行方案。使重復(fù)邊最多重復(fù)一次524363459444l12+l69+l14+l98=21中國(guó)郵路問(wèn)題解法（7）524363459444第三步：檢查圖中每個(gè)圈是否滿足定理?xiàng)l件（2），若不滿足則進(jìn)行調(diào)整。524363459444524363459444第三步要求檢查每個(gè)圈，這一步可能是相當(dāng)繁瑣的。例如上例中的圖就包括下圖所示的圈。中國(guó)郵路問(wèn)題解法（8）

“巧渡河”問(wèn)題問(wèn)題：人、狼、羊、菜用一條只能同時(shí)載兩位的小船渡河，“狼羊”、“羊菜”不能在無(wú)人在場(chǎng)時(shí)共處，當(dāng)然只有人能架船。圖模型：頂點(diǎn)表示“原岸的狀態(tài)”，兩點(diǎn)之間有邊當(dāng)且僅當(dāng)一次合理的渡河“操作”能夠?qū)崿F(xiàn)該狀態(tài)的轉(zhuǎn)變。起始狀態(tài)是“人狼羊菜”，結(jié)束狀態(tài)是“空”。問(wèn)題的解：找到一條從起始狀態(tài)到結(jié)束狀態(tài)的