欧拉图在生活中的应用论文

Liaoning Normal University （2013届）

本科生毕业论文(设

题 目： 欧拉图在生活中的应用 学 院： 数学学院 专 业： 数学与应用数学 班级序号： 11班22号 学 号： 20111122060022 学生姓名： 陈旭 指导教师： 张楠

2013年5月

计)

目 录

摘要 ...................................................................... 1 Abstract .................................................................. 1 前言 ...................................................................... 2 1欧拉图问题提出的研究背景和定义 .......................................... 3

1﹒1问题提出的研究背景 ............................................... 3 1﹒2定义 ............................................................. 3 2欧拉图的判定定理和实例 .................................................. 4

2﹒1欧拉图的判定定理 ................................................. 4 2﹒2欧拉图实例 ....................................................... 5 3欧拉图的应用 ............................................................ 8

3﹒1中国邮递员问题及算法 ............................................. 8 3﹒2牛奶配送问题 .................................................... 13 参考文献 ................................................................. 17 致谢 ..................................................................... 18

i

欧拉图在生活中的应用

摘要：欧拉图起源于哥尼斯堡七桥问题，通过图中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图。欧拉图在现实生活中有着较广泛的应用。本文主要介绍了欧拉图问题提出的研究背景、相关概念和常用的判定定理、判别法及算法以及欧拉图在生活中的实际应用例子。

关键词：欧拉图；判定定理；算法；应用。

Abstract: Euler graph originated in Konigsberg seven Bridges problem, all through the picture edge once and only once traveled all the vertices in the graph of pathways called Euler path, all through the picture edge once and once traveled all vertices of Euler circuit. With Euler circuit diagram called Euler graph. Euler graph has a wide application in real life. Euler graph problem is mainly introduced in this paper puts forward the research background, related concepts and common decision theorem, Euler graph method and algorithm as well as practical application example in the life.

Key words: Euler graph; Judgment theorem; Algorithm; Application.

第1页

欧拉图在生活中的应用

前言

图论是近210年来发展十分迅速、应用比较广泛的一个新兴的数学分支，19世纪末期，图论已经用来研究电网络方程组和有机化学中的分子结构；20世纪中叶以后，借助于计算机，图论又用来求解生产管理、军事、交通运输、计算机以及通信网络等领域中的许多离散性问题，同时图论中的一些著名问题也借助于计算机科学、电子学、信息论、控制论、网络理论、社会科学和管理科学等领域中，因此受到全世界越来越广泛的重视。图论的内容十分丰富，涉及面也比较广。本文章所涉及的只是图论中的欧拉图的问题提出背景、一些基本定义、判定定理和生活中的应用。

欧拉图是由哥尼斯堡七桥问题诞生的，讲述的是：18世纪，普鲁士的哥尼斯堡城有一条贯穿全城的河流，河中有两个岛，有七座桥将两岸与岛屿及岛屿之间连接，当时当敌人们热衷于一个难题：一个散布者怎样不重复地走完七桥，最后回到出发点。这个问题困扰了人们许多年，成千上万的人试过了，但都没有成功。这个问题引起了欧拉的注意，为了寻找答案，欧拉对此问题进行观察、思考和研究，终于解决了这一难题，就是我们现在学习的欧拉图的判定方法。最后讲述了欧拉图在生活中的应用问题，是本文的重要组成部分。

运用欧拉图的相关定理来解决生活中的实际应用问题任重而道远，需要我们共同努力为国家贡献力量！

第2页

欧拉图在生活中的应用

1欧拉图问题提出的研究背景和定义

1﹒1问题提出的研究背景

18世纪，普鲁士的哥尼斯堡城有一条贯穿全城的河流（普雷格尔河），河中有两个岛，有七座桥将两岸与岛屿及岛屿之间连接，当时当敌人们热衷于一个难题：一个散布者怎样不重复地走完七桥，最后回到出发点。这个问题困扰了人们许多年，成千上万的人试过了，但都没有成功。

