1.基本概念

1.1.Euler图

定义 经过的每条边的迹叫做的Euler迹；闭的Euler迹叫做Euler回路或E回路；含Euler回路的图叫做Euler图。

简单地说，Euler图就是那种能一笔从起点经过图地所有边再回到起点的图。

定理1 1.是Euler图的充分必要条件是联通且每个顶点都是偶次顶点。
2.是Euler图的充分必要条件是联通且
，是圈，

3.中有Euler迹的充要条件是联通且至多有两个顶点。

1.2.Hamilton图

定义 包含的每个顶点的轨叫做Hamilton轨；闭的Hamilton轨叫做Hamilton圈或H圈；含Hamilton圈的图叫做Hamilton图。

直观的讲，Hamilton图就是从一顶点出发每顶点都只经过一次再回到起点的图。

1.3.Euler图和Hamilton图的区别

都是含有一个圈，但是Euler图的关键词是“边”，它要经过该图中的每一条边。而Hamilton图的关键词是"顶点"只要经过每个顶点就行了，也就是说，Euler图的要求更高。

2.Euler回路的Fleury算法

1.，令。
2.假设迹已经选定，那么按下列方法从中选取边:
(1)和相关联；
(2)除非没有别的边可选择，否则不能是的割边（割边是一条删除后使连通图不再联通的边）。
3.当第2步不能再执行时，算法停止。

3.应用

3.1.邮递员问题

一位邮递员从邮局选好邮件去投递，然后返回邮局，当然他必须经过他负责投递的每条街道至少一次，为他设计一条投递路线，使得他行程最短。

上述中国邮递员问题的数学模型是：在一个赋权连通图上求一个含所有边的回路，且使此回路的权最小。

显然，若此连通赋权图是 Euler 图，则可用 Fleury 算法求 Euler 回路，此回路即为所求。

若是非Euler图，则有以下算法：

设是联通赋权图
1.求
2.对每对顶点，求（是和的距离，可用最短路问题中的算法来求出）
3.构造完全赋权图，以为顶点集，以为边的权。
4.求中的最小完美对集。
5.求中边的端点之间的在中的最短轨。
6.在5中求得的每条最短轨上每条边添加一条等权的所谓“倍边”（即共端点共权的边）。
7.在6中所得的图中求Euler回路即是邮递员问题的解。

3.2.旅行商问题

一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这个问题称为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的Hamilton 圈。称这种圈为最优圈。与最短路问题及连线问题相反，目前还没有求解旅行商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。

一个可行的方法是首先求一个Hamilton圈C，然后适当修改C得到具有更小权的另一个Hamilton圈，修改的方法叫做改良圈算法。

设初始圈
1.对于，构造新的Hamilton图：

它是由C中删去边和，添加边和得到的。若则以代替，称为圈的改良圈。
2.转1，直到无法进行，停止。

这个算法得到的结果几乎肯定不是最优的，为了得到更高的精确度，可以选择不同的初始圈，重复几次算法，以求得较准确的结果。

例1 从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)
五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之
间的航线距离如表。

利用改良圈算法编写Matlab程序如下：

function main
clc,clear
global a
a=zeros(6);
a(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;
a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;
a(3,4)=36;a(3,5)=68;a(3,6)=68; a(4,5)=51;a(4,6)=61;
a(5,6)=13; a=a+a'; L=size(a,1);
c1=[5 1:4 6];
[circle,long]=modifycircle(c1,L);
c2=[5 6 1:4];%改变初始圈，该算法的最后一个顶点不动
[circle2,long2]=modifycircle(c2,L);
if long2<long
    long=long2;
    circle=circle2;
end
circle,long
%*******************************************
%修改圈的子函数
%*******************************************
function [circle,long]=modifycircle(c1,L);
global a
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
    end
end
long=a(c1(1),c1(L));
for i=1:L-1
    long=long+a(c1(i),c1(i+1));
end
circle=c1;