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

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

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

環,多重邊,簡單圖如果邊e的兩個端點相重，稱該邊為環。如右圖中邊e1為環。如果兩個點之間多于一條，稱為多重邊，如右圖中的e4和e5，對無環、無多重邊的圖稱作簡單圖。含多重邊的圖稱為多重圖。v3e7e4e8e5e6e1e2e3v1v2v4v5簡單圖多重圖圖的基本知識環多重邊

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

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

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

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

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

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

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

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

網絡（賦權圖）設圖G＝（V，E），對G的每一條邊(vi,vj)相應賦予數量指標wij，wij稱為邊(vi,vj)的權，賦予權的圖G稱為網絡(或賦權圖）。權可以代表距離、費用、通過能力(容量)等等。端點無序的賦權圖稱為無向網絡，端點有序的賦權圖稱為有向網絡。①②③④⑤⑥910201571419256圖的基本知識

路徑，圈，連通圖定義

無向圖中一個點、邊交錯的序列，序列中的第一個和最后一個元素都是點，若其中每條邊以序列中位于它之前和之后的點為端點，則稱這個點邊序列為圖中連接其第一個點與最后一個點的鏈（途徑）。鏈中所含的邊數稱為鏈長。圖的基本知識鏈，但只是跡而非路跡：沒有重復邊；路徑：既無重復邊也無重復點。對有向圖可類似定義鏈（各邊方向一致）。路徑，圈，連通圖定義

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

連通圖圖的基本知識定義

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

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

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

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

“巧渡河”問題問題：人、狼、羊、菜用一條只能同時載兩位的小船渡河，“狼羊”、“羊菜”不能在無人在場時共處，當然只有人能架船。圖模型：頂點表示“原岸的狀態”，兩點之間有邊當且僅當一次合理的渡河“操作”能夠實現該狀態的轉變。起始狀態是“人狼羊菜”，結束狀態是“空”。問題的解：找到一條從起始狀態到結束狀態的