【数学建模算法】(11)图的应用：Euler图和Hamilton

2019-08-13 本文已影响0人热爱学习的高老板

1.基本概念

1.1.Euler图

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

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

定理1 1. $G$ 是Euler图的充分必要条件是 $G$ 联通且每个顶点都是偶次顶点。
2. $G$ 是Euler图的充分必要条件是 $G$ 联通且
$G=\bigcup_{i=1}^{d} C_{i}$ ， $C_{i}$ 是圈，
$E\left(C_{i}\right) \cap E\left(C_{j}\right)=\Phi(i \neq j)$
3. $G$ 中有Euler迹的充要条件是 $G$ 联通且至多有两个顶点。

1.2.Hamilton图

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

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

1.3.Euler图和Hamilton图的区别

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

2.Euler回路的Fleury算法

1. $\forall v_{0} \in V(G)$ ，令 $W_{0}=v_{0}$ 。
2.假设迹 $W_{i}=v_{0} e_{1} v_{1} \cdots e_{i} v_{i}$ 已经选定，那么按下列方法从 $E-\left\{e_{1}, \cdots, e_{i}\right\}$ 中选取边 $e_{i+1}$ :
(1) $e_{i+1}$ 和 $v_{i}$ 相关联；
(2)除非没有别的边可选择，否则 $e_{i+1}$ 不能是 $G_{i}=G-\left\{e_{1}, \cdots, e_{i}\right\}$ 的割边（割边是一条删除后使连通图不再联通的边）。
3.当第2步不能再执行时，算法停止。

3.应用

3.1.邮递员问题

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

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

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

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

设 $G$ 是联通赋权图
1.求 $V_{0}=\{v | v \in V(G), d(v)=1(\bmod 2)\}$
2.对每对顶点 $u, v \in V_{0}$ ，求 $d(u,v)$ （ $d(u,v)$ 是 $u$ 和 $v$ 的距离，可用最短路问题中的算法来求出）
3.构造完全赋权图 $K_{\left.\right|_{V_{0}} |}$ ，以 $V_{0}$ 为顶点集，以 $d(u,v)$ 为边 $uv$ 的权。
4.求 $K_{\left|V_{0}\right|}$ 中的最小完美对集 $M$ 。
5.求 $M$ 中边的端点之间的在 $G$ 中的最短轨。
6.在5中求得的每条最短轨上每条边添加一条等权的所谓“倍边”（即共端点共权的边）。
7.在6中所得的图中求Euler回路即是邮递员问题的解。

3.2.旅行商问题

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

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

设初始圈 $C=v_{1} v_{2} \cdots v_{n} v_{1}$
1.对于 $1<i+1<j<n$ ，构造新的Hamilton图：
$C_{y}=v_{1} v_{2} \cdots v_{i} v_{j} v_{j-1} v_{j-2} \cdots v_{i+1} v_{j+1} v_{j+2} \cdots v_{n} v_{1}$
它是由C中删去边 $v_{i} v_{i+1}$ 和 $v_{j} v_{j+1}$ ，添加边 $v_{i} v_{j}$ 和 $v_{i+1} v_{j+1}$ 得到的。若 $w\left(v_{i} v_{j}\right)+w\left(v_{i+1} v_{j+1}\right)<w\left(v_{i} v_{i+1}\right)+w\left(v_{j} v_{j+1}\right)$ 则以 $C_{i j}$ 代替 $C$ ， $C_{i j}$ 称为圈 $C$ 的改良圈。
2.转1，直到无法进行，停止。

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

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

	伦敦(L)	墨西哥(M)	纽约(N)	巴黎(Pa)	北京(Pe)	东京(T)
伦敦(L)		56	35	21	51	60
墨西哥(M)	56		21	57	78	70
纽约(N)	35	21		36	68	68
巴黎(Pa)	21	57	36		51	61
北京(Pe)	51	78	68	51		13
东京(T)	60	70	68	61	13

利用改良圈算法编写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;