这个问题引起了欧拉的注意，为了寻找答案，欧拉对此问题进行观察、思考和研究，“也许并不存在这样的走法？”为了证明自己的猜想，他首先考虑到了集合中的“列举法”，但检验起来却十分麻烦，而且在同样的问题中，如果桥更多，那么“列举法”就无使用价值了，因此他放弃了这个方法，后来他改变了思考的角度，发现七桥问题仅仅涉及物体的位置关系，而与路程无关，于是他用点A、B表示岛屿，点C、D表示河的两岸，用连接两点的线表示桥，这样就可以画出如图1-1所示的无向图，这个问题就转化为“能否一笔画出该无向图且最后返回起点”。哥尼斯堡城七桥问题是否有解，就相当于这个无向图是否存在经过图中每条边一次且仅一次的简单回路。

我们知道，从某一个点出发最后又回到这个点，经过这一点的边的条数一定是偶数；经过中间的每一点，有进去的一条边，又有出来的一条边，因此，经过这些点的边的条数也是偶数。根据这个道理，我们可以看到图中经过每一点巧妙地解决了这个困扰人们多年但又十分有趣的问题。那这个方法也就成了我们现在学习的欧拉图的判定方法。

图1-1

1﹒2定义

定义1 图：图论中将图定义为一个偶对GV,E，其中V表示顶中点的集合，E是无序组集合VV的一个子集合，集合VV中的元素在E出现不止一次边的集合。分别 用VG和EG表示图G的顶点集合与边的集合。如果VG和EG都是有限集合，则称G为有限图，否则称为无限图。若VGn，则称G为n阶图。

定义1 平凡图：只有一个顶点的图叫做平凡图。 定义2 关联：一条边的端点称为与这条边关联。

定义3 连通：设u,v是图G中的两个顶点，若G中存在一条u,v道路，则称顶点u和v是连通的。

定义4 度：设G中与顶点v关联的边的数目，称为v（在G中）的度，记作dv。 定义5 回路：设G为图G中顶点与边的交替序列vi0ej1vj1ej2„ejlvil称为vi0到vil的通路，若viovil，则称通路为回路。（若的所有边各异，则称G为简单回路。）

第3页

欧拉图在生活中的应用

定义6 通过图中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图。

定义7 给定有向图D，经过D中每边一次且仅一次的有向迹称为有向欧拉图；经过D中每边一次且仅一次的有向闭迹(回路)称为有向欧拉回路。

定义8 含欧拉回路的无向连通图与含有向欧拉回路的弱连通有向图，统称为欧拉圈。 定义9 欧拉闭迹：经过图G的每条边恰好一次的闭迹。 定义10 欧拉迹：经过每条边恰好一次的迹。

定义11 桥：即去掉该边后，剩下的所有顶点将不能够连通，即无法构成连通图

2欧拉图的判定定理和实例

2﹒1欧拉图的判定定理

下面介绍欧拉图的一些判定定理：

引理：设GV,E一般图，如果它的每个顶点的度数都是偶数，则G的每条边都属于一条闭迹，因而也属于一个圈。 证明：利用下面的算法，可以找到一条包含任意指定边1x0,x1的闭迹。在该算法中，我们要构造一个顶点集W和一个边集F。 求闭迹的算法 i) 令i1

ii) 令Wx0,x1 iii) 令F1

iv) 当xix0时，执行

a) 找出一个不在F中的边i1xi,xi1。

b) 将xi1放人W中（也许xi1已在W中）。 c) 将i1放入F中。

d) 令ii1。

这样，经过i)～iii)步初始化以后，在算法中的，我们都要找到一条新边

i1xi,xi1，它邻接于最后一次放入W中的顶点xi，再将xi1和i1分别放入W和F中，并使i的值增1.重复这个过程，直到最终又到达x0为止。

假设只要xix0时，满足iv)a)的一条边i1总存在。设i的终值它为k，所产生的顶点集Wx0,x1,,xk，边的多重集F1,,k，于是，根据算法得到的1,k就是包含初始边1的一条闭迹。因此，我们只需证明：如果xix0，那么就有一个不在F中的边与xi邻接。正是在这里，用到了偶度次顶点的假设。

容易看到：算法中每步iv)的d)结束时，一般图HW,F的每个顶点都具有偶度次，只有顶点x0（它起始于奇度1）和最新加入的顶点xi（它的度数刚刚增加1）可能除外。此外，x0和xi具有偶度次，当且仅当x0xi，因此，如果xix0，则xi在一般图H中就具有奇度次。既然xi在一般图G中具有偶度次，则必存在一个还不属于F的边

i1xi,xi1与xi邻接。所以，当算法结束时，必有xkx0，从而式1,k是一条闭

