组合优化(欧拉图)

1、欧拉图与中国邮递员问题算法欧拉图与中国邮递员问题算法欧拉图与中国邮递员问题算法欧拉图与中国邮递员问题算法欧拉图和哈密顿图的介绍欧拉图的算法介绍欧拉图在中国邮递员问题的运用哈密顿图的相关介绍哈密顿图在旅行商问题的运用欧拉图和哈密顿图的介绍欧拉图和哈密顿图的介绍 图： 图是一个有序二元组，其中V称为顶点集，E称为边集。E的元素都是二元组，用(x,y)表示，其中x , y来源于V.欧拉图和哈密顿图的介绍欧拉图和哈密顿图的介绍 欧拉路： 通过图G的每条边一次且仅一次的开路称为欧拉路。 半欧拉图： 存在欧拉路的图称为半欧拉图。 欧拉回路： 通过图G的每条边一次且仅一次的回路称为欧拉回路。 欧拉图： 存在

2、欧拉回路的图称为欧拉图。 哈密顿路： 通过图G的每个结点一次且仅一次的路径称为哈密尔顿路。 半哈密顿图：存在哈密顿路的图称为半哈密顿图。 哈密顿回路： 通过图G的每个结点一次且仅一次的回路称为哈密尔顿回路。 哈密顿图： 存在哈密顿回路的图称为哈密顿图。欧拉图和哈密顿图的介绍欧拉图和哈密顿图的介绍欧拉图的算法介绍欧拉图的算法介绍 定理1： 无向图G为欧拉图的充要条件G是连通图且没有奇度顶点。 定理2： 无向图G是半欧拉图的充要条件G是连通的且恰有两个奇度的顶点。 无向图中寻找欧拉回路欧拉图的算法介绍欧拉图的算法介绍要输出的欧拉回路队列当前访问的节点已经访问的边节点的邻近节点从当前访问节点的邻居中

3、找一个节点 例：欧拉图的算法介绍欧拉图的算法介绍 定理3： 由上述的算法框架可以找到一条欧拉回路。 定理1： 无向图G为欧拉图的充要条件G是连通图且没有奇度顶点。欧拉图的算法介绍欧拉图的算法介绍 有向图中寻找欧拉回路的预备知识点 这儿我们使用逆向思维(如果可以找到欧拉回路，那么这个图肯定是欧拉图。当然，如果是欧拉图，也肯定能找到欧拉回路) Spanning out-tree欧拉图的算法介绍欧拉图的算法介绍 定理4： If G is a connected, balanced diagraph with spanning out-tree T rooted at u , then an Eule

4、rian circuit can be traced in reverse direction as follows: (a) The initial edge is any edge incident to u; (b) Subsequent edges are chosen so as to be incident to the current vertex and such that： No edge is traversed more than once. No edge of T is chosen if another edge is still available. The pr

5、ocess stops when a vertex is reached which has no unused edges incident to it.欧拉图的算法介绍欧拉图的算法介绍时间复杂度：O(|E|) 有向图中寻找欧拉回路欧拉图的算法介绍欧拉图的算法介绍要输出的欧拉回路队列节点的邻近节点Av链表的下标对Av队列进行赋值进行寻找欧拉回路 例：欧拉图的算法介绍欧拉图的算法介绍欧拉图在中国邮递员问题的运用欧拉图在中国邮递员问题的运用 中国邮递员问题 如何走完一个城市的所有路径，然后回到原地。 首先，对于一个欧拉图不止一条欧拉回路。 对于无向欧拉图 对于有些欧拉图欧拉图在中国邮递员问题的运

