第6章 網(wǎng)絡(luò)優(yōu)化

山東財(cái)經(jīng)大學(xué)運(yùn)籌學(xué)網(wǎng)絡(luò)分析圖與子圖圖的連通與割集樹(shù)與支撐樹(shù)最小樹(shù)最短有向路最大流最小費(fèi)用流圖與子圖圖與網(wǎng)絡(luò)

無(wú)向圖的基本概念

有向圖與網(wǎng)絡(luò)圖的表示方法

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

鄰接矩陣

主要結(jié)論子圖問(wèn)題的背景實(shí)際網(wǎng)絡(luò)--交通網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、Internet網(wǎng)絡(luò)關(guān)系網(wǎng)絡(luò)—人際關(guān)系網(wǎng)絡(luò)、工作關(guān)系網(wǎng)絡(luò)、先后關(guān)系網(wǎng)絡(luò)等抽象網(wǎng)絡(luò)—描述研究對(duì)象之間是否存在關(guān)系無(wú)向圖的基本概念無(wú)向圖G：一個(gè)有序二元組(N,E),記為G=(N,E)G的點(diǎn)集合：

N=（1，2，3，4）是一個(gè)無(wú)向圖的點(diǎn)的集合G的邊集合：E={eij}且eij={ni,nj}為無(wú)序二元組稱ni和nj為eij的端點(diǎn)，且稱eij

連接點(diǎn)ni和nj

3412abcde34512afedbcg圈（環(huán)）：兩個(gè)端點(diǎn)重合為一點(diǎn)的邊（例如圖（1）中的d）孤立點(diǎn)：不與任何邊關(guān)聯(lián)的點(diǎn)（例如圖（1）中的頂點(diǎn)5）重邊：端點(diǎn)重合的邊f(xié)和g點(diǎn)邊關(guān)系關(guān)聯(lián)：一條邊的端點(diǎn)稱為這條邊的關(guān)聯(lián)點(diǎn)，頂點(diǎn)1與邊a和b鄰接：與同一條邊關(guān)聯(lián)的端點(diǎn)稱為是鄰接的，如點(diǎn)1和2，同時(shí)如果兩條邊有一個(gè)公共端點(diǎn)，則稱這兩條邊是鄰接的，如邊a和b。

3412abcde特殊圖類有限圖：點(diǎn)和邊都是有限集合的圖空?qǐng)D：沒(méi)有任何邊的圖平凡圖：只有一個(gè)點(diǎn)的圖簡(jiǎn)單圖：既沒(méi)有環(huán)也沒(méi)有兩條邊連接同一對(duì)點(diǎn)的圖空?qǐng)D平凡圖簡(jiǎn)單圖完全圖：每一對(duì)點(diǎn)之間均有一條邊相連的圖二分圖G=(N,E)：存在的一個(gè)二分劃(S,T)，使得G的每條邊有一個(gè)端點(diǎn)在S中，另一個(gè)端點(diǎn)在T中完全二分圖G=(S,T,E)：S中的每個(gè)點(diǎn)與T中的每個(gè)點(diǎn)都相連的簡(jiǎn)單二分圖簡(jiǎn)單圖G的補(bǔ)圖:與G有相同頂點(diǎn)集合的簡(jiǎn)單圖，且中的兩個(gè)點(diǎn)相鄰當(dāng)且僅當(dāng)它們?cè)贕中不相鄰返回完全圖完全二分圖補(bǔ)圖有向圖與網(wǎng)絡(luò)♂有向圖G：一個(gè)有序二員組(N,A)，記為G=(N,A)G的弧集合：A={aij}且aij={ni,nj}為有序二元組，若aij={ni,nj}，則稱aij從ni連向nj，

ni稱為aij的尾，nj為

aij的頭，ni稱為nj的先輩，nj稱為