迹。

由于一条闭迹中的边可以被划分为圈，所以我们完成了引理的证明。

第4页

欧拉图在生活中的应用

定理1 设G是一个连通一般图，则G中存在闭欧拉迹，当且仅当G中每个顶点的度数是偶数。

证明：我们已经观察到了：如果G中有一条闭欧拉迹，则G的每个顶点都具有偶度次。现在设G1V1,E2是一个连通一般图，且它的每个顶点都具有偶度次，我们选定G1的任意一条边1，并应用引理证明中给出的求闭迹的算法，求得一条包含边1的闭迹1。令G2V2,E2是去掉E1中属于闭迹1的边后得到的一般图，则G2的所有顶点都具有偶度次。如果E2中至少含有一条边，则由于G1的连通性，G2中至少有一条边2与闭迹1中的某个顶点z1邻接，我们对G2和边2应用算法求出一条包含边2的闭迹2。现在我们把1和2在顶点z1处拼接在一起，得到一条包含1和2的所有边的闭迹12。令G3V3,E3是E2中去掉2的边后得到的一般图，如果E3中至少含有一条边，则它必有一条边3与闭迹12中的某个顶点z2邻接，再对G3和边3应用算法，求得一条包含边3与闭迹3，又将12和3在顶点z2出拼接，得到一条包含1，2和3的所有边的闭迹123。重复上述过程，直到所有的边都包含在一条闭迹12k 中为止。因此，重复调用求闭欧拉迹的算法。

定理2 设G是一个连通的一般图，则G中存在一条开欧拉迹，当且仅当G中恰好有两个奇度顶点u和v。此外，G中任均连接意一条开欧拉迹u和v。

证明：首先，回忆定理（设G是一个一般图，则其所有顶点的度数之和d1d2dn是一个偶数，从而，其奇度顶点的个数也必为偶数。): G中奇度顶点的个数必为偶数。如果G中存在一条开欧拉迹，则它必连接G中的两个奇度顶点u和v，而G中的其他顶点必是偶度次的（因为欧拉迹每次进入并离开一个不同于u和v的顶点x时，使得与x邻接的边必成对出现）。现在假设G是连通的，且G恰好有两个奇度顶点u和v，令G是通过对G增加一条连接u和v的新边u,v而得到的一般图，则G是连通的，且此时G的所有顶点都是偶度次的，因此，由定理1，G中存在一条欧拉迹。我们可以把看作起始与顶点v，其第一条边是连接u和v的新边u,v的闭欧拉迹，从中去掉这条边，我们就得到了一条G中连接u和v的，且起始与顶点u的开欧拉迹。我们可以利用求G的一条闭欧拉迹的算法，得到求G的一个开欧拉迹的算法。

定理3 设G是一个连通一般图，并设G中奇度顶点的个数m0，则G的边可以被划分为m/2个开迹，但不能被划分为少于m/2个开迹。

定理4 有向图G是欧拉图当且仅当G是强连通的且每个顶点的入度都等于出度。 定理5 有向图G是半欧拉图当且仅当G是单向连通的，且G中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度。 定理6 G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈之并。

z1z2z1z2zk1z1z1z12﹒2欧拉图实例

例1 设k是给定正整数，由k个圈组成一个（有向或无向）图，最少要添加的几条边使之成为欧拉图？

第5页

欧拉图在生活中的应用

图2-1 解答：在无向图中，假设如果有2个圈，不重合，加上最少的边成为欧拉图，即在这2个圈之间加2条平行边（如图2所示）。因为圈中每个点的度数是2，已经符合欧拉图的条件，如果再添加边必须在一个顶点上再加两条边与其相邻的顶点连接（如图3所示）， 这样才能使之符合欧拉图的每个顶点的度均为偶数的条件。于是，可以想象，k个圈可以假设成k个点，要使k个点成为图，即在这2个圈之间加2条方向相反的边，因为圈中每个点的度数是2（1入1出），已经符合欧拉图的条件，必须在一个顶点上再加两条方向相反的边与其相邻的顶点连接，这样才能使之符合欧拉图的每个顶点的度均为偶数且出度等于入度的条件。于是，可以想象，k个圈可以假设成k个点，要使k个点成为图，那么最少必须加上k条边且方向相同才能使之成为欧拉图。

