圖的概念課件

第六章圖與網絡方法

圖的概念

樹 最短路問題 網絡最大流 最小費用流1引言--哥尼斯堡七橋問題

十八世紀的哥尼斯堡城中流過一條河（普雷.格爾河），河上有7座橋連接著河的兩岸和河中的兩個小島。當時那里的人們熱衷于這樣一個游戲：一個游者怎樣才能一次連續(xù)走過這7座橋，回到原出發(fā)點，而每座橋只允許走一次。沒有人想出走法，又無法說明走法不存在，這就是著名的“哥尼斯堡7橋”難題。2頂點(Vertex)表示研究對象

－－物理實體、事物，一般用vi

表示邊(Edge)

表示兩個對象之間的某種特定關系

－－頂點間的連線，一般用ei

表示

圖(Graph)頂點和邊的集合G＝（V，E）V--點集合E--邊集合1、什么是圖3例V={v1，v2，v3，v4}E={e1，e2，…，e7}eij4e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9階：頂點的個數(shù)n

關聯(lián)：若某頂點與某條邊連接，則稱它們彼此關聯(lián)孤立點：與任何邊沒有關聯(lián)的頂點多重邊：某兩個頂點之間多于一條邊多重圖：具有多重邊的圖環(huán)：起點和終點為一個頂點的邊簡單圖：無多重邊，無環(huán)的圖相鄰：兩頂點之間至少存在一條邊次數(shù)：與某個頂點相關聯(lián)的邊的數(shù)目5

無向圖由頂點和邊組成G=（V，E）

弧(Arc)

頂點與頂點之間有方向的連線

有向圖：由點和弧組成

G=（V，A）2、有向圖和無向圖例V={v1，v2,…,v6}A={a1，a2,…,a9}a1a2a3a4a5v2v3v1v4v5v6a6a7a8a96無向圖有向圖混合圖連線為弧既有邊又有弧連線為邊7子圖設：G1=(V1，E1)，G2=(V2，E2)若：V1

V2，又E1

E2

則稱G1是G2的子圖3、子圖e1e2e3e4e5v2v3v1G1e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9G28生成子圖（支撐子圖）設：G1=(V1，E1)

G2=(V2，E2)若：V1＝V2又E1

E2

則稱G1是G2的生成子圖9基礎圖(母圖)子圖支撐子圖10

鏈點邊交錯系列，記為：圈的鏈簡單鏈（圈）鏈（圈）中的邊均不相同初等鏈（圈）點均不相同路

初等鏈回路初等圈無重復點,無重復邊有重復點,無重復邊4、鏈、路、圈和回路11路回路簡單鏈初等鏈初等圈12

5、連通圖若一個圖G的任意兩點之間至少存在一條鏈，則稱這個圖G是一個連通圖，否則稱作不連通圖。例如圖中，v1和v6之間沒有通路，因此它不是連通圖，而如果去掉v6，則構成一個連通圖。

e1e2e3e4e5v2v3v1v4v5v6e6e7e8e913K部圖連通圖不連通圖二部圖14權程度的度量，數(shù)量描述線權給圖的邊賦以某一數(shù)值點權給圖的頂點賦以某一數(shù)值網絡賦權的圖（邊權圖、點權圖、混合圖）6、加權圖

v1139538362v6

v5

v3

v4

v2對G中的每一條邊相應的有一個數(shù)wij15圖與矩陣

在圖與網絡分析的應用中，將面臨一個問題——如何分析、計算一個較大型的網絡，這當然需借助快速的計算工具——計算機。那么，如何將一個圖表示在計算機中，或者，如何在計算機中存儲一個圖呢？現(xiàn)在已有很多存儲的方法，但最基本的方法就是采用矩陣來表示一個圖，圖的矩陣表示也根據(jù)所關心的問題不同而有——鄰接矩陣、關聯(lián)矩陣、權矩陣等。7、關聯(lián)矩陣和鄰接矩陣16e10e1e2v1v2v3v5v4v8v6v7e3e4e6e5e7e9e12e11e8A=(aij)=v1v2v3v4v5v6v7v8e1e2e3e4e5e6e7e8e9e10e11e12

