离散数学之欧拉图与汉密尔顿图.doc

离散数学之欧拉图与汉密尔顿图在生活中的应用 离散数学是以数学的方法研究离散体的结构特征、相互关系以及相互运算规律的学科。经过一学期的学习，我对离散数学的命题逻辑、谓词逻辑、集合与关系、代数结构以及图论都有所了解。相对而言，我对图论这章，特别是特殊树：欧拉图与汉密尔顿图的内容比较感兴趣，所以我本人就的特殊图对所学做一小总结。现实世界中许多状态是由图形来描述的。从图的结构、图的分类以及对土的不同操作要求进行综合讨论，将得出不同特征的特殊图。1736年瑞士数学家列昂哈德欧拉发表了图论的的一篇论文“哥尼斯堡七桥问题”（其中七桥问题抽象为无向图）并在论文中提出了一条简单的准则，确定了哥尼斯堡七桥问题是不能解的，即不可能得出一条路径走完七桥，不准重复，再回到原点。在讨论七桥问题先给定有关基本概念：（1）欧拉路：给定无孤立节点的图G（可以是无向图，也可以是有向图），若存在一条路径，经过图中的每条边一次且仅一次，则称这条路为欧拉路。（2）欧拉图：若存在一条回路，经过图中每条边一次且仅一次，回到起点，则称该回路为欧拉回路，具有欧拉回路的图称为欧拉图。七桥问题的核心是一笔画原理，对满足下列两个要求的图就可以一笔画出：i.首先是连通图；ii.其次奇点个数为0或2，当且仅当奇点个数为0时，始点和终点重合，形成的一笔画称为欧拉回路，而当奇点个数为2时，形成的一笔画称为欧拉迹。我们知道，对于可一笔画出的图，首先必须是连通的；其次对于图中的某点，如果不是始点或终点，那么它必有进有出，即交汇于此点的弧线总是成双成对的，此点必定是偶点。如图，七桥问题的图的奇点的个数为4，这表明它不是欧拉回路，也不是欧拉迹，因而，不论始点和终点是否重合都不可能找到一条经过七座桥且每座桥只走一次的路线！随着图论的进一步发展，欧拉回路问题也有所拓广。一笔画问题在实际问题中也有所应用。例如，1962年由管梅谷提出的所谓“中国邮路问题”：一个邮递员从邮局出发，在所分管的区域内走遍所有街道，将邮件送到每个收件人手中，最后又回到邮局。如何计划投递路线，使走的全程路径最短？将上述问题加以抽象：（1）关心的是每条街走到，换句话说，必须经过每条边，仅关心边的条数。（2）若图的结构满足欧拉回路的条件，则任何一条欧拉回路均可以，且全程路径长度是一样的。因为走遍所有的边且仅一次所以各边权值相加就是总路径长。（3）当图的路径不满足欧拉图的条件时，而每条边走到，还要回到出发点，这时不得不重复某条边，使其回到出发点。那么选择哪条路径是加上重复边之后的总路长最短呢？中国邮路问题就是在带权图中寻求一条回路，必须经过所有的边，虽有时不得不允许重复某些边，但要求总路径长度最短。这个问题事实上是一个典型的优化问题。最直观的做法是将图中的某些边复制成两条边，然后在所得的图中确定一条欧拉回路，这就是问题的解。下面分析下问题：由于网络的奇点必定成双，又图中奇点有6个，根据一笔画原理，此图不存在欧拉回路，则必须通过添加弧线，使每个顶点均变成偶点，同时考虑添加的弧线长度总 和最短才满足要求。显然两奇点间可直接添弧一条；奇点与偶点间添弧一条且此偶点还须与另一奇点添弧一条；两偶点间不必添弧。 添弧时应注意：（1）不能出现重迭添弧。重迭添弧应成对抹去，这样并不改变每一点的奇偶性；（2）每一个圈上的添弧总长不能超过圈长一半。否则应将此圈上的原添弧抹去，而在此圈上原没有添弧的路线上加添弧，这样也不改变每一点的奇偶性。注意了（1）、（2），既保证了不改变每点奇偶性，又保证了添弧总长最短。 现在我们看邮递员的投邮路线，如图1。添弧后的新图形已是不含奇点的脉胳，根据一笔画原理，这个脉胳的全部弧线可构成一条欧拉回路。对照（1）、（2）可 知，图中添弧总长不是最短，必须调整。显然在ABJKHI圈中，添弧总长超过了该圈长一半。调整后，如图2。此时，添弧不重迭并且每一个圈上的添弧总 长都不超过本圈长的一半。另外，每点奇偶性相对于图1没有改变，全是偶点。全部弧线仍可构成一条欧拉回路，并且这条路线才是最短投邮路线。因此，邮递员的 投邮路线并非最短。 根据以上分析，最短投邮路线可设计为：KHGFEDCBAIHIJBJDEKJK或KJKHGFEDCBAIHIJBJDEK等等。此时，最短路线比邮递员路线少0.8 华里。由上述问题也可引出一系列类似问题，如道路管理员从A点出发，经过他所管辖的所有道路，这些道路分布在九个点之间，现在我们把所有各点之间的道路长度都注在图中，请你设计出经过所有道路的最短路线。这一问题的求解就较为简单，可按上述方法求的最短路线为：ABGHBCHCDHIDEIEFIGFAG与欧拉图非常类似的问题是汉密尔顿图的问题。汉密尔顿图主要是访问图中的所有节点且只访问一次，允许有的边没访问到。它是由英国数学家汉密尔顿于1859年提出的周游世界问题。他用一个正12面体的20个顶点代表世界上20个大城市，每条棱表示城市间的一条路线，要求游戏者从任何一点出发访问每一节点一次且仅一次，最后回到出发点 将上述问题转化为图论的形式语言描述为：给定图G，若存在一条路经过图中的每一节点且仅一次，则称这条路为汉密尔顿路。若存在一条回路经过图中每一节点且仅一次，则称该路为汉密尔顿回路，具有汉密尔顿回路的图称为汉密尔顿图。判断汉密尔顿图是比较困难的，到目前为止还没有找到一个判定汉密尔顿图的充分必要条件，只能分别给出一些充分条件和必要条件：(1) 设无向图G=，对任意V1V，则W(GV1)|V1|，其中W(GV1)是（GV1）中连通分支数(必要条件)若此条件不满足，即V1V，使得W(GV!)|V1|，则G一定不是汉密尔顿图(非汉密尔顿图的充分条件)所以，可以利用此条件来说明某些图不是汉密尔顿图(2) 在无向简单图G=中|V|3，任意不同结点，则G是汉密尔顿图(充分条件)(3) 有向完全图D, 若，则图D是汉密尔顿图. (充分条件)关于汉密尔顿图的应用典型问题是旅行商问题：有n个城市，其中任意两城市之间都有道路，一个旅行推销员要去n个城市售货。从某一城市出发，顺序走遍其余n-1个城市，最后回到出发的城市。试问：如何经过n个城市，使其所走的路线长度最短？ 该问题经过抽象转化为图论问题：（1）n个城市即为图中的n个节点。（2）其中任意两城市之间有道路即为两节点可达。（3）该无向图为边带权的网络，若两节点间有连线，则边的权值为给定的数据；若两节点之间没有连线则边的权值为。（4）求推销员的最短路径化为求带权无向完全图G所有汉密尔顿图回路中最短的那条路径。 最直截了当的求解旅行商问题的方法是检查所有可能的汉密尔顿回路并且挑选出总权值最小的一条回路。若在图中有n个城市，则为了求解这个问题，得检查多少条回路？一旦选定了出发点，需要检查的不同的汉密尔顿回路就有（n-1）！2条，因为第二个顶点有n-1种选择，第三个顶点有n-2种选择，依此类推。因为可以用相反顺序来经过一条汉密尔顿回路，所以最后的结果是（n-1）！2而不是（n-1）！当有许多需要访问的城市时，解决旅行商问题的可行方法是近似方法。所谓近似方法就是这样的方法，它们不必产生精确解，取而代之的是保证产生接近精确解的近似解。即它们可能产生 总权值为的汉密尔顿回路，使得，其中是精确解的总权值，而c是一个常数。例