例2 验证一个连通的线的网络，能够无折回地走通时，则网络中的奇度顶点要么为0，要么为2。

解答：在计算机领域中，网络就是用物理链路将各个孤立的工作站或主机连在一起，组成数据链路，从而达到资源共享和通信的目的。网络是在物理上或和逻辑上，按一定拓扑结构连接在一起的多个结点和链路的集合。这里如果我们把工作站和主机都看做是结点，链路看做是边的话，那么连通的网络就是判断有没有欧拉通路的网络，结合欧拉图的判定定理，每个结点的度都是偶数或只有奇度顶点（其它点的度都为偶数），才能构成欧拉通路。所以一个连通的线的网络，能够无折回地走通时，网络中的奇度顶点个数要么为0，要么为2，具有可信性和可执行性。

例3 设G是欧拉图，但G不是平凡图，也不是一个环则G2 证明：只需证明G中不肯能有桥（如何证明？）

图2-2 图2-3

上图中，图2-2，图2-3两图都是欧拉图，均从A点出发，如何一次成功地走出一条欧拉回路来？

第6页

欧拉图在生活中的应用

例4 多米诺骨牌

28块，能否排成一圈使两两相邻的半边的点数相同，问是否可能？

2解答：C7728种

例5 “两只蚂蚁比赛问题”。两只蚂蚁甲、乙分别处在图G中的顶点a,b处，并设图中各边长度相等。甲提出同乙比赛：从它们所在顶点出发，走过图中所有边最后到达顶点c处。如果它们速度相同，问谁最先到达目的地？

解：图G中，有两个奇度顶点b,c，因此存在从b到c的欧拉通路，蚂蚁乙走到c只要走一条欧拉通路，边数为9，蚂蚁甲要想走完图中所有边到达c，至少要先走一条边到达b，再走一条欧拉通路，故它至少要走10条边到达c，所以乙必胜。

a(甲)b(乙) c 图2-4

例6下面图中谁是欧拉图？谁是非欧拉图但存在欧拉迹？谁是非欧拉图且不存在欧拉迹？

图2-5 图2-6 图2-7

解：图2-5是欧拉图；图2-6是非欧拉图，但存在欧拉迹；图2-7中不存在欧拉迹。 例7 证明：若G和H是欧拉图，则GH是欧拉图。 证明：首先证明：对任意uVG,vVG，有：

dudvdu,v

事实上，设z是u的任意一个邻点，一定有u,v的一个邻点z,v，反之亦然。同理，对于v的任意一个邻点w，一定有u,v的一个邻点u,w，反之亦然。即：u,v在乘积图中邻点个数等于u在G中邻点个数与v在H中邻点个数之和。 所以，G，H是欧拉图，那么GH顶点度数为偶数。 其次证明：GH是连通的。

u1,v1,u2,v2VGH

由于，G，H都是欧拉图，所以都连通。设最短的u1,u2路最短的v1,v2路分别为：

第7页

欧拉图在生活中的应用

u1x1x2xku2 v1y1y2ymv2

那么，由乘积图的定义：在乘积图中有路：

u1,v1x1,v1xk,v1u2,v1u2,y1u2,ymu2,v2

这样，我们证明了GH是连通的且每个顶点度数为偶数。即它是欧拉图。

3欧拉图的应用

3﹒1中国邮递员问题及算法

中国邮递员问题

中国邮递员问题，是我国梅谷教授于1960年首先提出而得名。设邮递员从邮局出发，遍历他所管辖的每一条街道，将信件送到目的地后返回邮局，要求所走的路径最短。当然如若他所管辖的街道构成一欧拉回路，则这欧拉回路便是所求路径。如若不然，即存在度数为奇数的顶点，必然有些街道需要多走至少1遍，这时用中国邮路问题算法可求出最短路径。

现将中国邮路问题用图论的语言描述如下：

设GV,E是连通图，而且对于所有的eE，都赋以权ce0，求从点vV出发，通过所有至少一次最后返回v点的回路C，使得ce达到最小。

不失一般性，假定图GV,E存在度数为奇数的顶点，如若不然，存在一条欧拉回路，它就是所求的邮路。我们可以设想，有些边添加若干次使得到的图GaV,Ea的所有顶点的度数均为偶数，即Ga为欧拉图，问题导致求Ga图的欧拉回路，但图Ga不再是简单图，它具有平行边，设e边重复了k2次，去掉偶数条后，仍保持各顶点的度数为偶数，即所得到的图仍是欧拉图。为使总数ce达到最小，我们不妨假定每条边

