图论习题及答案

1、作业解答练习题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,

2、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:nfor j = 1:num + 1if w(i) < bin(j)bin(j) = bin(j) - w(i);sj = sj,i;if j = num + 1num = num + 1;endbreak;endendends = s(1:num);解答二：clear;clc;V=100;v=60 45 35 20 20 20;n=length(v);v=

3、fliplr(sort(v);box_count=1;x=zeros(n,n);V_Left=100;for i=1:nif v(i)>=max(V_Left)box_count=box_count+1;x(i,box_count)=1;V_Left=V_Left V-v(i);elsej=1;while(v(i)>V_Left(j)j=j+1;endx(i,j)=1;V_Left(j)=V_Left(j)-v(i);endtemp=find(x(i,:)=1);fprintf('第d个物品放在第 d个容器n',i,temp) endoutput:第1个物品放在第1

4、个容器第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:nj=1;while(j<=box_count) if x(i)>box(j)j=j+1;continue;else box(j)=box(j)-x(i)

5、;E(i)=j； break;endend if j>box_countbox_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)121223ans =3练习题5超市大赢家提供了 50种商品作为奖品供中奖顾客选择,车的容量为1000dm3,奖品i占用的空间为wi dm3,价值为vi元,具体的数据如下：vi = 220, 208, 198, 192, 180, 180, 165, 162,

6、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,

7、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

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:nf(1,i)=v(i)/w(i);f(2,i)=w(i);end for i=1:(n-1)for j=

9、(i+1):nif 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;endendend totalv=0;a=;for i=1:nif f(2,i)<=limitwa=a,f(3,i);%disp(f(3,i);limitw=limitw-f(2,i);totalv=totalv+f(1,i)*f(2,i);endend atotalvtotalw=totalw-limitw结果a =Columns 1

10、through 21 10401725131124279Columns 22 through 27 2263014totalv = 3103 totalw = 1000281623412471935371482620练习题8 对最后一个求有向圈的例如用 matlab程序实现求写6. 7的有同酒的不向用一闺&T解答：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)

11、=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;%搜索路径向前延伸一个点elsei=i+1;%当前被搜索点不满足条件,换下一个点endendif i>n %k点往后的所有点都被搜索if

12、 H(p(k),p(1)=1%有圈,每次搜索的都是包含初始点的圈disp(p(1:k);% 输出圈end%不管有没有圈,此时k点要往回返if k>1%路径上不止出发点for j=1:nX(p(k),j)=0;%取消以前的限制通行endX(p(k-1),p(k)=1;%增加此路已搜索p(k)=0;%撤销路径上的 k点k=k-1;%返回上一个点作为当前点else %返回到出发点了p(1)=p(1)+1; %换下一个出发点(初始点)endendend运行结果：1243245243253练习题9选址问题 现准备在7个居民点中设置一银行,路线与距离如下列图,问设在哪个 点,可使最大效劳距离最小假设

13、设两个点呢v13 V22V36V41.5 V6 1.8V7V5解答：第一步：function D,R=floyd(A)%用floyd算法实现求任意两点之间的最短路程.可以有负权%#数D为连通图的权矩阵A=03infinfinfinfinf302infinfinfinf206inf4infinf60infinf3infinfinfinf0infinfinf0infinf43inf0;D=A;n=length(D);for i=1:nfor j=1:nR(i,j)=i;%赋路径初值 endendfor k=1:nfor i=1:nfor j=1:nif D(i,k)+D(k,j)<D(i,j

14、)D(i,j尸D(i,k)+D(k,j);%更新D(i,j),说明通过k的路程更短 R(i,j尸R(k,j);%更新R(i,j),需要通过kendendendhl=0;for i=1:nif D(i,i)<0hl=1;break;%跳出内层的for循环endendif(hl=1)fprintf('有负回路')break;%跳出最外层循环endendD运行结果：D=0000000第二步：对于第一问在矩阵D中每一个取大得到一列数,再在这列数中取小,m,n=size(D);P=;for i=1:mp(i)=max(D(i,:);endfor i=1:mif p(i)=min(p

15、) disp(i);endendmin(p)在顶点6建立银行,最大效劳距离最小,最小是 .第三步：对于第二问任取两个点做集合,计算每个点到这个集合的最小值,再在这个最小值中取大,即在矩阵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);endendendm=size(b,1);p=;for i=1:mp(i)=max(b(i,:);endfor i=1:m

16、if p(i)=min(p) disp(si);endendmin(p)结果,在顶点2,4或2,7点建立银行都使得最大效劳距离最小,最小值是3练习题10货物调运 该地区有生产该物资的企业三家,大小物资仓库八个,国家级储藏库两个,其分布情况见下面的附件 1.经核算该物资的运输本钱 为高等级公路2元/公里百件,普通公路元/公里百件,假设各企业、物资仓库及 国家级储藏库之间的物资可以通过公路运输互相调运, 请给出各个仓库应该从哪 个企业调运.e=息可出Jfl. M.脾*串隹*M即舞.M处IL 与® 叫-一 解答：首先建立各个交汇点的距离矩阵m.然后建立函数文件.%各仓库到各企业的最小运费f

17、unction 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:42for j=1:42if m(i,j)=0A(i,j)=*m(i,j);%普通公路上每百件的运费elseA(i,j)=inf;endendendfor i=1:nfor j=1:nA(g(i),g(j)=2*A(g(i),g(j)/;%高级公路上每百件

18、的运费endendfor i=1:42A(i,i)=0;endD,R=floyd(A);for i=1:10for j=1:3X(i,j)=D(C(i),q(j);endendXX,INDEX=min(X')在命令窗口输入：>> min_spend(m)XX =INDEX =2133132313XX为从各个仓库到三个企业中的最小费用,INDEX为最小费用的企业.练习题14最小代价流 将上题容量网络的边上增加另一个权数-代价,变为具有代价的容量网络,单位代价为容量数的十位上的数字,求比最大流少30单位的最小代价流.由上题结果可知,最大流为142,那么最小代价流的流量应该为11

19、2.用迭代算法,预定流量值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

20、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%M 初始可行流 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(

21、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;end if(pd)break;end;end%求最短路

22、的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)

23、;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);end if(pd)break;end%如果最大流量到达预定的流量值wf=0; for(j=1:n)wf=wf+f(1,j

24、);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 =025026610000000003600000000000000000026000110009410000000000450000000067000000000000000000wf = 112zwf =17081708.由程序运行结果可得：比最大流少30单位的最小彳t价流为 f,最小代价为方法二在流量上限情况下的L

25、ingo最小费用求解 sets:nodes/1.9/:;arcs(nodes, nodes): c,b,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

26、 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 40 0 0 0 0 3 0 0 60 0 0 0 0 0 0 0 70 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)=fma

27、x;for(arcs:bnd(0,f,c);练习题20现在有8个城市,两个城市之间的路费如下表,现在有一个人从A城市出发旅行,应该选择怎样的路线才能刚好每个城市都到达一次又回到AVi到Vj时,Xij 1 ,否那么,城市,其总路费最少ABC D E FGHA563521516043B39C2157787064D49E366870F60G51616526134562532650解答:方法一建立规划模型:先将一般加权连通图转化成一个等价的加权完全图,设当从Xij 0,那么得如下模型:nminnWij Xij1,(i 1, ,n)ns.t.Xj 1,(j 1, , n)i1xi1i2Xi2i3x, i

28、k 1,(i1, , ik 1,iki1, 1 , k ,n;k 2, ,n 1)Xj0 或 1,i,j1, ,n;i j利用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 3956 21 57 78 70 64 4935 21 36 68 1000 70 6021 57 36 51 61 65 2651 78 68 51 13 45 6160 70 1000 61

29、 13 53 2643 64 70 65 45 53 5039 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)

30、;););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););A城市,且总end由程序运行结果可得,从 A城市出发旅行,刚好每个城市都到达一次又回到路费最少的路线为：ADHFEGBC A.最少费用为251.方法二(参考)求一个 Hamilton 圈 c % vw 1VjVj 1 vnv1 ,构造新圈：由c中删掉边vm 1和VjVj 1,添加边yVj和Vj 1Vj 1而得到,判断：假设ViVj + Vi 1Vj 1 <ViVi 1 +

31、VjVj 1 ,那么以新圈代替旧圈,称为改进圈.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;

32、a(7,8)=50;a(8,:)=0;a=a+a'c1= 1 3 2 5:8 4;L=length(c1);flag=1;while flag>0flag=0;for m=1:L-3for n=m+2:L-1if 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);endendendendsum1=0;for i=1:L-1sum1=sum1+a(c1(i),c1(i+1);endsum1=sum1+a(c1(8),c1(1)circle=c

33、1;sum=sum1;c1=1 4 3 2 5:8 ;%改变初始圈,该算法的最后一个顶点不动flag=1;while flag>0flag=0;for m=1:L-3for n=m+2:L-1if 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);endendendendsum1=0;for i=1:L-1sum1=sum1+a(c1(i),c1(i+1);endsum1=sum1+a(c1(8),c1(1)if sum1<sumsum=su

34、m1;circle=c1;endcircle,sum练习题21某街道布局如下,在0点处停放有一辆洒水车,每天洒水车都要给 每条街道洒水,请给洒水车优化一条路线.53IS 4解答(参考)：以下版本方法正确,应可以简化.该题为中国邮递员问题,故先使用floyd算法求出奇点间的最短距离,并建立以奇点为顶点的完全图,调用文件clear;c=inf 5 inf 6 inf inf inf inf inf inf5 inf 5 inf 6 inf inf inf inf infinf 5 inf inf inf 2 inf inf inf inf6 inf inf inf 3 inf 4 inf inf

35、infinf 6 inf 3 inf 6 inf 4 inf infinf inf 2 inf 6 inf inf inf 4 infinf inf inf 4 inf inf inf 4 inf 2inf inf inf inf 4inf 4 inf 3 infinf inf inf inf inf4 inf3 inf infinf inf inf inf inf inf 2 inf inf inf;m=length(c);Path=zeros(m);for k=1:mfor i=1:mfor j=1:mif c(i,j)>c(i,k)+c(k,j)c(i,j)=c(i,k)+c(k,

36、j);Path(i,j)=k;endendendendh1=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=zeros(6); a(1,2)=h1;a(1,3)=h2;a(1,4)=h3;a(1,5)=h4;a(1,6)=h5; a(2,3)=h6;a(

37、2,4)=h7 ;a(2,5)=h8;a(2,6)=h9;a(3,4)=h10;a(3,5)=h11;a(3,6)=h12;a(4,5)=h13;a(4,6)=h14;a(5,6)=h15;a=a+a' a(find(a=0)=inf;Hung_Al(a);%原矩B的2, 4, 6, 7, 8, 10分别对应于奇点矩阵的1, 2, 3, 4, 5, 6顶点%接着调用文件找出以奇点为顶点的完全图的最优匹配function Matching,Cost = Hung_Al(Matrix)Matrix=a;Matching = zeros(size(Matrix);%找出每行和每列相邻的点数n

38、um_y = sum(isinf(Matrix),1); num_x = sum(isinf(Matrix),2);%找出每行和每列的孤立点数x_con = find(num_x-=0); y_con = find(num_y-=0); %将矩阵压缩、重组 P_size = max(length(x_con),length(y_con);P_cond = zeros(P_size);P_cond(1:length(x_con),1:length(y_con) = Matrix(x_con,y_con);if isempty(P_cond)Cost = 0;return;end%保证存在完美匹配

39、,计算矩阵边集Edge = P_cond;Edge(P_cond=Inf) = 0;cnum=min_line_cover(Edge);Pmax = max(max(P_cond(P_cond=Inf);P_size = length(P_cond)+cnum;P_cond = ones(P_size)*Pmax;P_cond(1:length(x_con),1:length(y_con) = Matrix(x_con,y_con);%主函数程序,此处将每个步骤用switch命令进行限制调用步骤函数exit_flag = 1;stepnum = 1;while exit_flagswitch

40、stepnumcase 1P_cond,stepnum = step1(P_cond);case 2r_cov,c_cov,M,stepnum = step2(P_cond);case 3c_cov,stepnum = step3(M,P_size);case 4M,r_cov,c_cov,Z_r,Z_c,stepnum = step4(P_cond,r_cov,c_cov,M);case 5M,r_cov,c_cov,stepnum = step5(M,Z_r,Z_c,r_cov,c_cov);case 6P_cond,stepnum = step6(P_cond,r_cov,c_cov);

41、case 7exit_flag = 0;endendMatching(x_con,y_con) = M(1:length(x_con),1:length(y_con);Cost = sum(sum(Matrix(Matching=1);MatchingCost%下面是6个步骤函数 step1step6%步骤1:找到包含 0最多的行,从该行减去最小值function P_cond,stepnum=step1(P_cond)P_size = length(P_cond);for ii = 1:P_sizermin = min(P_cond(ii,:);P_cond(ii,:) = P_cond(i

42、i,:)-rmin;endstepnum = 2;%步骤2：在P-cond中找一个 0,并找出一个以该数 0为星型的覆盖function r_cov,c_cov,M,stepnum = step2(P_cond)%定义变量r-cov, c-cov分别表示行或列是否被覆盖P_size = length(P_cond);r_cov = zeros(P_size,1);c_cov = zeros(P_size,1);M = zeros(P_size);for ii = 1:P_sizefor jj = 1:P_sizeif P_cond(ii,jj) = 0 && r_cov(ii)

43、 = 0 && c_cov(jj) = 0M(ii,jj) = 1; r_cov(ii) = 1; c_cov(jj) = 1;endendend%重初始化变量r_cov = zeros(P_size,1);c_cov = zeros(P_size,1);stepnum = 3;%步骤3:每列都用一个 0构成的星型覆盖,如果每列都存在这样的覆盖,那么 M为最大 匹配function c_cov,stepnum = step3(M,P_size)c_cov = sum(M,1);if sum(c_cov) = P_sizestepnum = 7;else stepnum = 4;

44、end%步骤4:找一个未被覆盖的0且从这出发点搜寻星型0覆盖.如果不存在,转步骤 5,否那么转步骤6function M,r_cov,c_cov,Z_r,Z_c,stepnum = step4(P_cond,r_cov,c_cov,M)P_size = length(P_cond);zflag = 1;while zflagrow = 0;col = 0;exit_flag = 1; ii = 1; jj = 1;while exit_flagif P_cond(ii,jj) = 0 && r_cov(ii) = 0 && c_cov(jj) = 0row =

45、ii;col = jj;exit_flag = 0;endjj = jj + 1;if jj > P_size; jj = 1; ii = ii+1; endif ii > P_size; exit_flag = 0; endendif row = 0stepnum = 6;zflag = 0;Z_r = 0;Z_c = 0;elseM(row,col) = 2;if sum(find(M(row,:)=1) = 0r_cov(row) = 1; zcol = find(M(row,:)=1); c_cov(zcol) = 0;else stepnum = 5; zflag = 0

46、; Z_r = row; Z_c = col;endendend%步骤5:function M,r_cov,c_cov,stepnum = step5(M,Z_r,Z_c,r_cov,c_cov)zflag = 1; ii = 1;while zflagrindex = find(M(:,Z_c(ii)=1);if rindex > 0ii = ii+1;Z_r(ii,1) = rindex;Z_c(ii,1) = Z_c(ii-1);else zflag = 0;endif zflag = 1;cindex = find(M(Z_r(ii),:)=2); ii = ii+1; Z_r(

47、ii,1) = Z_r(ii-1); Z_c(ii,1) = cindex; endendfor ii = 1:length(Z_r)if M(Z_r(ii),Z_c(ii) = 1M(Z_r(ii),Z_c(ii) = 0;else M(Z_r(ii),Z_c(ii) = 1;endendr_cov = r_cov.*0; c_cov = c_cov.*0; M(M=2) = 0; stepnum = 3;%步骤6:function P_cond,stepnum = step6(P_cond,r_cov,c_cov)a = find(r_cov = 0);b = find(c_cov = 0

48、);minval = min(min(P_cond(a,b);P_cond(find(r_cov = 1),:) = P_cond(find(r_cov = 1),:) + minval; P_cond(:,find(c_cov = 0)= P_cond(:,find(c_cov = 0) - minval;stepnum = 4;%function cnum=min_line_cover(Edge)r_cov,c_cov,M,stepnum=step2(Edge);c_cov,stepnum = step3(M,length(Edge);M,r_cov,c_cov,Z_r,Z_c,stepn

49、um = step4(Edge,r_cov,c_cov,M);cnum = length(Edge)-sum(r_cov)-sum(c_cov);Hung_Al运行的结果如下:TT2'latching =即对于所有奇点构成的矩阵的1和3, 2和5, 4和6之间增加边.00100000001010000000000101000000010C%原矩B的2, 4, 6, 7, 8, 10分别对应于奇点矩阵的 1, 2, 3, 4, 5, 6顶点相对原矩阵即 2和6, 4和8, 7和10增加边,(相当于236, 4-5-8, 7-10不变)边长为原来求得的最短距离即 7,7,2. 得到新的矩阵

50、如下：inf5inf6 inf infinf inf inf inf5 inf5inf 67inf inf inf infinf5inf inf inf2inf inf inf inf6 inf inf inf3inf4 7 inf infinf 6 inf 3 inf 6 inf 4 inf inf inf 7 2 inf 6 inf inf inf 4 inf inf inf inf 4 inf inf inf 4 inf 2 inf inf inf 7 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用Fleury方法求出其欧拉回路即为所求的最正确邮差回路,文件如下:clear;w=inf 5 inf6inf inf inf inf inf inf5inf5 inf 67 inf inf inf infinf 5 inf inf inf 2 inf inf inf inf 6 inf inf inf 3 inf 4 7 inf inf inf 6 inf 3 inf 6 inf 4 inf inf inf 7 2 inf 6 inf inf inf