图论习题及答案.docx
《图论习题及答案.docx》由会员分享,可在线阅读,更多相关《图论习题及答案.docx(38页珍藏版)》请在冰点文库上搜索。
图论习题及答案
作业解答
练习题2利用matlab编程FFD算法完成下题:
设有6种物品,它们的体积分别为:
60、45、35、20、20和20单位体积,箱子的容积为100个单位体积。
解答一:
function[num,s]=BinPackingFFD(w,capacity)
%一维装箱问题的FFD(降序首次适应)算法求解:
先将物体按长度从大到小排序,
%然后按FF算法对物体装箱
%输入参数w为物品体积,capacity为箱子容量
%输出参数num为所用箱子个数,s为元胞数组,表示装箱方案,s{i}为第i个箱子所装
%物品体积数组
%例w=[60,45,35,20,20,20];capacity=100;
%num=3,s={[1,3],[2,4,5],6};
w=sort(w,'descend');
n=length(w);
s=cell(1,n);
bin=capacity*ones(1,n);
num=1;
fori=1:
n
forj=1:
num+1
ifw(i)bin(j)=bin(j)-w(i);
s{j}=[s{j},i];
ifj==num+1
num=num+1;
end
break;
end
end
end
s=s(1:
num);
解答二:
clear;
clc;
V=100;
v=[604535202020];
n=length(v);
v=fliplr(sort(v));
box_count=1;
x=zeros(n,n);
V_Left=100;
fori=1:
n
ifv(i)>=max(V_Left)
box_count=box_count+1;
x(i,box_count)=1;
V_Left=[V_LeftV-v(i)];
else
j=1;
while(v(i)>V_Left(j))
j=j+1;
end
x(i,j)=1;
V_Left(j)=V_Left(j)-v(i);
end
temp=find(x(i,:
)==1);
fprintf('第%d个物品放在第%d个容器\n',i,temp)
end
output:
第1个物品放在第1个容器
第2个物品放在第2个容器
第3个物品放在第1个容器
第4个物品放在第2个容器
第5个物品放在第2个容器
第6个物品放在第3个容器
解答三:
functionbox_count=FFD(x)
%降序首次适应算法
v=100;
x=fliplr(sort(x));
%v=input('请输入箱子的容积:
');
n=length(x);
I=ones(n);
E=zeros(1,n);
box=v*I;
box_count=0;
fori=1:
n
j=1;
while(j<=box_count)
ifx(i)>box(j)
j=j+1;
continue;
else
box(j)=box(j)-x(i);
E(i)=j;
break;
end
end
ifj>box_count
box_count=box_count+1;
box(box_count)=box(box_count)-x(i);
E(i)=j;
end
end
disp(E);
在命令窗口输入:
>>x=[60,45,35,20,20,20];
>>FFD(x)
121223
ans=
3
练习题5“超市大赢家”提供了50种商品作为奖品供中奖顾客选择,车的容量为1000dm3,奖品i占用的空间为widm3,价值为vi元,具体的数据如下:
vi={220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1}
wi={80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1}。
问如何装车才能总价值最大。
解答:
clear;
clc;
v=[220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1];
w=[80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1];
totalw=1000;limitw=1000;
n=length(w);
fori=1:
n
f(1,i)=v(i)/w(i);
f(2,i)=w(i);
f(3,i)=i;
end
fori=1:
(n-1)
forj=(i+1):
n
iff(1,i)t=f(1,i);
f(1,i)=f(1,j);
f(1,j)=t;
t=f(2,i);
f(2,i)=f(2,j);
f(2,j)=t;
t=f(3,i);
f(3,i)=f(3,j);
f(3,j)=t;
end
end
end
totalv=0;a=[];
fori=1:
n
iff(2,i)<=limitw
a=[a,f(3,i)];%disp(f(3,i));
limitw=limitw-f(2,i);
totalv=totalv+f(1,i)*f(2,i);
end
end
a
totalv
totalw=totalw-limitw
结果
a=
Columns1through21
10401725281619353782620131124279234114
Columns22through27
2263014247
totalv=
3103
totalw=
1000
练习题8对最后一个求有向圈的示例用matlab程序实现。
解答:
H=[01000;
00011;
11100;
00101;
01000];
n=size(H,1);%顶点个数
p=zeros(1,n);%存储搜索过的顶点
X=zeros(n,n);%用来设置禁止矩阵,往回返的时候设置此路已被搜索
k=1;
p
(1)=1;%第一个点作为初始点开始搜索
whilep
(1)<=n%每个顶点都作为初始点搜索包含p
(1)的有向圈,
i=p
(1)+1;%当前点k往后搜索时都是从p
(1)+1开始,从而也可以搜索下标小于k的点
whilei<=n%还有后续点没有搜索(这些点有可能比当前点k小)
if(H(p(k),i)==1)&(X(p(k),i)==0)&isempty(find(p==i))%满足三个条件
k=k+1;%搜索路径上增加一个点
p(k)=i;%搜索路径向前延伸一个点
else
i=i+1;%当前被搜索点不满足条件,换下一个点
end
end
ifi>n%k点往后的所有点都被搜索
ifH(p(k),p
(1))==1%有圈,每次搜索的都是包含初始点的圈
disp(p(1:
k));%输出圈
end
%不管有没有圈,此时k点要往回返
ifk>1%路径上不止出发点
forj=1:
n
X(p(k),j)=0;%取消以前的限制通行
end
X(p(k-1),p(k))=1;%增加此路已搜索
p(k)=0;%撤销路径上的k点
k=k-1;%返回上一个点作为当前点
else%返回到出发点了
p
(1)=p
(1)+1;%换下一个出发点(初始点)
end
end
end
运行结果:
1243
245
243
25
3
练习题9选址问题现准备在7个居民点中设置一银行,路线与距离如下图,问设在哪个点,可使最大服务距离最小若设两个点呢
解答:
第一步:
function[D,R]=floyd(A)
%用floyd算法实现求任意两点之间的最短路程。
可以有负权
%参数D为连通图的权矩阵
A=[03infinfinfinfinf
302infinfinf
inf206inf4
infinf60infinf3
infinfinfinf0inf
infinf0
infinf43inf0
];
D=A;n=length(D);
fori=1:
n
forj=1:
n
R(i,j)=i;%赋路径初值
end
end
fork=1:
n
fori=1:
n
forj=1:
n
ifD(i,k)+D(k,j)D(i,j)=D(i,k)+D(k,j);%更新D(i,j),说明通过k的路程更短
R(i,j)=R(k,j);%更新R(i,j),需要通过k
end
end
end
hl=0;
fori=1:
n
ifD(i,i)<0
hl=1;
break;%跳出内层的for循环
end
end
if(hl==1)
fprintf('有负回路')
break;%跳出最外层循环
end
end
D
运行结果:
D=
0
0
0
0
0
0
0
第二步:
对于第一问
在矩阵D中每一个取大得到一列数,再在这列数中取小,
[m,n]=size(D);
p=[];
fori=1:
m
p(i)=max(D(i,:
));
end
fori=1:
m
ifp(i)==min(p)
disp(i);
end
end
min(p)
在顶点6建立银行,最大服务距离最小,最小是.
第三步:
对于第二问
任取两个点做集合,计算每个点到这个集合的最小值,再在这个最小值中取大,即在矩阵D中任取两行,对应比较取小得一向量,将所有这样的向量写成行向量构成一矩阵,然后用问题一的算法程序即可。
a=0;
b=[];
n=size(D,1);
fori=1:
(n-1)
forj=(i+1):
n
a=a+1;
fork=1:
n
s{a}=[ij];
b(a,k)=min(D(i,k),D(j,k));
end
end
end
m=size(b,1);
p=[];
fori=1:
m
p(i)=max(b(i,:
));
end
fori=1:
m
ifp(i)==min(p)
disp(s{i});
end
end
min(p)
结果,在顶点2,4或2,7点建立银行都使得最大服务距离最小,最小值是3
练习题10货物调运已知该地区有生产该物资的企业三家,大小物资仓库八个,国家级储备库两个,其分布情况见下面的附件1。
经核算该物资的运输成本为高等级公路2元/公里百件,普通公路元/公里百件,假设各企业、物资仓库及国家级储备库之间的物资可以通过公路运输互相调运,请给出各个仓库应该从哪个企业调运。
解答:
首先建立各个交汇点的距离矩阵m。
然后建立函数文件。
%各仓库到各企业的最小运费
functionmin_spend(m)
c=[28,23,35,31,22,36,29,38];%仓库
cc=[27,30];%国家储存库
C=[c,cc];
g=[8,15,11,27,7,10,17,14,28,16,18,25,6,5,39,35,13,40,4,29];%高级公路上的点
n=length(g);
A=zeros(42);
fori=1:
42
forj=1:
42
ifm(i,j)~=0
A(i,j)=*m(i,j);%普通公路上每百件的运费
else
A(i,j)=inf;
end
end
end
fori=1:
n
forj=1:
n
A(g(i),g(j))=2*A(g(i),g(j))/;%高级公路上每百件的运费
end
end
fori=1:
42
A(i,i)=0;
end
[D,R]=floyd(A);
fori=1:
10
forj=1:
3
X(i,j)=D(C(i),q(j));
end
end
[XX,INDEX]=min(X')
在命令窗口输入:
>>min_spend(m)
XX=
INDEX=
2133132313
XX为从各个仓库到三个企业中的最小费用,INDEX为最小费用的企业。
练习题14最小代价流将上题容量网络的边上增加另一个权数----代价,变为具有代价的容量网络,单位代价为容量数的十位上的数字,求比最大流少30单位的最小代价流。
由上题结果可知,最大流为142,则最小代价流的流量应该为112。
用迭代算法,预定流量值wf0=112。
方法一:
C=[025056610000;
00710036000;
0000000340;
00004907400;
024000725700;
003800005345;
00000380067;
0000000074;
000000000];%弧容量
b=[020560000;
007003000;
000000030;
000040700;
020007500;
003000054;
000003006;
000000007;
000000000];%弧上单位流量的费用
n=9;
wf=0;wf0=112;%wf表示最大流量,wf0表示预定的流量值
for(i=1:
n)for(j=1:
n)f(i,j)=0;end;end%取初始可行流f为零流
while
(1)
for(i=1:
n)for(j=1:
n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋权图
for(i=1:
n)for(j=1:
n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j);
elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j);
elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end
for(i=2:
n)p(i)=Inf;s(i)=i;end%用Ford算法求最短路,赋初值
for(k=1:
n)pd=1;%求有向赋权图中vs到vt的最短路
for(i=2:
n)for(j=1:
n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end;end;end
if(pd)break;end;end%求最短路的Ford算法结束
if(p(n)==Inf)break;end%不存在vs到vt的最短路,算法终止.注意在求最小费用最大流时构造有向赋权图中不会含负权回路,所以不会出现k=n
dvt=Inf;t=n;%进入调整过程,dvt表示调整量
while
(1)%计算调整量
if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t);%前向弧调整量
elseif(a(s(t),t)<0)dvtt=f(t,s(t));end%后向弧调整量
if(dvt>dvtt)dvt=dvtt;end
if(s(t)==1)break;end%当t的标号为vs时,终止计算调整量
t=s(t);end%继续调整前一段弧上的流f
pd=0;if(wf+dvt>wf0)dvt=wf0-wf;pd=1;end%如果最大流量大于或等于预定的流量值
t=n;while
(1)%调整过程
if(a(s(t),t)>0)f(s(t),t)=f(s(t),t)+dvt;%前向弧调整
elseif(a(s(t),t)<0)f(t,s(t))=f(t,s(t))-dvt;end%后向弧调整
if(s(t)==1)break;end%当t的标号为vs时,终止调整过程
t=s(t);end
if(pd)break;end%如果最大流量达到预定的流量值
wf=0;for(j=1:
n)wf=wf+f(1,j);end;end%计算最大流量
zwf=0;for(i=1:
n)for(j=1:
n)zwf=zwf+b(i,j)*f(i,j);end;end%计算最小费用
f%显示最小费用最大流
wf%显示最小费用最大流量
zwf%显示最小费用
运行结果:
>>
f=
025026610000
0000036000
000000000
0000002600
01100094100
0000000045
0000000067
000000000
000000000
wf=
112
zwf=
1708
由程序运行结果可得:
比最大流少30单位的最小代价流为f,最小代价为1708。
方法二
在已知流量上限情况下的Lingo最小费用求解
sets:
nodes/1..9/:
;
arcs(nodes,nodes):
c,b,f;!
f为流,c为网络容量,b为费用;
endsets
data:
fmax=112;!
流量上界;
c=025056610000
00710036000
0000000340
00004907400
024000725700
003800005345
00000380067
0000000074
000000000;
b=020560000
007003000
000000030
000040700
020007500
003000054
000003006
000000007
000000000;
enddata
min=@sum(arcs:
b*f);
@for(nodes(i)|i#ne#1#and#i#ne#@size(nodes):
@sum(arcs(i,j):
f(i,j))-@sum(arcs(j,i):
f(j,i))=0);
@sum(arcs(i,j)|i#eq#1:
f(i,j))=fmax;
@for(arcs:
@bnd(0,f,c));
练习题20现在有8个城市,已知两个城市之间的路费如下表,现在有一个人从A城市出发旅行,应该选择怎样的路线才能刚好每个城市都到达一次又回到A城市,其总路费最少
ABCDEFGH
A
B
C
D
E
F
G
56352151604339
215778706449
3668---7060
51616526
134562
5326
50
解答:
方法一
建立规划模型:
先将一般加权连通图转化成一个等价的加权完全图,设当从
到
时,
,否则,
,则得如下模型:
利用lingo求解:
model:
!
TSP问题;
sets:
cities/A,B,C,D,E,F,G,H/:
level;
link(cities,cities)|&1#ne#&2:
w,x;!
W距离矩阵;
endsets
data:
w=56352151604339
56215778706449
3521366810007060
21573651616526
51786851134561
6070100061135326
43647065455350
39496026612650;
enddata
n=@size(cities);
min=@sum(link(i,j)|i#ne#j:
w(i,j)*x(i,j));
@for(cities(i):
@sum(cities(j)|j#ne#i:
x(j,i))=1;
@sum(cities(j)|j#ne#i:
x(i,j))=1;
@for(cities(j)|j#gt#1#and#j#ne#i:
level(j)>=level(i)+x(i,j)
-(n-2)*(1-x(i,j))+(n-3)*x(j,i);
);
);
@for(link:
@bin(x