eCeC重复数目不超过1。仍使邮路达到最短，也就是要求重复边的长度达到最短。设E是所求的重复边的集合，使WEce达到最小，对于任一简单回路C，可分解为与E相交的部分ECE，及其余EC\\E。

定理7 设EE是使WEce达到最小的重复边集合，当且仅当对于Ga图的任

eE一回路C，恒有WECEWEC\\E。 证明：必要性。如若不然，假定存在C使

WECEWEC\\E，

~这意味ECE部分的权超过其余EC\\E部分的权，令EECE即

~EECE\\ECE。

~~E也可作为重复边使G图成为欧拉图。这里是对称差。显然，E可使图G的所有顶点保持其度数为偶数，由于假定

cece，

eEeECEeEC\\E故

eEcece。

~eE跟E的假设相矛盾。必要性得到了证明。

第8页

欧拉图在生活中的应用

~注意：这里E分解为与EC共同部分，还有其余部分，后者出现在E中。

充分性证明。假定存在EiE,i1,2,由Ei的边作为重复的边，满足定理的条件：

对于任一回路C有

eECEicece,i1,2，

eEC\\Ei可以证明等式

eE1cece。

eE2令EE1E2，

则图GV,E没有度数为奇数的顶点，E可分解成若干简单回路C1,C2,,Ch， 或记以

EE1E2C1C2Ch，

则有

eECiE1cece,i1,2,,h。

eECi\\E1但ECi\\E1ECiE2，故

eECiE1cece,i1,2,,h。

eECi\\E2同理

eECiE2ceceeECi\\E2eECiE1ce,i1,2,,h。

即

eECiE1ceeECiE2ce,i1,2,,h，

所以

eE1cece。

eE2充分得证。

从上定理的证明过程提供了构造中国邮路问题的算法。设已知图G中顶点的度数为奇数的点为v1,v2,,v2h。 算法

第一步：i从1到h，引从v2i1到v2i得链Pi的每条边附加一条使成为重复边。 第二步：检查图G的每条边。若添加的重复边数超过1，则出去其中偶数条，使得每条边之多有一条添加的边，且每一个顶点的度为偶数，从而得图G。图G中重复边的集合记为E0。

第三步：k0，

图3-1若Ek对于回路C有

第9页

欧拉图在生活中的应用

eEkECcece，

eEC\\Ek则作【Ek1EkEC,kk1，转图3-1】否则转图3-2。 图3-2输出Ek，Ek便是最优集。 例题：给出中国邮路问题求解的过程。

解：图3-1到图3-5给了中国邮路问题的求解过程。图3-1便是G图，其中v2,v3,v4,v5,v6,v7点是度数为奇数的点，引重复边v2,v3,v4,v5,v6,v7便得图3-2。图3-2中不存在重复边数超过1的边。 v2 1 5 2 2 v3 3 2 5 3 v1 3 v7 4 v4 v6 3 图3-1 5 v5 v2 1 5 2 4 3 2 v3 3 2 5 3 v1 v7 4 v4 3 v6 考察回路

3 图3-2 v5 C:v2v3v7v2，

由于

E0v2,v3,v4,v5v6,v7，

eE0ECeEC\\E0ce5，

ce224，

不满足定理的要求，作 得图3-3，考察3-3中的回路

E1E0EC。

第10页

欧拉图在生活中的应用

v2 1 5 2 v3 2 2 3 v1 3 v6 v7 4 5 3 图3-3 v5 3 v4 C:v4v5v6v7v4，

eE1ECce347，

eECce235， E2E1EC。

显然不满足定理的要求，作 修改图3-3得图3-4 v2 1 5 2 2 v3 3 2 5 3 v1 3 v7 4 v4 v6 3 v5 图3-4

考察回路

C:v3v7v4v3，

eE2ECce224，

eEC\\E2ce3。

v3 2 2 5 3 3 不满足定理，修改得图3-5

v2 5 1 2 v1 3 v7 4 v4 v6 图3-5 3 v5 第11页

欧拉图在生活中的应用

易知，图3-5满足定理7，故图3-5是欧拉回路。 例8 在下面欧拉图G中求一条欧拉回路。