ni的后繼有向圖G的基本圖：對(duì)于G的每條弧用一條邊代替后得到的無(wú)向圖網(wǎng)絡(luò)G：對(duì)（有向）圖G的每條邊（弧）都賦予一個(gè)實(shí)數(shù)，并稱為邊（?。┑臋?quán)，則連同它邊（弧）上的權(quán)稱為（有向）網(wǎng)絡(luò)關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣示例134521342返回鄰接矩陣鄰接矩陣示例返回134521342主要結(jié)論♂子圖♂Scilab中輸入圖命令：g=make_graph(name,directed,n,tail,head)其中：

name：圖的名稱，字符串‘graph1’directes：有向無(wú)向，0-無(wú)向圖，1-有向圖

n：頂點(diǎn)個(gè)數(shù)

tail向量，各邊的尾部

head向量，各邊的頭部例子123456abcdefghiabcdefghi121133445254346566邊尾點(diǎn)頭點(diǎn)常用函數(shù)g1=add_edge(i,j,g)//加邊g1=add_node(g,[xy,name])//加點(diǎn)g1=delete_arcs(ij,g)//刪除邊g1=delete_nodes(v,g)//刪除點(diǎn)ma=edge_number(g)//邊數(shù)g2=graph_union(g,g1)//圖的并g1=line_graph(g)//反圖n=node_number(g)//點(diǎn)數(shù)關(guān)聯(lián)矩陣和鄰接矩陣a=graph_2_mat(g,mat)其中g(shù):圖mat:字符串,'node-arc'or'node-node'a:點(diǎn)邊關(guān)聯(lián)矩陣或點(diǎn)點(diǎn)鄰接矩陣g=mat_2_graph(a,directed,[mat])其中a:點(diǎn)邊關(guān)聯(lián)矩陣或點(diǎn)點(diǎn)鄰接矩陣directed:integer,0(無(wú)向)or1(有向)mat:字符串,'node-arc'or'node-node'g:graphlist圖的連通與割集

圖的連通

無(wú)向圖

有向圖圖的割集

概念

主要結(jié)論♂無(wú)向圖的路135426圖G中路：一個(gè)點(diǎn)和邊交替序列(ni,eij,nj,…,nk,ekl,nl)，簡(jiǎn)單路：邊不重的路初級(jí)路：點(diǎn)不重的路回路：在G中，一條至少包含一個(gè)邊并且ni=nl的{ni,nl}路簡(jiǎn)單回路：邊不重的回路初級(jí)回路：點(diǎn)不重的回路連通性點(diǎn)i和j點(diǎn)是連通的：G中存在一條（i，j）路G是連通的：G中任意兩點(diǎn)都是連通的連通分支：G的極大連通子圖返回有向路134256有向圖G中的一條有向路：個(gè)點(diǎn)和弧的交錯(cuò)序列(ni,aij,nj,…,nk,akl,nl)，記為(ni,nl)有向路簡(jiǎn)單有向路：弧不重的有向路初級(jí)有向路：點(diǎn)不重的有向路有向回路：至少包含一條弧且ni=nj的(ni,nj)有向路簡(jiǎn)單有向回路：弧不重的有向回路初級(jí)有向回路：點(diǎn)不重的有向回路

點(diǎn)i和點(diǎn)j是強(qiáng)連通的：G中存在一條(i,j)有向路，也存在一條(j,i)有向路G是強(qiáng)連通的：G中任意兩點(diǎn)都是強(qiáng)連通的G的強(qiáng)連通分支：G的極大連通子圖返回強(qiáng)連通性p=find_path(i,j,g)割集♂割集的性質(zhì)♂樹(shù)與支撐樹(shù)樹(shù)及其基本性質(zhì)

概念及符號(hào)

基本性質(zhì)支撐樹(shù)及其基本性質(zhì)

概念及符號(hào)