6、用欧拉图在中国邮递员问题的运用n-ii = 1count = (d (v ) - 1)!n-ii = 1count = T(G) * (d (v ) - 1)! 问题： 如何在一个有权重、无向的、非欧拉图中找到一条最短的路径?(所有的路径都要至少走一遍，并且回到原点) 解决方法： 在将原本的非欧拉图G基础加入路径后形成欧拉图G。 由于是求最短路径，故加入的路径长度应该越短越好。欧拉图在中国邮递员问题的运用欧拉图在中国邮递员问题的运用 算法框架：欧拉图在中国邮递员问题的运用欧拉图在中国邮递员问题的运用 例：欧拉图在中国邮递员问题的运用欧拉图在中国邮递员问题的运用 问题： 如何在一个有权重、有向的

7、、非欧拉图中找到一条最短的路径?(所有的路径都要至少走一遍，并且回到原点) 与无向图的区别： 可能形成不了环。欧拉图在中国邮递员问题的运用欧拉图在中国邮递员问题的运用XY 定理4： 有些图有邮递员回路，当且仅当它是强连通的。 解决方法： 在将原本的有向非欧拉图G基础加入路径后形成有向欧拉图G。 由于是求最短路径，故加入的路径长度应该越短越好。欧拉图在中国邮递员问题的运用欧拉图在中国邮递员问题的运用 算法框架：欧拉图在中国邮递员问题的运用欧拉图在中国邮递员问题的运用 例：欧拉图在中国邮递员问题的运用欧拉图在中国邮递员问题的运用哈密顿图的相关介绍哈密顿图的相关介绍 哈密顿路： 通过图G的每个结点一

8、次且仅一次的路径称为哈密尔顿路。 半哈密顿图：存在哈密顿路的图称为半哈密顿图。 哈密顿回路： 通过图G的每个结点一次且仅一次的回路称为哈密尔顿回路。 哈密顿图： 存在哈密顿回路的图称为哈密顿图。 一些现有的知识理论： 完全图是哈密顿图。 基本图是完全图的有向图，包含了哈密顿路径。 基本图是完全图的强连通图，是一个哈密顿图。 如果G是一个无向图，并且它的边数n大于3，每个顶点的度都大于1/2 n，则G是哈密顿图。 如果G=(V,E)是一个哈密顿图，那么对于它的每一子图都有：C(G V) b - c - a 52. a - b - a - b - a 4 问题所在： 就是在带有权重的图中，存在这样

9、的情况：三个点形成的三角形不满足三角形不等式，即两边之和不大于第三边。 然而，在第二种情况下，我们所得的解并不是一个环了，可能有多个。给我们对问题求解带来很多麻烦。 解决方法： 对图进行调整。 总结： 对于那些满足三角形不等式的图形，我们可以直接求其回路。(相对应于第一种定义) 对于那些不满足三角形不等式的图形，我们进行调整后在求其回路。 (相对应于第二种定义)哈密顿图在旅行商问题的运用哈密顿图在旅行商问题的运用 定理5： 对图形进行调整前后，旅行商问题的最短路径长度是相同的。 前提： 对图形计算最短哈密顿回路的时间复杂度为O(N)。哈密顿图在旅行商问题的运用哈密顿图在旅行商问题的运用由于准确

10、求解所需时间过长，我们采取近似求解。假设准确求解结果为L,近似求解结果为L，我们定义：则，a越趋近于1，结果越好。哈密顿图在旅行商问题的运用哈密顿图在旅行商问题的运用01L/L Nearest-neighbour method 即每次都从邻居中选择最短的路径 哈密顿图在旅行商问题的运用哈密顿图在旅行商问题的运用1( ln( )1)2n An approximation algorithm for the travelling salesman problem哈密顿图在旅行商问题的运用哈密顿图在旅行商问题的运用2 例：哈密顿图在旅行商问题的运用哈密顿图在旅行商问题的运用L(v1)=1 L(v2)=2 L(v3)=3 L(v4)=4 L(v5)=5 L(v6) =6 An improved approximation algorithm for the travelling salesman problem哈密顿图在旅行商问题的运用哈密顿图在旅行商问题的运用32 例：哈密顿图在旅行商问题的运用哈密顿图在旅行商问题的运用L(v1)=