d f h a b c e 解： d g 图3-6 i j f h a b c e g i j 图3-7

例9 某博物馆的一层布置如图2-10，其中边代表走廊，结点e是入口，结点g是礼品店，通过g我们可以离开博物馆。请找出从博物馆e进入，经过每个走廊恰好一次，最后从g处离开的路线。 d j b fi a e g c 图3-8

f 解：图中只有两个奇度顶点e和g，因此存在起点e，终点为g的欧拉迹。

为了在G中求出一条起点为e，终点为g的欧拉迹，在e和g间添加一条平行边m

第12页

欧拉图在生活中的应用

d j b fi a e g m c 图3-9 f dhgdjiejge用算法求出欧拉环游为：emgcfabchb

bhcbafcg 所以：解为：egjeijdghd

3﹒2牛奶配送问题

目前我国绝大数牛奶生产企业以人工、凭主观、靠经验对配送线路进行优化，也有少部分企业开始借助于信息技术实现配送路线的优化工作，但能够提出完整的物流配送线路优化系统的企业还非常少。而国外的一些路径优化软件由于交通规则、道路规划等各方面不符合我国国情，很难符合改革中的中国牛奶的管理流程，因此牛奶配送路径优化问题已成为制约我国牛奶物流发展的主要因素之一。

目前，国内外大多数研究很难一次形成合适的配送线路，往往需要辅助很多人工干预和调整，增加了工作的复杂性。本文将中国邮路问题引入配送路径的优化中，在邮路问题中引用指派问题来处理奇点对之间增加重复边的问题，大大简化了多奇点对之间增加重复边的繁琐性，试图寻求一种新的适合我国牛奶配送系统的路径优化方法，并力求有所突破。

牛奶配送路径优化模型

本文结合我国牛奶配送的特点，建立了市区间的牛奶配送路径优化模型，其前提条件如下：

(1)某市牛奶零售网点分布在全市各地，其总体数量大致稳定；

(2)该市根据配送辐射半径，将全市划分多个配送区域，并确定每一区域的配送中心及每个配送中心所覆盖的零售网点；

(3)零售网点的配送任务由所在区域的牛奶需求量都必须在单车车载量以内，区域内各零售网点所在道路的长度可知；

(4)配送车辆有某一区域的配送中心出发，经过该区域内各零售网点，配送完成后车辆返回该物流中心。

符号规定如下：N为某牛奶配送区域内零售网点d的个数d1,2,N；Xd表示配送路径是否经过d个零售网点；GV,E为该区域零售网点所在道路形成的边权连通无向图；V为定理交叉点的集合v0,v1,,vn，点数Vn，其中A表示该区域的牛

vi,vj，道路个数Em,i,j0,1,,n；奶配送中心；E表示G中所有道路的集合Wvi,vj的长度；vkp、vkq表示G中的某两个奇点，p,q1,2,,r；C为从牛奶配送中心出发经过每个零售网点后重新回到配送中心的一个配送路径；Lc表示配送路径C的

第13页

欧拉图在生活中的应用

总长度。

模型描述与建立

对于某一个牛奶配送区域，零售网点是固定发布在道路上的，可将配送路径必须经过零售网点的问题转化为必须经过零售网点所在道路的问题，这样如果配送车辆能以最短路线遍行零售网点所在的道路，即能完成送货任务。所以在道路vi,vj可知的边权连通无向图V,E中

目标函数为：minLc

约束条件为：XdN

该问题在本质上与中国邮递员问题是一致的，故我们把该牛奶配送最短路径问题，转化为求解网络图的中国邮递员问题。 案例应用

某市一牛奶企业的物流配送具有客户多、批量小、品种多、时间要求高的特点，该企业按照单车车载量将本市划分为多个区域，每个区域分别由该地区的配送中心来进行分配，如图1是该牛奶企业的某个配送区域，在该区域有12个零售户，则该配送区域构成如下的边权连通无向图，目前该牛奶企业在该地区的配送路线为：

AV1V2V3V10V1V10V3V4V5V6V7V8V11V12V4V12V6V7V8

V11V10V9V8V9A配送路径的长度Lc70。 6 4 V7 V6 V5

3 1 3 2 2 2 3 NV8V9V11 1 1 V10 3 V12 5 5 5 4 V4 1 1 V3 V2 1

A 2 V1 图3-10

（1） 找出奇点及奇点数

