行遍性问题
1,欧拉图连通图G(V,E)中，若从某个顶点出发，经过有限条边（这些边构成的子集记为）、有限个顶点（这些点构成的子集记为），又回到了出发点，且整个行进过程中，每条边、每个顶点都没有被重复经过，则称子图是一个回路（或称：一个圈）.
性质：若图中边的个数不小于顶点个数，则必有回路连通图G(V,E)中，若从某个顶点出发，G的每条边恰好经过一次，又可回到出发点，则称该路径为欧拉路，称该图为欧拉图.
定理1 对于连通图G(V,E)，下面三条相互等价：
(1) G是一个欧拉图；
(2) G的每个顶点的次数都是偶数；
(3) 边集E可划分成多个子集（子集之间两两不相交，全体子集之并等于E），使得每个子集都单独构成一个回路.
证明 ：存在欧拉路C，考虑任一顶点v，C每次经过v时，总是既有来边、也有去边，与v关联的每条边都要被C经过一次，所以与v关联的边数（即：v的次数）必为偶数。
：每个顶点次数均为偶数，根据“顶点次数之和等于二倍的边数”得，边数不小于顶点个数，G必有回路，设是一个回路。考虑构成的子图，其顶点均为偶次，故必有回路。依次类推，因G是有限图，故可得有限个回路，使得,
：已知G是由若干个回路合并而成。选定一个顶点作为出发点，第一步(即第一条边)必在某个回路上，该回路记为，沿前进，若某个顶点处与另一回路相交，则记新回路为，并立即沿走，,不失一般性，设你正沿着走，在某个点处又与别的回路相交，先判断该回路是不是其中一，若是则不管，若不是则记新回路为并沿着它走,按上述规则就可以走出一条欧拉路,证毕.
2,中国邮递员问题问题：邮递员发送邮件，从邮局出发，辖区范围内的每条街道经过至少一次，回到邮局。确定路线，使总路程最短。
建模：街道==边；街道长==权；街道交叉口==顶点；邮局==顶点；辖区==赋权连通图G,
下面分三种情况：
（1）G的顶点都是偶次
此时，G是欧拉图，只需求出一个欧拉路即可，用Fleury算法：
定义：连通图的任一条边，若删除该边后使得图不再连通，则称该边为一条割边。
Fleury思路：每当要走一条边之前，先判断，在全体未被走过的边构成的子图中，该边是否为割边，若是则不走。
（2）G只有两个顶点是奇次先求那两个奇次顶点之间的最短路(用Dijkstra算法)，该路记为P,将P加入G（相当于在G中又适当增加了一些边），构成新的图，新图必为欧拉图，用（1）的方法求出一个欧拉路作为行进路线即可。
（3）G的奇次顶点个数大于2
因任何一个图的奇次顶点个数必是偶数，故可将奇次顶点两两配对。我们的目标是：适当配对，使得每对顶点之间的最短路长之和达到最小。将这些路加入G构成新欧拉图，用（1）的方法求出一个欧拉路作为行进路线即可。
例：求最佳邮递路线，G(V,E),V={},
E={}
解：4个顶点是奇次，先求他们之间的最短路
再求这4个点之间的最佳配对，当4与7配对、8与9配对时，距离之和达到最小5+3=8.
在G中添加路径与，形成一个欧拉图，该图的任意一条欧拉路都是最佳邮递路线。
题：求最佳邮递路线
3 2 3
4
3
4
1
2 2
3
3 3
1
3 2 3
3,推销员问题流动推销员需要访问某地区的所有城镇，最后回到出发点．问如何安排旅行路线使总行程最小．这就是推销员问题最佳推销员回路问题解法：由给定的图G=(V,E)构造一个以V为顶点集的完备图G’=(V,E’)，E’的每条边(x,y)的权等于顶点x与y在图中最短路的权．
例 对一个完备图，用二边逐次修正法求最佳推销员回路 （见文件“第9讲 行遍性问题.ppt”）
clear
n=6;bbb=0;
a=[0,56,35,2,51,60;
0,0,21,57,78,70;
0,0,0,36,68,68;
0,0,0,0,51,61;
0,0,0,0,0,13
0,0,0,0,0,0];
for i=2:n
for j=1:i-1
a(i,j)=a(j,i);
end
end
a(n,n+1)=a(n,1);b=a;cx=1:n+1;cx1=1:n+1;
while bbb==0
bbb=1;
for j=3:n
for i=1:j-2
if a(i,i+1)+a(j,j+1)>a(i,j)+a(i+1,j+1)
bbb=0;
for k=i+1:j
b(k,:)=a(j+i+1-k,:);
end
a=b;
for l=i+1:j
b(:,l)=a(:,j+i+1-l);
end
a=b;a(n,n+1)=a(n,1);xb=[1:i,j:-1:i+1,j+1:n+1];
for ii=1:n+1
kk=xb(ii);cx1(ii)=cx(kk);
end
cx=cx1;
i=j-2;j=n;
end
end
end
end
cx,a(1:n,1:n)
执行结果：
cx =
1 4 5 6 2 3 7
ans =
0 2 51 60 56 35
2 0 51 61 57 36
51 51 0 13 78 68
60 61 13 0 70 68
56 57 78 70 0 21
35 36 68 68 21 0
例：求最佳推销员回路.
解：邻接矩阵
步1：在原来9个顶点的基础上构造一个完备图，每条边的权等于“与它关联的两顶点之间”在原图中的最短路权．
记C1=C，做递推计算Ck=Ck-1C，k=2,3,4,……，（这里的乘法是第i行与第j列之元素对应向加之最小值。）
程序清单：
clear
c=inf*ones(8,8);
for i=1:8
c(i,i)=0;
end
c(1,2)=2;c(1,3)=1;c(1,4)=8;c(2,4)=6;c(2,5)=1;c(3,4)=7;c(3,7)=9;c(4,5)=5;c(4,6)=1;c(4,7)=2;c(5,6)=3;c(5,8)=9;c(6,7)=4;c(6,8)=6;c(7,8)=3;
for i=1:7
for j=i+1:8
c(j,i)=c(i,j);
end
end
d=c,
for xh=1:10
for i=1:8
for j=1:8
a(i,j)=min(d(i,:)+c(:,j)');
end
end
xhcs=xh+1;d=a;
end
a=d
执行结果：
a =
0 2 1 7 3 6 9 12
2 0 3 5 1 4 7 10
1 3 0 7 4 7 9 12
7 5 7 0 4 1 2 5
3 1 4 4 0 3 6 9
6 4 7 1 3 0 3 6
9 7 9 2 6 3 0 3
12 10 12 5 9 6 3 0
这就是所求完备图的邻接矩阵。
步2：针对完备图，用二边逐次修正法求出最佳推销员回路。
（续前一个程序）
n=8;bbb=0;
a(n,n+1)=a(n,1);b=a;cx=1:n+1;cx1=1:n+1;
while bbb==0
bbb=1;
for j=3:n
for i=1:j-2
if a(i,i+1)+a(j,j+1)>a(i,j)+a(i+1,j+1)
bbb=0;
for k=i+1:j
b(k,:)=a(j+i+1-k,:);
end
a=b;
for l=i+1:j
b(:,l)=a(:,j+i+1-l);
end
a=b;a(n,n+1)=a(n,1);xb=[1:i,j:-1:i+1,j+1:n+1];
for ii=1:n+1
kk=xb(ii);cx1(ii)=cx(kk);
end
cx=cx1;
i=j-2;j=n;
end
end
end
end
cx,a(1:n,1:n)
执行结果：
cx = 1 3 8 7 4 6 5 2 9
即，最佳推销员路线是：
u0---u2---u7---u6---u3---u5---u4---u1---u0.
ans =
0 1 12 9 7 6 3 2
1 0 12 9 7 7 4 3
12 12 0 3 5 6 9 10
9 9 3 0 2 3 6 7
7 7 5 2 0 1 4 5
6 7 6 3 1 0 3 4
3 4 9 6 4 3 0 1
2 3 10 7 5 4 1 0
即，路线长度是：1+12+3+2+1+3+1+2 == 25,完毕。
1,欧拉图连通图G(V,E)中，若从某个顶点出发，经过有限条边（这些边构成的子集记为）、有限个顶点（这些点构成的子集记为），又回到了出发点，且整个行进过程中，每条边、每个顶点都没有被重复经过，则称子图是一个回路（或称：一个圈）.
性质：若图中边的个数不小于顶点个数，则必有回路连通图G(V,E)中，若从某个顶点出发，G的每条边恰好经过一次，又可回到出发点，则称该路径为欧拉路，称该图为欧拉图.
定理1 对于连通图G(V,E)，下面三条相互等价：
(1) G是一个欧拉图；
(2) G的每个顶点的次数都是偶数；
(3) 边集E可划分成多个子集（子集之间两两不相交，全体子集之并等于E），使得每个子集都单独构成一个回路.
证明 ：存在欧拉路C，考虑任一顶点v，C每次经过v时，总是既有来边、也有去边，与v关联的每条边都要被C经过一次，所以与v关联的边数（即：v的次数）必为偶数。
：每个顶点次数均为偶数，根据“顶点次数之和等于二倍的边数”得，边数不小于顶点个数，G必有回路，设是一个回路。考虑构成的子图，其顶点均为偶次，故必有回路。依次类推，因G是有限图，故可得有限个回路，使得,
：已知G是由若干个回路合并而成。选定一个顶点作为出发点，第一步(即第一条边)必在某个回路上，该回路记为，沿前进，若某个顶点处与另一回路相交，则记新回路为，并立即沿走，,不失一般性，设你正沿着走，在某个点处又与别的回路相交，先判断该回路是不是其中一，若是则不管，若不是则记新回路为并沿着它走,按上述规则就可以走出一条欧拉路,证毕.
2,中国邮递员问题问题：邮递员发送邮件，从邮局出发，辖区范围内的每条街道经过至少一次，回到邮局。确定路线，使总路程最短。
建模：街道==边；街道长==权；街道交叉口==顶点；邮局==顶点；辖区==赋权连通图G,
下面分三种情况：
（1）G的顶点都是偶次
此时，G是欧拉图，只需求出一个欧拉路即可，用Fleury算法：
定义：连通图的任一条边，若删除该边后使得图不再连通，则称该边为一条割边。
Fleury思路：每当要走一条边之前，先判断，在全体未被走过的边构成的子图中，该边是否为割边，若是则不走。
（2）G只有两个顶点是奇次先求那两个奇次顶点之间的最短路(用Dijkstra算法)，该路记为P,将P加入G（相当于在G中又适当增加了一些边），构成新的图，新图必为欧拉图，用（1）的方法求出一个欧拉路作为行进路线即可。
（3）G的奇次顶点个数大于2
因任何一个图的奇次顶点个数必是偶数，故可将奇次顶点两两配对。我们的目标是：适当配对，使得每对顶点之间的最短路长之和达到最小。将这些路加入G构成新欧拉图，用（1）的方法求出一个欧拉路作为行进路线即可。
例：求最佳邮递路线，G(V,E),V={},
E={}
解：4个顶点是奇次，先求他们之间的最短路
再求这4个点之间的最佳配对，当4与7配对、8与9配对时，距离之和达到最小5+3=8.
在G中添加路径与，形成一个欧拉图，该图的任意一条欧拉路都是最佳邮递路线。
题：求最佳邮递路线
3 2 3
4
3
4
1
2 2
3
3 3
1
3 2 3
3,推销员问题流动推销员需要访问某地区的所有城镇，最后回到出发点．问如何安排旅行路线使总行程最小．这就是推销员问题最佳推销员回路问题解法：由给定的图G=(V,E)构造一个以V为顶点集的完备图G’=(V,E’)，E’的每条边(x,y)的权等于顶点x与y在图中最短路的权．
例 对一个完备图，用二边逐次修正法求最佳推销员回路 （见文件“第9讲 行遍性问题.ppt”）
clear
n=6;bbb=0;
a=[0,56,35,2,51,60;
0,0,21,57,78,70;
0,0,0,36,68,68;
0,0,0,0,51,61;
0,0,0,0,0,13
0,0,0,0,0,0];
for i=2:n
for j=1:i-1
a(i,j)=a(j,i);
end
end
a(n,n+1)=a(n,1);b=a;cx=1:n+1;cx1=1:n+1;
while bbb==0
bbb=1;
for j=3:n
for i=1:j-2
if a(i,i+1)+a(j,j+1)>a(i,j)+a(i+1,j+1)
bbb=0;
for k=i+1:j
b(k,:)=a(j+i+1-k,:);
end
a=b;
for l=i+1:j
b(:,l)=a(:,j+i+1-l);
end
a=b;a(n,n+1)=a(n,1);xb=[1:i,j:-1:i+1,j+1:n+1];
for ii=1:n+1
kk=xb(ii);cx1(ii)=cx(kk);
end
cx=cx1;
i=j-2;j=n;
end
end
end
end
cx,a(1:n,1:n)
执行结果：
cx =
1 4 5 6 2 3 7
ans =
0 2 51 60 56 35
2 0 51 61 57 36
51 51 0 13 78 68
60 61 13 0 70 68
56 57 78 70 0 21
35 36 68 68 21 0
例：求最佳推销员回路.
解：邻接矩阵
步1：在原来9个顶点的基础上构造一个完备图，每条边的权等于“与它关联的两顶点之间”在原图中的最短路权．
记C1=C，做递推计算Ck=Ck-1C，k=2,3,4,……，（这里的乘法是第i行与第j列之元素对应向加之最小值。）
程序清单：
clear
c=inf*ones(8,8);
for i=1:8
c(i,i)=0;
end
c(1,2)=2;c(1,3)=1;c(1,4)=8;c(2,4)=6;c(2,5)=1;c(3,4)=7;c(3,7)=9;c(4,5)=5;c(4,6)=1;c(4,7)=2;c(5,6)=3;c(5,8)=9;c(6,7)=4;c(6,8)=6;c(7,8)=3;
for i=1:7
for j=i+1:8
c(j,i)=c(i,j);
end
end
d=c,
for xh=1:10
for i=1:8
for j=1:8
a(i,j)=min(d(i,:)+c(:,j)');
end
end
xhcs=xh+1;d=a;
end
a=d
执行结果：
a =
0 2 1 7 3 6 9 12
2 0 3 5 1 4 7 10
1 3 0 7 4 7 9 12
7 5 7 0 4 1 2 5
3 1 4 4 0 3 6 9
6 4 7 1 3 0 3 6
9 7 9 2 6 3 0 3
12 10 12 5 9 6 3 0
这就是所求完备图的邻接矩阵。
步2：针对完备图，用二边逐次修正法求出最佳推销员回路。
（续前一个程序）
n=8;bbb=0;
a(n,n+1)=a(n,1);b=a;cx=1:n+1;cx1=1:n+1;
while bbb==0
bbb=1;
for j=3:n
for i=1:j-2
if a(i,i+1)+a(j,j+1)>a(i,j)+a(i+1,j+1)
bbb=0;
for k=i+1:j
b(k,:)=a(j+i+1-k,:);
end
a=b;
for l=i+1:j
b(:,l)=a(:,j+i+1-l);
end
a=b;a(n,n+1)=a(n,1);xb=[1:i,j:-1:i+1,j+1:n+1];
for ii=1:n+1
kk=xb(ii);cx1(ii)=cx(kk);
end
cx=cx1;
i=j-2;j=n;
end
end
end
end
cx,a(1:n,1:n)
执行结果：
cx = 1 3 8 7 4 6 5 2 9
即，最佳推销员路线是：
u0---u2---u7---u6---u3---u5---u4---u1---u0.
ans =
0 1 12 9 7 6 3 2
1 0 12 9 7 7 4 3
12 12 0 3 5 6 9 10
9 9 3 0 2 3 6 7
7 7 5 2 0 1 4 5
6 7 6 3 1 0 3 4
3 4 9 6 4 3 0 1
2 3 10 7 5 4 1 0
即，路线长度是：1+12+3+2+1+3+1+2 == 25,完毕。
