图论习题及答案(共24页).doc
精选优质文档-倾情为你奉上作业解答练习题2 利用matlab编程FFD算法完成下题：设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。解答一：function num,s = BinPackingFFD(w,capacity)%一维装箱问题的FFD（降序首次适应）算法求解:先将物体按长度从大到小排序,%然后按FF算法对物体装箱%输入参数w为物品体积，capacity为箱子容量%输出参数num为所用箱子个数，s为元胞数组，表示装箱方案，si为第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;for i = 1:n for j = 1:num + 1 if w(i) < bin(j) bin(j) = bin(j) - w(i); sj = sj,i; if j = num + 1 num = num + 1; end break; end end ends = s(1:num);解答二：clear;clc;V=100;v=60 45 35 20 20 20;n=length(v);v=fliplr(sort(v);box_count=1;x=zeros(n,n);V_Left=100;for i=1:n if v(i)>=max(V_Left) box_count=box_count+1; x(i,box_count)=1; V_Left=V_Left V-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)endoutput:第1个物品放在第1个容器第2个物品放在第2个容器第3个物品放在第1个容器第4个物品放在第2个容器第5个物品放在第2个容器第6个物品放在第3个容器解答三：function box_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;for i=1:n j=1; while(j<=box_count) if x(i)>box(j) j=j+1; continue; else box(j)=box(j)-x(i); E(i)=j; break; end end if j>box_count box_count=box_count+1; box(box_count)=box(box_count)-x(i); E(i)=j; endenddisp(E);在命令窗口输入：>> x=60,45,35,20,20,20;>> FFD(x) 1 2 1 2 2 3ans = 3练习题5 “超市大赢家”提供了50种商品作为奖品供中奖顾客选择,车的容量为1000dm3 , 奖品i占用的空间为wi dm3 ,价值为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, 1wi = 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);for i=1:n f(1,i)=v(i)/w(i); f(2,i)=w(i); f(3,i)=i;endfor i=1:(n-1) for j=(i+1):n if f(1,i)<f(1,j) 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 endendtotalv=0;a=;for i=1:n if f(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); endendatotalvtotalw=totalw-limitw结果a = Columns 1 through 21 10 40 17 25 28 16 19 35 37 8 26 20 13 11 24 27 9 23 41 1 4 Columns 22 through 27 22 6 30 14 2 47totalv = 3103totalw = 1000练习题8 对最后一个求有向圈的示例用matlab程序实现。解答：H= 0 1 0 0 0; 0 0 0 1 1; 1 1 1 0 0; 0 0 1 0 1; 0 1 0 0 0;n=size(H,1);%顶点个数p=zeros(1,n);%存储搜索过的顶点X=zeros(n,n);%用来设置禁止矩阵，往回返的时候设置此路已被搜索k=1;p(1)=1;%第一个点作为初始点开始搜索while p(1)<=n %每个顶点都作为初始点搜索包含p(1)的有向圈， i=p(1)+1;%当前点k往后搜索时都是从p(1)+1开始，从而也可以搜索下标小于k的点while i<=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;%当前被搜索点不满足条件，换下一个点 endendif i>n %k点往后的所有点都被搜索 if H(p(k),p(1)=1%有圈，每次搜索的都是包含初始点的圈 disp(p(1:k);%输出圈 end %不管有没有圈，此时k点要往回返 if k>1%路径上不止出发点 for j=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 endend运行结果：1 2 4 3 2 4 5 2 4 3 2 5 3练习题9 选址问题 现准备在7个居民点中设置一银行，路线与距离如下图，问设在哪个点，可使最大服务距离最小？若设两个点呢？解答：第一步：function D,R=floyd(A)%用floyd算法实现求任意两点之间的最短路程。可以有负权%参数D为连通图的权矩阵 A=0 3 inf inf inf inf inf 3 0 2 inf inf 1.5 inf inf 2 0 6 inf 2.5 4 inf inf 6 0 inf inf 3 inf inf inf inf 0 1.5 inf inf 1.5 2.5 inf 1.5 0 1.8 inf inf 4 3 inf 1.8 0 ;D=A;n=length(D);for i=1:n for j=1:n R(i,j)=i;%赋路径初值 endendfor 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);%更新 D(i,j)，说明通过k的路程更短 R(i,j)=R(k,j);%更新R(i,j)，需要通过k end end end hl=0; for i=1:n if D(i,i)<0 hl=1; break;%跳出内层的for循环 end end if(hl=1) fprintf('有负回路') break;%跳出最外层循环 endendD 运行结果：D= 0 3.0000 5.0000 9.3000 6.0000 4.5000 6.3000 3.0000 0 2.0000 6.3000 3.0000 1.5000 3.3000 5.0000 2.0000 0 6.0000 4.0000 2.5000 4.0000 9.3000 6.3000 6.0000 0 6.3000 4.8000 3.0000 6.0000 3.0000 4.0000 6.3000 0 1.5000 3.3000 4.5000 1.5000 2.5000 4.8000 1.5000 0 1.80006.3000 3.3000 4.0000 3.0000 3.3000 1.8000 0第二步：对于第一问在矩阵D中每一个取大得到一列数，再在这列数中取小，m,n=size(D);p=;for i=1:m p(i)=max(D(i,:);end for i=1:m if p(i)=min(p) disp(i); end endmin(p)在顶点6建立银行，最大服务距离最小，最小是4.8.第三步：对于第二问任取两个点做集合，计算每个点到这个集合的最小值，再在这个最小值中取大，即在矩阵D中任取两行，对应比较取小得一向量，将所有这样的向量写成行向量构成一矩阵，然后用问题一的算法程序即可。a=0;b=;n=size(D,1);for i=1:(n-1) for j=(i+1):n a=a+1; for k=1:n sa=i j; b(a,k)=min(D(i,k),D(j,k); end endendm=size(b,1);p=;for i=1:m p(i)=max(b(i,:);end for i=1:m if p(i)=min(p) disp(si); end end min(p)结果，在顶点2,4或2,7点建立银行都使得最大服务距离最小，最小值是3练习题10 货物调运 已知该地区有生产该物资的企业三家，大小物资仓库八个，国家级储备库两个，其分布情况见下面的附件1。经核算该物资的运输成本为高等级公路2元/公里百件，普通公路1.2元/公里百件，假设各企业、物资仓库及国家级储备库之间的物资可以通过公路运输互相调运，请给出各个仓库应该从哪个企业调运。解答：首先建立各个交汇点的距离矩阵m。然后建立函数文件。%各仓库到各企业的最小运费function min_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);for i=1:42 for j=1:42 if m(i,j)=0 A(i,j)=1.2*m(i,j); %普通公路上每百件的运费 else A(i,j)=inf; end endendfor i=1:n for j=1:n A(g(i),g(j)=2*A(g(i),g(j)/1.2; %高级公路上每百件的运费 endendfor i=1:42 A(i,i)=0;endD,R=floyd(A);for i=1:10 for j=1:3 X(i,j)=D(C(i),q(j); end endXX,INDEX=min(X')在命令窗口输入：>> min_spend(m)XX =69.6000 150.0000 147.6000 90.0000 156.0000 174.0000 189.6000 111.6000 120.0000 122.4000INDEX = 2 1 3 3 1 3 2 3 1 3XX为从各个仓库到三个企业中的最小费用，INDEX为最小费用的企业。练习题14 最小代价流 将上题容量网络的边上增加另一个权数-代价，变为具有代价的容量网络，单位代价为容量数的十位上的数字，求比最大流少30单位的最小代价流。由上题结果可知，最大流为142，则最小代价流的流量应该为112。用迭代算法，预定流量值wf0=112。方法一：C=0 25 0 56 61 0 0 0 0; 0 0 71 0 0 36 0 0 0; 0 0 0 0 0 0 0 34 0; 0 0 0 0 49 0 74 0 0; 0 24 0 0 0 72 57 0 0; 0 0 38 0 0 0 0 53 45; 0 0 0 0 0 38 0 0 67; 0 0 0 0 0 0 0 0 74; 0 0 0 0 0 0 0 0 0;%弧容量b=0 2 0 5 6 0 0 0 0; 0 0 7 0 0 3 0 0 0; 0 0 0 0 0 0 0 3 0; 0 0 0 0 4 0 7 0 0; 0 2 0 0 0 7 5 0 0; 0 0 3 0 0 0 0 5 4; 0 0 0 0 0 3 0 0 6; 0 0 0 0 0 0 0 0 7; 0 0 0 0 0 0 0 0 0;%弧上单位流量的费用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;endfor(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;endif(pd)break;end;end%求最短路的Ford算法结束if(p(n)=Inf)break;end%不存在vs到vt的最短路, 算法终止. 注意在求最小费用最大流时构造有向赋权图中不会含负权回路, 所以不会出现k=ndvt=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;endif(s(t)=1)break;end%当t的标号为vs时, 终止计算调整量t=s(t);end%继续调整前一段弧上的流fpd=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);endif(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 = 0 25 0 26 61 0 0 0 0 0 0 0 0 0 36 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 26 0 0 0 11 0 0 0 9 41 0 0 0 0 0 0 0 0 0 0 45 0 0 0 0 0 0 0 0 67 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0wf = 112zwf = 1708由程序运行结果可得：比最大流少30单位的最小代价流为f，最小代价为1708。方法二在已知流量上限情况下的Lingo最小费用求解sets: nodes/1.9/:; arcs(nodes, nodes): c,b,f; !f为流，c为网络容量，b为费用;endsetsdata:fmax = 112; !流量上界; c=0 25 0 56 61 0 0 0 0 0 0 71 0 0 36 0 0 0 0 0 0 0 0 0 0 34 0 0 0 0 0 49 0 74 0 0 0 24 0 0 0 72 57 0 0 0 0 38 0 0 0 0 53 45 0 0 0 0 0 38 0 0 67 0 0 0 0 0 0 0 0 74 0 0 0 0 0 0 0 0 0;b= 0 2 0 5 6 0 0 0 0 0 0 7 0 0 3 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 4 0 7 0 0 0 2 0 0 0 7 5 0 0 0 0 3 0 0 0 0 5 4 0 0 0 0 0 3 0 0 6 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0;enddatamin=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城市，其总路费最少？A B C D E F G HABCDEFG 56 35 21 51 60 43 39 21 57 78 70 64 49 36 68 - 70 60 51 61 65 26 13 45 62 53 26 50解答：方法一建立规划模型：先将一般加权连通图转化成一个等价的加权完全图，设当从到时，否则，则得如下模型：利用lingo求解：model:!TSP问题;sets: cities/A,B,C,D,E,F,G,H/:level; link(cities, cities)|&1#ne#&2: w, x;!W距离矩阵;endsetsdata: w= 56 35 21 51 60 43 39 56 21 57 78 70 64 49 35 21 36 68 1000 70 60 21 57 36 51 61 65 26 51 78 68 51 13 45 61 60 70 1000 61 13 53 26 43 64 70 65 45 53 50 39 49 60 26 61 26 50;enddatan=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);for(cities(i) | i #gt# 1 : level(i)<=n-1-(n-2)*x(1,i); level(i)>=1+(n-2)*x(i,1););end由程序运行结果可得，从A城市出发旅行，刚好每个城市都到达一次又回到A城市，且总路费最少的路线为：。最少费用为251。方法二（参考）求一个Hamilton圈，构造新圈：由中删掉边和，添加边和而得到，判断：若+<+，则以新圈代替旧圈，称为改良圈。cleara(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;a(1,7)=43;a(1,8)=39;a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;a(2,7)=64;a(2,8)=49;a(3,4)=36;a(3,5)=68;a(3,6)=Inf;a(3,7)=70;a(3,8)=60;a(4,5)=51;a(4,6)=61;a(4,7)=65;a(4,8)=26;a(5,6)=13;a(5,7)=45;a(5,8)=62;a(6,7)=53;a(6,8)=26;a(7,8)=50;a(8,:)=0;a=a+a'c1= 1 3 2 5:8 4;L=length(c1);flag=1;while flag>0 flag=0; for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1)<a(c1(m),c1(m+1)+a(c1(n),c1(n+1) flag=1; c1(m+1:n)=c1(n:-1:m+1); end end endendsum1=0;for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1);endsum1=sum1+a(c1(8),c1(1)circle=c1;sum=sum1;c1=1 4 3 2 5:8 ;%改变初始圈，该算法的最后一个顶点不动flag=1;while flag>0 flag=0; for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1)<. a(c1(m),c1(m+1)+a(c1(n),c1(n+1) flag=1; c1(m+1:n)=c1(n:-1:m+1); end end endendsum1=0;for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1);endsum1=sum1+a(c1(8),c1(1)if sum1<sum sum=sum1; circle=c1;endcircle,sum练习题21 某街道布局如下，在0点处停放有一辆洒水车，每天洒水车都要给每条街道洒水，请给洒水车优化一条路线。解答（参考）：以下版本方法正确，应可以简化。该题为中国邮递员问题，故先使用floyd算法求出奇点间的最短距离，并建立以奇点为顶点的完全图，调用jidianjvzhen.m文件clear; c=inf 5 inf 6 inf inf inf inf inf inf 5 inf 5 inf 6 inf inf inf inf inf inf 5 inf inf inf 2 inf inf inf inf 6 inf inf inf 3 inf 4 inf inf inf inf 6 inf 3 inf 6 inf 4 inf inf inf inf 2 inf 6 inf inf inf 4 inf inf inf inf 4 inf inf inf 4 inf 2 inf inf inf inf 4 inf 4 inf 3 inf inf inf inf inf inf 4 inf 3 inf inf inf inf inf inf inf inf 2 inf inf inf; m=length(c); Path=zeros(m); for k=1:m for i=1:m for j=1:m if c(i,j)>c(i,k)+c(k,j) c(i,j)=c(i,k)+c(k,j); Path(i,j)=k; end end end end h1=c(2,4); h2=c(2,6); h3=c(2,7); h4=c(2,8); h5=c(2,10);h6=c(4,6);h7=c(4,7);h8=c(4,8);h9=c(4,10); h10=c(6,7); h11=c(6,8); h12=c(6,10); h13=c(7,8); h14=c(7,10); h15=c(8,10);disp(c(2,6);disp(c(4,8);disp(c(7,10);a=
