22-23欧拉图和哈密尔顿图-070101.pptVIP

必要条件的局限性 ——只能判定一个图不是哈密尔顿图 下图(Petersen图)满足上述必要条件。 Petersen图不是H_图。 H-通路/半哈密尔顿图 充分条件 [定理]简单G有n(n ?2)个节点，若G中任二点度数和大于等于n-1，则G有H-通路 例.有H_通路，无H_回路 设 S= {v1,v4}， |S|=2 W(G-S)=3 ? 2 = |S| H-图的 充分条件 [定理]简单G有n个结点，n?3，若G中任二点度数和大于等于n，则G有H-图 例. N边形， n?5 任一对结点度数和=45 但它显然是H_图 例. Kn是完全图 d(vi)+d(vj)=(n-1)+(n-1)=2n-2 ?n (n?3) ∴ Kn是H-图 只要图中边足够多，G易为H_图 只要图中成对节点度数足够大，G易为H_图 间接充要条件 [引理] 设 G中u,v不相邻，且 d(u)+d(v) ?n，则 G+{(u,v)}是H_图的充要条件是G是H_图 定义闭合图C(G)： 在G中反复增添结点度数和?|VG|的不相邻的节点对上的边，直至不能再添，得到的图为闭合图C(G) 图G的闭合图是唯一的 例 加成了完全图， 故是H_图 “如果只在满足 d(u)+d(v) ? n 的 u,v 之间加边——构造闭合图，图的哈密尔顿性质不会改变” 棋盘上的哈密尔顿回路问题 在4?4或5?5的缩小了的国际象棋棋盘上，马(Knight)不可能从某一格开始，跳过每个格子一次，并返回起点。 货郎担/旅行推销员(TSP)问题： 在一个赋权的完全图中，找出一个具有最小权的H_回路，也即回路边的权之和最小 对该赋权图上的边，满足三角不等式（距离不等式） W(a,b) ? W(a,c) + W(c,b) 数学模型 构造无向带权图G， VG中的元素对应于每个城市， EG中每个元素对应于城市之间的道路，道路长度用相应边的权表示。 则问题的解对应于G中包含所有边的权最小的哈密尔顿回路。 G是带权完全图，总共有n!/2条哈密尔顿回路。因此，问题是如何从这n!/2条中找出最短的一条 eg：含20个顶点的完全图中不同的哈密尔顿回路有约6000万亿条-(1.21645?1017)/2，若机械地检查，每秒处理10万条，需2万年 货郎担问题的近似算法 1)由任一点v0开始，找一条与之相关联的权最小的边(V0 ,V1 )，形成初始回路v0 v1 2)设v0 v1 ??? vi 已选定，从V— {v0 v1 ???vi}中找一点 vi+1 与 vi 距离最近 3)重复2)直到所有节点都在通路中 4)连接始点与终点 不一定是最佳解 例 8 c d e a b e 14 12 9 5 6 7 13 11 10 从a出发的“较好的”回路， 14 8 a d c e b a 7 6 5 长度：40 算法精度下限 设算法所得的回路长度为d， d0 是最小H_回路的长度，G有n点，则 d / d0 ? ? [ln(n)+1]+ ? 改进： 如果在已有回路中，W(vi,vj)+ W(vi+1,vj+1) W(vi,vi+1)+ W(vj,vj+1), 则分别用边 vivi+1 和 vjvj+1 替代 vivj 和 vi+1vj+1。 从a出发的“较好的”回路长度：40 14 8 a a d c e b 7 6 5 9 10 a a d c e b 7 6 5 9 10 经改进的回路，长度：37 c d e a b e 14 12 9 5 6 7 13 11 10 * 欧拉图和哈密尔顿图 信号处理中的数学方法 第2-4讲 一.欧拉回路：一般不限于简单图，一般指无向图 原问题：“右边的图中是否存在包含每条边一次且恰好一次的回路？” 原问题等价于：欧拉图 C D A B A C B D Eg. 哥尼斯堡七桥问题