表1 各点对应的度数值 奇点 V1 V2 V3 V4 度数 3 2 3 3 V5 2 V6 3 V7 2 V8 3 V9 3 V10 4 V11 3 V12 3 A 2 共有8个奇点，分别为V1,V3,V4,V6,V8,V9,V11,V12，引重复边V1,V6,V3,V4,V8,V9V11,V12 便得图3-11。图3-11中不存在重复边数超过1的边。 （2） 考察回路

V7 3 6 V6 3 4 V5 3 V8 1 V9 1 2 2 V11 1 3 V12 5 4 V4 1 1 A 1 V10 第14页 2 5 2 V3 V2 V1 5 欧拉图在生活中的应用

图3-11

利用中国邮路算法，考察图3-11中回路

C：V1V6V12V11V10V1，

E0V1,V6,V11,V12，

eE0ECce14317，

eEC\\E0ce3115，

不满足定理的要求，作

得图3-12

考察图3-12中回路

满足定理

满足定理

E1E0EC，

E1V1,V10,V6,V12,V10,V11。 V7 6 V6 4 V53 3 3 VV11 8 2 3 V12 4 V41 V9 2 1 5 1 V31 1 V1 2 10 5 A5 V 2 V1 2图3-12 C：V8V9V10V11V8，

E2V8,V9,V10,V11，

ce112，

eE2ECce224。

eEC\\E2C:V3V4V12V11V10V3, E3V3,V4,V10,V11,

ce112，

eE3ECce34512。

eEC\\E3C：V1V10V9AV1， E4V1,V10，

ce1，

eE4ECce2215。

eEC\\E4第15页

欧拉图在生活中的应用

满足定理

C：V4V5V6V12V4, E5V6,V12,

eE5ECeEC\\E5ce3,

ce43310。

也满足定理。

在邮路图中对每个配对奇点之间按照最短路径添加重复边,此图中已没有奇点,并且满足定理7。如图3-12所示。

在图3-12中，此时配送路径C的长度Lc58Lc70，即为该配送区域的最短路径，从配送中心A出发找出欧拉回路：

AV1V2V3V10V1V10V11V12V4V3V4V5V6V12V6V7V8

V9V10V11V8V9A此回路即该配送区域内送货车辆的最短行驶路线。显然，求出的最短配送路径远远小于目前该牛奶公司的配送路径长度。考虑到现实配送过程所耗费的人员和车辆等费用后，该牛奶个数改用最短配送路径后可大大提高配送的效率，并将节省大量物流成本。 结束语

我们已经注意到：我们使用的词语—中国邮递员问题，从纯数学角度而言可能是个挺有意思的问题，但它却没有太大的实际意义，因为该问题并没有把街道的长度考虑在内，某些街道可能很长，而另一些则可能很短，如果邮递员不得不重走某些街道的话，显然选取越短的街道越好。为使该问题具有实际意义，我们应在每条边上都加上一个非负的权，于是，衡量途径时不再用它的长度（即途径中边的数目），而是用它的总权数（即途径中每条边的权数之和，某个边在途径中重复几次，该边的权就有累次几次）来衡量。实用的中国邮递员问题就是要确定一条包含每条边最少一次且总权数最小的途径，该问题从算法的角度而言也已经得到了的解决。

第16页

欧拉图在生活中的应用

参考文献

[1]屈婉玲，耿素云，张立昂，离散数学[M]. 北京：高等教育出版社， 2008. [2]卢开澄，卢华明，图论及其应用[M].北京：清华大学出版社，1998. [3]王朝瑞，图论[M]，北京：北京理工大学出版社，2004.

[4]周炳生， 高向阳， 哈密顿图和欧拉图的一种判别方法[J]. 广西科学院学报， 2006（01）. [5]王淑栋， 郑惠琴， 关于欧拉图的一个猜想的新结果[J]. 山东矿业学院学报， 1999(1). [6]陈显强，吴集林，论哈密尔顿图的判定问题[J]. 广东广播电视大学学报， 2005(1). [7]黄永华， 欧拉图与哈密顿图[J]. 唐山师专学报， 1999(2).

