數(shù)學(xué)建模圖論課件

1、圖論知識(shí)與部分相關(guān)編程介紹圖論知識(shí)與部分相關(guān)編程介紹中南大學(xué)數(shù)學(xué)院中南大學(xué)數(shù)學(xué)院 何偉何偉 圖論源于如下七橋問題圖論源于如下七橋問題左 接近實(shí)物圖接近實(shí)物圖右 抽象成圖論中的圖抽象成圖論中的圖u1736 年發(fā)表的“哥尼斯堡的七座橋” u1847年，克?；舴?yàn)榱私o出電網(wǎng)絡(luò)方程而引進(jìn)了“樹”的概念 u1857年，凱萊在計(jì)數(shù)烷 的同分異構(gòu)物時(shí)，也發(fā)現(xiàn)了“樹” 22 nnHCu哈密爾頓于1859年提出“周游世界”游戲，用了圖論的術(shù)語 圖論的理論和方法已經(jīng)滲透到物理、化學(xué)、通訊科學(xué)、建筑學(xué)、生物遺傳學(xué)、心理學(xué)、經(jīng)濟(jì)學(xué)、社會(huì)學(xué)等學(xué)科中。 基本概念：圖graph、有向圖directed graph 、無向圖

2、undirected graph 、點(diǎn)vertex、邊edge、度degree、權(quán)weight、道路path圖的表示方法：鄰接矩陣adjacency matrix、關(guān)聯(lián)矩陣incident matrix 、邊列表、正向表、逆向表、鄰接表l鄰接矩陣：l關(guān)聯(lián)矩陣每列對(duì)應(yīng)弧的順序?yàn)?1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4) l有向圖的邊列表l無向圖的邊列表l正向表有向圖有向圖無向圖無向圖l逆向表l鄰接表 起點(diǎn)11234455終點(diǎn)23423534權(quán)89640367邊所對(duì)應(yīng)邊所對(duì)應(yīng)權(quán)為右邊：權(quán)為右邊：與圖論有關(guān)的幾個(gè)問題：與圖論有關(guān)的幾個(gè)問題： 最短路

3、問題（SPPshortest path problem） 公路連接問題 指派問題（assignment problem） 中國(guó)郵遞員問題（CPPchinese postman problem） 旅行商問題（TSPtraveling salesman problem） 運(yùn)輸問題（transportation problem） l最短路問題最短路問題 求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法 61v5v6v3v221572346例1、某公司在六個(gè)城市 中有分公司，從到的直接航程票價(jià)記在下述矩陣的 位置上 ，如下矩陣，621,ccc),(ji表示無直接航路 求第一個(gè)城市到其它城市的

4、最短路徑的Matlab程序如下：clear;clc;M=10000;a(1,:)=0,50,M,40,25,10;a(2,:)=zeros(1,2),15,20,M,25;a(3,:)=zeros(1,3),10,20,M;a(4,:)=zeros(1,4),10,25;a(5,:)=zeros(1,5),55;a(6,:)=zeros(1,6);a=a+a;pb(1:length(a)=0;pb(1)=1;index1=1;index2=ones(1,length(a);d(1:length(a)=M;d(1)=0;temp=1;while sum(pb)=2 index=index(1);

5、 end index2(temp)=index;endd, index1, index2 第二種解決這一問題的方法是由Floyd R W提出的算法，稱之為Floyd算法。 Floyd算法的Matlab程序如下：clear;clc;M=10000;a(1,:)=0,50,M,40,25,10;a(2,:)=zeros(1,2),15,20,M,25;a(3,:)=zeros(1,3),10,20,M;a(4,:)=zeros(1,4),10,25;a(5,:)=zeros(1,5),55;a(6,:)=zeros(1,6);b=a+a;path=zeros(length(b);for k=1:6

6、 for i=1:6 for j=1:6 if b(i,j)b(i,k)+b(k,j) b(i,j)=b(i,k)+b(k,j); path(i,j)=k; end end end end第三種算法：第三種算法：Ford算法算法l旅行商問題的“便宜”算法：l旅行商問題的分支界法算法思路參見清華大學(xué)版圖論與代數(shù)結(jié)構(gòu)P21lPT圖和PERT圖PT圖l關(guān)鍵路徑問題 1max,ijjiijvvvvw v v ,ininvvv v,inv vPERT圖l中國(guó)郵路問題（無向圖版）：歐拉回路歐拉回路：)無向圖中，每個(gè)結(jié)點(diǎn)為偶數(shù)或恰好只有兩個(gè)結(jié)點(diǎn)為奇結(jié)點(diǎn)的連通圖有歐拉回路，反之也對(duì)。)有向圖中，每個(gè)結(jié)點(diǎn)的出度

7、和入度都為偶數(shù)或恰有一個(gè)奇出度結(jié)點(diǎn)和一個(gè)奇入度結(jié)點(diǎn)的連通圖有歐拉回路，反之也對(duì)。l ) prim算法構(gòu)造最小生成樹算法構(gòu)造最小生成樹針對(duì)右上圖有如下編程：clc;clear;M=1000;a(1,2)=50; a(1,3)=60;a(2,4)=65; a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50; a(4,6)=30;a(4,7)=42;a(5,6)=70; a=a;zeros(2,7);a=a+a;a(find(a=0)=M;result=;p=1;tb=2:length(a);while length(result)=length(a)-1 temp=a(

8、p,tb);temp=temp(:); d=min(temp); jb,kb=find(a(p,tb)=d); j=p(jb(1);k=tb(kb(1); result=result,j;k;d;p=p,k;tb(find(tb=k)=;endresultlKruskal算法求最小生成樹：針對(duì)上面同樣的例子，該方法的編程為：clc;clear; M=1000; a(1,2)=50; a(1,3)=60;a(2,4)=65; a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50; a(4,6)=30;a(4,7)=42; a(5,6)=70; i,j=find(a=0)

9、&(a=M); b=a(find(a=0)&(a=M); data=i;j;b;index=data(1:2,:); loop=max(size(a)-1; result=; while length(result)v2 index(find(index=v1)=v2; else index(find(index=v2)=v1; end data(:,flag)=; index(:,flag)=; end resultl 匹配問題 人員分派問題：人員分派問題：工作人員 去做n件工作 ，每人適合做其中一件或幾件，問能否每人都有一份適合的工作？如果不能，最多幾人可以有適合的工作？ 這個(gè)問題的數(shù)學(xué)模型是： 是二分圖，頂點(diǎn)集劃分為 ， ，當(dāng)且僅當(dāng) 適合做工作 時(shí) 求 中的最大對(duì)集。 1965年埃德門茲(Edmonds)提出的匈牙利算法 ：nxxx,21nyyy,21GYXGV)(,11nxxX,11nyyYixiy)(GEyxiiG例 32,xyl 最優(yōu)分派問題：分派問題：在人員分派問題中，工作人員適合做的各項(xiàng)工作當(dāng)中，效益未必一致，我們需要制定一個(gè)分派方案，使公司總效益最大。 121il