数学建模04-图论
程序员文章站
2022-04-22 11:41:13
数学建模04-图论一.图论图与网络是运筹学(Operations Research)中的一个经典和重要的分支。许多经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域的问题。图的优化问题:最小支撑树;最短路径问题;最大流量问题,最小费用最大流问题。1.具体内容1.1 图论的基本概念1.1.1 图的定义1.1.2 其他定义1.1.3 图的矩阵表示1.2 图的优化问题1.2.1 相关函数函数名功能graphallshortes...
数学建模04-图论
一.图论
图与网络是运筹学(Operations Research)中的一个经典和重要的分支。许多经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域的问题。
图的优化问题:
- 最小支撑树;
- 最短路径问题;
- 最大流量问题,最小费用最大流问题。
1.具体内容
1.1 图论的基本概念
1.1.1 图的定义
1.1.2 其他定义
1.1.3 图的矩阵表示
1.2 图的优化问题
1.2.1 相关函数
函数名 | 功能 |
---|---|
graphallshortestpaths | 求图中所有顶点之间的最短距离 |
grapconnredcomp | 找无(有)向图的(强/弱)连通分支 |
graphisreddag | 测试有向图是否含有圈 |
graphisomorphism | 确定一个图是否有生成树 |
graphmaxflow | 计算有向图的最大流 |
graphminspantree | 在图中找最小生成树 |
grapshortestpath | 求置顶一对顶点间的最短距离和路径 |
graphtopoorder | 执行有相无圈图的拓扑排序 |
graphtraverse | 求从一顶点出发,所能便利图中的顶点 |
1.2.2 graphshortestpath函数用法
最短路径求解:
[a,b,c,d,e,f] = deal(1,2,3,4,5,6);
% a b c d e f
w = [ 0 2 3 0 0 0 ; %a
2 0 6 5 3 0 ; %b
3 6 0 0 1 0 ; %c
0 5 0 0 1 2 ; %d
0 3 1 1 0 4 ; %e
0 0 0 2 4 0]; %f
W = sparse(w);
[dist,path,pred] = graphshortestpath(W,a,f)
1.2.3 最小生成树
w = [ 0 4 inf 5 inf 3
4 0 5 inf 3 3
inf 5 0 5 3 inf
5 inf 5 0 2 4
inf 3 3 2 0 1
3 3 inf 4 1 0];
W = sparse(w);
[ST,pred] = graphminspantree(W)
1.2.4 Floyd算法
求解任意两顶点之间的最短路径:
- folyd.m
function [D,path,min1,path1]=floyd(a,start,terminal)
D=a;n=size(D,1);path=zeros(n,n);
for i=1:n
for j=1:n
if D(i,j)~=inf
path(i,j)=j;
end,
end,
end
for k=1:n
for i=1:n
for j=1:n
if D(i,k)+D(k,j)<D(i,j)
D(i,j)=D(i,k)+D(k,j);
path(i,j)=path(i,k);
end,
end,
end,
end
if nargin==3
min1=D(start,terminal);
m(1)=start;
i=1;
path1=[ ];
while path(m(i),terminal)~=terminal
k=i+1;
m(k)=path(m(i),terminal);
i=i+1;
end
m(i+1)=terminal;
path1=m;
end
- tulun2.m
a= [ 0,50,inf,40,25,10;
50,0,15,20,inf,25;
inf,15,0,10,20,inf;
40,20,10,0,10,25;
25,inf,20,10,0,55;
10,25,inf,25,55,0];%矩阵可更改
[D, path]=floyd(a)
1.2.5 最大流量问题
最大流问题(maximum flow problem),一种组合最优化问题,就是要讨论如何充分利用装置的能力,使得运输的流量最大,以取得最好的效果。
例题:
clc,clear
u(1,2)=1;u(1,3)=1;
u(1,4)=2;u(2,3)=1;
u(2,5)=2;u(3,5)=1;
u(4,3)=3;u(4,5)=3;
f(1,2)=1;f(1,3)=0;
f(1,4)=1;f(2,3)=0;
f(2,5)=1;f(3,5)=1;
f(4,3)=1;f(4,5)=0;
n=length(u);
list=[];
maxf(n)=1;
while maxf(n)>0
maxf=zeros(1,n);
pred=zeros(1,n);
list=1;
record=list;
maxf(1)=inf;
%list是未检查邻接点的标号点,record是已标号点
while (~isempty(list))&(maxf(n)==0)
flag=list(1);list(1)=[];
label1= find(u(flag,:)-f(flag,:));
label1=setdiff(label1,record);
list=union(list,label1);
pred(label1)=flag;
maxf(label1)=min(maxf(flag),u(flag,label1)...
-f(flag,label1));
record=union(record,label1);
label2=find(f(:,flag));
label2=label2';
label2=setdiff(label2,record);
list=union(list,label2);
pred(label2)=-flag;
maxf(label2)=min(maxf(flag),f(label2,flag));
record=union(record,label2);
end
if maxf(n)>0
v2=n; v1=pred(v2);
while v2~=1
if v1>0
f(v1,v2)=f(v1,v2)+maxf(n);
else
v1=abs(v1);
f(v2,v1)=f(v2,v1)-maxf(n);
end
v2=v1;
v1=pred(v2);
end
end
end
f
1.2.6 最小费用最大流问题
LINGO程序:
model:
sets:
nodes/s,1,2,3,4,t/:d;
arcs(nodes,nodes):c,u,f;
endsets
data:
d=14 0 0 0 0 -14;
c=0; u=0;
enddata
calc:
c(1,2)=2;
c(1,4)=8; c(2,3)=2;
c(2,4)=5; c(3,4)=1;
c(3,6)=6; c(4,5)=3;
c(5,3)=4;c(5,6)=7;
u(1,2)=8;u(1,4)=7;
u(2,3)=9;u(2,4)=5;
u(3,4)=2;u(3,6)=5;
u(4,5)=9;u(5,3)=6;
u(5,6)=10;
endcalc
min=@sum(arcs:c*f);
@for(nodes(i):@sum(nodes(j):f(i,j))-@sum(nodes(j):f(j,i))=d(i));
@for(arcs:@bnd(0,f,u));
end
(以上文章及代码在查看各种网课和相关资料后整理自用。)
本文地址:https://blog.csdn.net/weixin_45480903/article/details/107347637