基本性質(zhì)概念及符號(hào)最少用多少邊可把下列點(diǎn)連起來(lái)？♂樹(shù)的基本性質(zhì)概念及符號(hào)♂支撐樹(shù)的基本性質(zhì)最小樹(shù)最小樹(shù)及其性質(zhì)求最小樹(shù)的Kruskal算法

算法步驟

算例

算法復(fù)雜性Dijkstra算法

算法步驟

算例

算法復(fù)雜性

Scilab實(shí)現(xiàn)最小支撐樹(shù)算法步驟

算例

1452312432214迭代過(guò)程

1452312432214145231243221414523124322141452312432214算法復(fù)雜性

♂算法步驟

算例

1452312432214迭代過(guò)程

1452312432214145231243221414523124322141452312432214算法復(fù)雜性

Scilab實(shí)現(xiàn)用Scilab語(yǔ)句求解下列網(wǎng)絡(luò)的最小樹(shù)t=min_weight_tree(g)

1452312432214Scilab命令及結(jié)果最短有向路最短有向路問(wèn)題數(shù)學(xué)規(guī)劃模型最短有向路方程Dijkstral算法

Scilab實(shí)現(xiàn)最短有向路問(wèn)題12345652332426179數(shù)學(xué)規(guī)劃模型最短有向路方程通過(guò)求解方程組求出最短有向路需要解決的問(wèn)題1.方程組的解是否唯一？由于最短路長(zhǎng)度是唯一的，如果方程組的解不唯一，就無(wú)法處理。2.方程組的解是否容易求解？求解的難點(diǎn)在哪里？算法步驟

算例

12345652332426179計(jì)算的迭代過(guò)程

123456523324261705∞9∞31234565233242617051095399123456523324261705695391234565233242617056853912345652332426170568539算法復(fù)雜性

Scilab實(shí)現(xiàn)結(jié)果最大流最大流問(wèn)題數(shù)學(xué)規(guī)劃模型最大流最小割定理最大流算法Scilab實(shí)現(xiàn)最大流問(wèn)題1234565233242617數(shù)學(xué)規(guī)劃模型主要定理算法步驟

算例

1234565233242617迭代過(guò)程

1234565,22,23,23,22,2426,21712345632,2112,2426,217-∞+1,3+2,1+1,1算法復(fù)雜性

結(jié)果擴(kuò)展多發(fā)點(diǎn)多收點(diǎn)流邊有損耗的問(wèn)題多階段流問(wèn)題最小費(fèi)用流最小費(fèi)用流問(wèn)題

規(guī)劃模型與對(duì)偶理論

算法步驟

算例

算法復(fù)雜性運(yùn)輸問(wèn)題Scilab實(shí)現(xiàn)最小費(fèi)用流問(wèn)題2,32,13,21,33,11,24,25,21,22,32,13,21,33,11,24,25,21,22,32,13,21,33,11,24,25,21,22222222223211V=4，費(fèi)用為32V=4，費(fèi)用為25線性規(guī)劃形式對(duì)偶規(guī)劃原可行對(duì)偶可行互補(bǔ)松弛基本思路給定一組pj在滿足互補(bǔ)條件的邊上找最大流停止最大流值是否大于v修改pj算法步驟

算例

1,21,21,23,13,4迭代過(guò)程1,2,01,2,01,2,03,1,03,4,000001,2,01,2,01,2,03,1,03,4,011102,01,2,21,2,21,2,23,1,03,4,013201,2,01,2,01,2,03,1,03,4,012202,02,02,02,22,22,21,2,21,2,21,2,23,1,03,4,024302,22,22,21,01,2,21,2,21,2,23,1,03,4,025302,22,22,21,04,01,2,21,2,11,2,23,1,13,4,12530算法復(fù)雜性

♂Scilab實(shí)現(xiàn)用Scilab語(yǔ)言求解以上算例所示網(wǎng)絡(luò)的最小費(fèi)用流Scilab語(yǔ)句：cleartail=[11223];head=[23344];

g=make_graph('g'