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

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

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

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

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旅行商問題的分支界法算法思路參見清華大學版圖論與代數(shù)結構P21lPT圖和PERT圖PT圖l關鍵路徑問題 1max,ijjiijvvvvw v v ,ininvvv v,inv vPERT圖l中國郵路問題（無向圖版）：歐拉回路歐拉回路：)無向圖中，每個結點為偶數(shù)或恰好只有兩個結點為奇結點的連通圖有歐拉回路，反之也對。)有向圖中，每個結點的出度

7、和入度都為偶數(shù)或恰有一個奇出度結點和一個奇入度結點的連通圖有歐拉回路，反之也對。l ) prim算法構造最小生成樹算法構造最小生成樹針對右上圖有如下編程：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算法求最小生成樹：針對上面同樣的例子，該方法的編程為：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件工作 ，每人適合做其中一件或幾件，問能否每人都有一份適合的工作？如果不能，最多幾人可以有適合的工作？ 這個問題的數(shù)學模型是： 是二分圖，頂點集劃分為 ， ，當且僅當 適合做工作 時 求 中的最大對集。 1965年埃德門茲(Edmonds)提出的匈牙利算法 ：nxxx,21nyyy,21GYXGV)(,11nxxX,11nyyYixiy)(GEyxiiG例 32,xyl 最優(yōu)分派問題：分派問題：在人員分派問題中，工作人員適合做的各項工作當中，效益未必一致，我們需要制定一個分派方案，使公司總效益最大。 121il