资源描述：
《图论与网络模型_中国邮递员问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、图论中的图是由点和点与点之间的线所组成的。通常，我们把点与点之间不带箭头的线叫做边，带箭头的线叫做弧。如果边[vi,vj]∈E，E是边集合，那么称vi,vj是边的端点，或者称vi,vj是相邻的。如果一个图G中，一条边的两个端点是相同的，那么称为这条边是环。如果两个端点之间有两条以上的边，那么称为它们为多重边。一个无环，无多重边的图标为简单图。一个无环，有多重边的图标图称为多重图。以点v为端点的边的个数称为点v的度，度为零的点称为弧立点。度为1的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点。度为
2、偶数的点称为偶点。链：由两两相邻的点及其相关联的边构成的点边序列；如：v0,e1,v1,e2,v2,⋯⋯,vn−1,en,vn；v0,vn分别为链的起点和终点。vi代表点，ei代表边。简单链：链中所含的边均不相同。初等链：链中所含的点均不相同，也称通路。回路：若v0≠vn，则称该链为开链，否则称为闭链或回路。圈：除起点和终点外，链中所含的点均不相同的回路。连通图：图中任意两点之间均至少有一条通路，否则称作不连通图。设有一个连通多重图G，如果在G中存在一条链，经过G的每条边一次且仅一次，那么这条链叫做欧拉链
3、。如在G中存在一个简单圈，经过G的每条边一次，那么这个圈叫做欧拉圈。一个图如果有欧拉圈，那么这个图叫做欧拉图。欧拉图就是从一顶点出发，每边恰好通过一次能回到出发点的那种图，即不重复地行遍所有边再回到出发点。比如哥尼斯堡七桥问题，欧拉把它抽象成具有四个项点，并且都是奇点的形状。如下左图。很明显，一个漫步者不可能不重复的走完七座桥，并最终回到原出发地。欧拉把七桥问题转化成连通网络能否一笔画的问题。一笔画问题：从某一点开始画画，笔不离纸，各条线路仅画一次，最后回到原来的出发点。下右图，仅有两个奇点，可以一笔画出
4、。它是一条欧拉链。Cv1v3v5ABDv2v4v6无向连通图的割点（关键点）是指：删除该结点以及与其相连的边之后，无向图不再连通，下图中割顶有：1,2,5,9。无向连通图的桥是指：删除该边(i,j)后，点i和j不再连通，下图的桥有(1,3)，(1,2)，(5,6)，(9,7)。邮递员问题一位邮递员从邮局选好邮件去投递，然后返回邮局，他必须经过由他负责投递的每条街道至少一次，为这位邮递员设计一条投递线路，使其耗时最少。用图的语言来描述，就是给定一个连通图G，在每条边e上有一个非负的权w(e)，要寻求一个回路
5、W，经过G的每条边至少一次，并且回路W的总权数最小。∑w(e)=mine∈W如果G是欧拉图，则所求的W就是一条欧拉回路。由于这个问题是我国菅梅谷同志于1962年首先提出来的，因此国际上长称它为中国邮递员问题。求无奇点连通图的中国邮递员问题的算法(Fleury算法)就是求欧拉回路。算法思想：“过河拆桥，尽量不走独木桥”。例如，下图是欧拉图，设从v1开始，寻找一条欧拉回路，如果开始三步是v1v3v2v1，那么就失败了，因为回到v1之后发现左侧的v3上的边还没有用过，而v1的关联边已全用过，不能从v1再去通过左
6、侧那些未用过的边了（注意每边只能用一次）。究其失败的原因，是因为用了v1v3边之后，在未用过的边们导出的子图上，v2v3是桥，提前过桥v2v3的后果是断了去左侧v3的后路。这里的教训是，非必要时，不要通过未用过的边的导出子图的桥，根据这一思路，Fleury设计了如下求欧拉回路的有效算法，代号FE算法：（1）任取v0∈V(G)，令W0=v0。V(G)是点集合。（2）设欧拉链Wi=v0v1v2⋯vi已选定，则从E(G)-E(W)中选一条边ei+1，使得ei+1与vi相关联，且非必要时，ei+1不要选G-E(W
7、)的桥。（3）反复执行（2），直至每条边e∈E(G)皆入选为止。E(G)是边集合。FE算法是有效算法，其时间复杂度是Ο(
8、E(G)
9、)。用FE算法在上图中可选得欧拉回路：W=v1v3v4v5v6v7v3v5v7v4v6v3v2v1求有奇点连通图的中国邮递员问题的算法●管梅谷首先提出的方法是奇偶点图上作业法（1962年）●Edmonds，Johnson（1973年）给出有效算法。Edmonds-Johnson算法有奇点的中国邮路问题，这种情形下，有的边要通过至少两次。下图中，边旁写的是权。图3（1）在图3中
10、，奇点集合为V={v,v,v,v}01234（2）在V0中，每对点的距离为（用Dijkstra算法求）：d(v1,v2)=4d(v1,v3)=5d(v1,v4)=2d(v2,v3)=3d(v2,v4)=5d(v3,v4)=3（3）构造完全加权图K4，V(K4)={v1,v2,v3,v4}，边的权w(vivj)=d(vi,vj)i≠j,1≤i,j≤4，见图4：图4（4）求（3）中K4的最佳（总权最小）的完备匹配M，M={v1v4
