圖的概念課件

第六章圖與網(wǎng)絡(luò)方法

圖的概念

樹(shù) 最短路問(wèn)題 網(wǎng)絡(luò)最大流 最小費(fèi)用流1引言--哥尼斯堡七橋問(wèn)題

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

－－物理實(shí)體、事物，一般用vi

表示邊(Edge)

表示兩個(gè)對(duì)象之間的某種特定關(guān)系

－－頂點(diǎn)間的連線(xiàn)，一般用ei

表示

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

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

無(wú)向圖由頂點(diǎn)和邊組成G=（V，E）

弧(Arc)

頂點(diǎn)與頂點(diǎn)之間有方向的連線(xiàn)

有向圖：由點(diǎn)和弧組成

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

V2，又E1

E2

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

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

E2

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

鏈點(diǎn)邊交錯(cuò)系列，記為：圈的鏈簡(jiǎn)單鏈（圈）鏈（圈）中的邊均不相同初等鏈（圈）點(diǎn)均不相同路

初等鏈回路初等圈無(wú)重復(fù)點(diǎn),無(wú)重復(fù)邊有重復(fù)點(diǎn),無(wú)重復(fù)邊4、鏈、路、圈和回路11路回路簡(jiǎn)單鏈初等鏈初等圈12

5、連通圖若一個(gè)圖G的任意兩點(diǎn)之間至少存在一條鏈，則稱(chēng)這個(gè)圖G是一個(gè)連通圖，否則稱(chēng)作不連通圖。例如圖中，v1和v6之間沒(méi)有通路，因此它不是連通圖，而如果去掉v6，則構(gòu)成一個(gè)連通圖。

e1e2e3e4e5v2v3v1v4v5v6e6e7e8e913K部圖連通圖不連通圖二部圖14權(quán)程度的度量，數(shù)量描述線(xiàn)權(quán)給圖的邊賦以某一數(shù)值點(diǎn)權(quán)給圖的頂點(diǎn)賦以某一數(shù)值網(wǎng)絡(luò)賦權(quán)的圖（邊權(quán)圖、點(diǎn)權(quán)圖、混合圖）6、加權(quán)圖

v1139538362v6

v5

v3

v4

v2對(duì)G中的每一條邊相應(yīng)的有一個(gè)數(shù)wij15圖與矩陣

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

1

01

000000000110010000000010001110000000000001001001111000000000000001

100000000000111000

1

001

10000關(guān)聯(lián)矩陣

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

n=v1v2v3v4v5v6v7v8v1v2v3v4v5v6v7v8

010010001010100001001002

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

圖（2）的鄰接矩陣是

3451342122345124319說(shuō)明

當(dāng)圖的頂點(diǎn)和邊（?。┑木幪?hào)確定之后，關(guān)聯(lián)矩陣和鄰接矩陣就與圖建立了確定的一一對(duì)應(yīng)關(guān)系，因而可用關(guān)聯(lián)矩陣或鄰接矩陣來(lái)表達(dá)圖。一般來(lái)說(shuō)，圖的鄰接矩陣比關(guān)聯(lián)矩陣小，因而在存貯和計(jì)算時(shí)用得較多。20二、樹(shù)1、什么是樹(shù)樹(shù):連通的無(wú)圈圖稱(chēng)為樹(shù)，通常用字母T表示懸掛點(diǎn)21樹(shù)的性質(zhì)如果樹(shù)的頂點(diǎn)數(shù)≥2，則它至少有兩個(gè)懸掛點(diǎn)243512435124351如果樹(shù)的頂點(diǎn)個(gè)數(shù)為n，則邊的個(gè)數(shù)為n-1樹(shù)中任意兩個(gè)節(jié)點(diǎn)之間只有唯一的一條鏈在樹(shù)的任意兩個(gè)不相鄰的節(jié)點(diǎn)之間增加一條邊，則形成唯一的圈22定理：（樹(shù)的六個(gè)等價(jià)定義）&

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

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

若T=(V,E)是G的一個(gè)支撐樹(shù),E中的所有邊的權(quán)（）之和稱(chēng)為支撐樹(shù)的權(quán),記為w(T):28

最小樹(shù)（T*）

在賦權(quán)圖G的所有支撐樹(shù)中，必有某個(gè)支撐樹(shù)，其所有邊的權(quán)的和最小，稱(chēng)為最小樹(shù)。求最小樹(shù)的丟邊法（破圈法）

求最小樹(shù)的加邊法（避圈法）

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