1

01

000000000110010000000010001110000000000001001001111000000000000001

100000000000111000

1

001

10000關聯(lián)矩陣

0若頂點i與邊j不關聯(lián)aij=1若頂點i與邊j相關聯(lián)17B=（bij）n

n=v1v2v3v4v5v6v7v8v1v2v3v4v5v6v7v8

010010001010100001001002

0000011011100001000100100001110000201000e1e2v1v2v3v5v4v8v6v7e3e4e6e5e7e9e12e11e8鄰接矩陣bij=連接頂點vi和vj的邊數(shù)18鄰接矩陣示例圖（1）的鄰接矩陣是

圖（2）的鄰接矩陣是

3451342122345124319說明

當圖的頂點和邊（弧）的編號確定之后，關聯(lián)矩陣和鄰接矩陣就與圖建立了確定的一一對應關系，因而可用關聯(lián)矩陣或鄰接矩陣來表達圖。一般來說，圖的鄰接矩陣比關聯(lián)矩陣小，因而在存貯和計算時用得較多。20二、樹1、什么是樹樹:連通的無圈圖稱為樹，通常用字母T表示懸掛點21樹的性質如果樹的頂點數(shù)≥2，則它至少有兩個懸掛點243512435124351如果樹的頂點個數(shù)為n，則邊的個數(shù)為n-1樹中任意兩個節(jié)點之間只有唯一的一條鏈在樹的任意兩個不相鄰的節(jié)點之間增加一條邊，則形成唯一的圈22定理：（樹的六個等價定義）&

T連通且無回路&無圈，且有n－1條邊&連通，且有n－1條邊&無圈，但增加一條邊，可得到一個且僅一個圈&連通，但舍棄一條邊，圖便不連通&每一對頂點之間有一條且僅有一條初等鏈232、生成樹（支撐樹）定義

設圖T是圖G的一個生成子圖,如果T是一棵樹,則稱樹T是G的一個生成樹（支撐樹）24圖的生成樹由網絡的所有節(jié)點（n個）和網絡的n-1條邊組成的樹稱為網絡的生成樹，網絡中不屬于生成樹的邊稱為生成樹的弦423142314231423142314231423125生成樹的變換4231網絡的一個生成樹，增加一條弦，形成唯一的圈，去掉生成樹的一條邊，得到一個新的網絡的生成樹423142314231生成樹2生成樹3生成樹1////26生成樹和線性規(guī)劃的關系網絡的一個生成樹對應于線性規(guī)劃的一個基生成樹上的邊對應于線性規(guī)劃的基變量生成樹的弦對應于線性規(guī)劃的非基變量生成樹的變換對應于線性規(guī)劃單純形法的進基和離基變換273、最小生成樹支撐樹的權

若T=(V,E)是G的一個支撐樹,E中的所有邊的權（）之和稱為支撐樹的權,記為w(T):28

最小樹（T*）

在賦權圖G的所有支撐樹中，必有某個支撐樹，其所有邊的權的和最小，稱為最小樹。求最小樹的丟邊法（破圈法）

求最小樹的加邊法（避圈法）

T29丟邊法（破圈法）655172344v1v2v3v4v5v6思路：任選一個圈，從圈中去掉權最大的一條邊。在余下的圖中重復這個步驟，直到得到一不含圈的圖為止。30v1v2v3v5e2e3e5e1e6e7e8v1v2e1v3e2e4e4v4v4v5e6加邊法（避圈法）思路：從所有邊中選出一條權最小的邊，并把它納入樹中；在余下的未選邊中，再選出一條最小且與已選入樹中的邊不構成圈的邊，將其納入樹中；如此重復，直到樹中含有n－1條邊為止。31圖G1542453134421512生成最小樹T生成最