運(yùn)籌學(xué)-圖與網(wǎng)絡(luò)分析課件

OPERATIONSRESE運(yùn)籌學(xué)第六章圖與網(wǎng)絡(luò)分析引論:哥尼斯堡七橋問題鐵路交通圖此圖是我國北京,上海等十個(gè)北京天津城市間的交通圖,反映了這十個(gè)城市間的鐵路分布情況濟(jì)南青島點(diǎn)表示城市點(diǎn)間的連線表示兩個(gè)城市間的鐵路線鄭州徐州連云港諸如此類問題還有電話線分南京上海布圖或煤氣管道分布圖等武漢球隊(duì)比賽圖五個(gè)球隊(duì)比賽比過的兩個(gè)隊(duì)之間用連線相連,還沒有比賽的隊(duì)之間沒有連線61圖的基本概念a圖是由點(diǎn)和線構(gòu)成的。點(diǎn)代表所研究的對(duì)象,線表示對(duì)象間的關(guān)系。a1、圖的分類:無向圖,有向圖無向圖:由點(diǎn)和邊所組成的圖。表示為G=(VE)有向圖:由點(diǎn)和弧所組成的圖。表示為D=VA)點(diǎn)的集合用Ⅴ表示,V={v}2、圖上的基本概念:(1)邊:圖中不帶箭頭的連線叫做邊(edge),邊的集合記為E={e},一條邊可以用兩點(diǎn)[vv表示,e=[vv弧:圖中帶箭頭的連線叫做弧(arc),弧的集合記為A,A={a,條弧也是用兩點(diǎn)表示,ak=[wv弧有方向:v為始點(diǎn),w為終點(diǎn)口例13a4a6a9為V2環(huán):兩端點(diǎn)相同的邊。多重邊:若兩點(diǎn)之間有多于一條邊,則稱這些邊為多重邊。簡單圖:無環(huán)、無多重邊的圖。多重圖:無環(huán),但允許有多重邊的圖。(2)次:以點(diǎn)u為端點(diǎn)的邊的條數(shù),叫做點(diǎn)u的次。懸掛點(diǎn):次為1的點(diǎn)叫做懸掛點(diǎn);孤立點(diǎn):次為0的點(diǎn)叫做孤立點(diǎn);奇點(diǎn):次為奇數(shù)則稱奇點(diǎn);偶點(diǎn):次為偶數(shù)則稱偶點(diǎn)?；径ɡ?、圖G=(VE)中,所有點(diǎn)的次之和是邊數(shù)的兩倍,即d(v)=2q2、任一圖中,奇點(diǎn)的個(gè)數(shù)為偶數(shù)。(3)鏈:點(diǎn)邊交替序列稱為鏈;圈:首尾相連的鏈稱為圈初等鏈:鏈中各點(diǎn)均不同的鏈;初等圈:圈中各點(diǎn)均不同的圈;簡單鏈:鏈中邊均不同的鏈;簡單圈:圈中邊均不同的圈。(4)連通圖:任意兩點(diǎn)之間至少有一條鏈的圖連通分圖:對(duì)不連通的圖,每一連通的部分稱為一個(gè)連通分圖。支撐子圖:對(duì)G=(VE),若G=(V,E),使V=V,E'包含于E,則G是G的一個(gè)支撐子圖。賦權(quán)圖:在圖中,如果每一條邊(弧)都被賦予一個(gè)權(quán)值(5)路:在有向圖中,如果鏈上每條弧的箭線方向與鏈行進(jìn)方向相同,則稱之為路?；芈?首尾相接的路稱回路62樹與最小生成樹1、樹的概念與性質(zhì)樹:無圈的連通圖稱為樹定理:定量3:設(shè)圖G=(VE是一個(gè)樹,p(G)2,則G中至少有兩個(gè)懸掛點(diǎn)。定量4:圖G=(VE)是一個(gè)樹的充要條件是G不含圈,且恰有p-1條邊。定量5:圖G=(VE是一個(gè)樹的充要條件是G是連通圖,并且q(G)=p(G)定量6:圖G=(V,E)是一個(gè)樹的充要條件是任意兩個(gè)頂點(diǎn)之間恰好有一條鏈。2、圖的支撐樹支撐樹:設(shè)T=(VE)是圖G=(VE)的支撐子圖,如果T是一個(gè)樹,則稱T為G的支撐樹。定理7:圖G有支撐樹的充要條件是圖G是連通的。求支撐樹的方法:破圈法:即任取一個(gè)圈,從圈中去掉一條邊,對(duì)余下的圖重復(fù)這