[8]伍庆成， 论欧拉图、哈密顿图的判定及应用[J].中国高新技术企业报，2000（2）. [9]汤泽莹，谢政， 水灾地区邮递员问题[J]. 应用数学与计算数学学报， 2000(1). [10]汤泽莹，卢汉清， 战争地区邮递员问题[J]. 应用数学与计算数学学报， 2002(1). [11]李维铮， 运筹学[M]. 北京: 清华大学出版社， 2006.

[12]徐俊明.图论及其应用（第二版）.合肥：中国科学技术大学出版社，2004. [13]王树禾.图论.北京：科学出版社，2004

[14]宋森.过七桥-欧拉-一笔画〔J〕.思维与智慧，2001.

[15]王敬庚.欧拉是怎样解决七桥问题的〔J〕.数学史话,2005. [16]马叔良、顾豫；离散数学；电子工业出版社；1997.

[17]朱怀宏；离散数学自考应试指导；南京大学出版社；2003.

[18]邵学才、蒋强荣、石嘉明等；离散数学；清华大学出版社；2001. [19]张忠志、李立明、何伟；离散数学；高等教育出版社；2004. [20]左孝凌；离散数学；经济科学出版社；2000.

[21]谢政，网络算法与复杂性理论（第二版），国防科技大学出版社，2003.

[22]蒋长浩.关于Euler图的一个特点.宁波师院学报（自然科学版）.1995，13（1）. [23]常庚哲、魏有德等.中学数学竞赛导引[M].上海：上海教育出版社，1993. [24]F.哈拉里.图论（中译本）[M].上海：上海科学技术出版社1980. [25]何尚东.逻辑学教程：第二版[M]北京：高等教育出版社，2007. [26]雷澜、李霄民.关于广义棱连通度的一个注记.西南师范大学学报（自然科学版）.2008，33（3）. [27]管梅谷.奇偶点图上作业法.数学学报，1960.3.10. [28]李玮、王雷.中国邮递员问题的DNA计算机应用，2009.

[29]曹鱼、陈传波，遗传算法求解邮递员问题的探讨[计算机与数字工程]，2000. [30]滕传琳.管理运筹学.中国铁道出版社，1990.

第17页

欧拉图在生活中的应用

致谢

走的最快的总是时间，来不及感叹，大学生活已近尾声，大学几年多的努力与付出，随着本次论文的完成，将要划下完美的句号，而于我的人生却只是一个逗号，我将面对有一次征程的开始。

几年的求学生涯在师长、亲友的大力支持下，走的辛苦却也收获满囊，在论文即将付梓之际，思绪万千，心情久久不能平静。伟人、名人为我所崇拜，可是我更急切地要把我的敬意和赞美献给一位平凡的人，我的导师张楠老师。我不是您最出色的学生，而您却是我最尊敬的老师。您治学严谨，学识渊博，思想深邃，视野雄阔，为我营造了一种良好的精神氛围。授人以鱼不如授人以渔，置身其间，耳濡目染，潜移默化，使我不仅接受了全新的思想观念，树立了宏伟的学术目标，领会了基本的思考方式，从论文题目的选定到论文写作的指导，经由您悉心的点拨，再经思考后的领悟，常常让我有“山重水复疑无路，柳暗花明又一村”。论文初稿与定稿无不凝聚着张楠老师的心血和汗水，在我的毕业论文设计期间，张楠老师为我提供了种种专业知识上的指导和一些富于创造性的建议，张楠老师一丝不苟的作风，严谨求实的态度使我深受感动，没有这样的帮助和关怀和熏陶，我不会这么顺利的完成毕业论文。在此向张楠老师表示深深的感谢和崇高的敬意！

感谢我的爸爸妈妈，焉的谖草，言树之背，养育之恩，无以回报，你们永远健康快乐是我最大的心愿。

在临近毕业之际，我还要借此机会向在这几年中给予我诸多教诲和帮助的各位老师表示由衷的谢意，感谢他们多年来的辛勤栽培。不积跬步何以至千里，各位任课老师认真负责，在他们的悉心帮助和支持下，我能够很好的掌握和运用专业知识，并在设计中得以体现，顺利完成毕业论文。

同时，在论文写作过程中，我还参考了有关的书籍和论文，在这里一并向有关的作者表示谢意。同样也得到了许多同学的宝贵建议，在此一并致以诚挚的谢意。感谢所有关心、支持、帮助过我的良师益友。

最后，向在百忙中抽出时间对本文进行评审并提出宝贵意见的各位专家表示衷心地感谢！

第18页