《欧拉图和哈密尔顿图-精》由会员分享，可在线阅读，更多相关《欧拉图和哈密尔顿图-精（50页珍藏版）》请在金锄头文库上搜索。
1、欧拉图和哈密尔顿图信号处理中的数学方法 第2-4讲一.欧拉回路：一般不限于简单图，一般指无向 图n 原问题：“右边的图中是否存在包含每条边一次且恰好一 次的回路？” n 原问题等价于：欧拉图CDABACBDEg. 哥尼斯堡七桥问题欧拉回路，欧拉通路o 图G的一个回路/通路,它经过G中每条边恰 好一次，则回路/通路称为欧拉回路/通路。o 定义：如果图G中含欧拉回路，则图G称为 欧拉图。o 定义：如果图G中仅有欧拉通路，但没有欧 拉回路，则图G称为半欧拉图。 例 “一笔划”问题G中有欧拉通路？实例上图中，(1) ,(4) 为欧拉图例 多米诺骨牌，28块o 能否排成一圈使两两相邻的半边的点数相同，问
2、 是否可能？o 将0-6看作7个结点，任2点的边看作一块骨牌o 这样,该问题转化为G有无欧拉回路的问题 定理对连通图，下列命题等价o 1）G是欧拉图o 2）G的每个结点为偶度数o 3）G的边集能划分成为基本回路，即neg. 证 1)2)3) 1)o 1) 2):n 设Go为G的欧拉回路，可将Go表示为n v1e1v2e2envn+1(vn+1=v1)，其中vi的 一次出现总关联于左右2条边，对应度数为2n 又Go 的e1，e2，en互不相同，且穷尽了 所有的边，这样任一点vi的度数为vi在Go中 出现的度数之和必为2的倍数。/2) 3): G连通，不妨设G是非平凡图o 由2）每个结点度数至少为
3、2，所以G中含一基回 Z1，Z1的度数为偶度数，删去Z1的边得到G， 原G为偶度数，删去G的每个点仍为偶度数o 除孤立点外其余点至少为2度，即余连通点所图 至少2连通o 如法炮制，直至余图不含边o Z1，Z2 ，.,Zk 为E的一个划分。 /3) 1)：o Z1是划分中的一个基回，若Z1=E，则Z1就 欧拉回路，G是欧拉图 o 否则，存在另一回路Z2与Z1有公共点vo 构造简单回路，从v经Z1回到v，再经Z2回到vo 将Z1UZ2看作Z1，再重复上述过程，得到穷尽EG的简单回路。G欧拉图。/提示o 全部是偶度点的连通图中的回路 o 若干小回路串成欧拉回路续例 多米诺骨牌问题能构成回路，能够连成
4、首尾圈。/o定理 连通图G，若G中仅有0或2个奇度数点G有欧拉通路。o 0个奇度数，显然欧拉回路o 2个奇度数，u，v，分情况：1）u,v相邻，删(u,v)余图G为欧拉图，从u开始在G中走欧拉回路，回到u，再走(u,v)得到欧拉通路2） u,v不相邻，向着v方向，取(u,u1)删(u,u1)，以u1为始，重复过程，直至删(ui,v)后得到欧拉回路，连上所删除的边，得到 得到欧拉通路。/续例 .“一笔划”问题o G连通，从一个奇度点开始画，图只有0或2 个奇度点，则G可一笔画。/o 定理 对有向图，G有欧拉回路每一结 点入度等于出度。安排国展中心参观路线ABCJEFIKHGDLNMOABCIJD
5、KLMNHO EGF参观区域实景 图G设E为起始点E,N,M,O,L,K,I,L,M,J,N,D,C,J,B,I,A,K,H,G,O,F,Eo 1) 任取一点v0，置w0=v0o 2) 设简单回路wi= v0e1v1e2eivi 已选定 ，则从EGe1e2ei中选ei+1 n 选择条件：i. ei与vi相邻ii. 对EGe1e2ei而言非割边优先o 3) 重复2)，直到不能执行讨论这种情况下，会否出现o EGe1e2ei中有边，而2)之条件i不 成立的情况：n如 vi = v0，则必有某个jG是欧拉图，vVG，从v开始，每一步从当前 点所关联边中随机选边，均可构造欧拉回路，则G称为 以v为始点
6、的随机欧拉图。 p 注，若G是以v为始点的随机欧拉 图，则任何一个以v为始点的不包含G 中所有边的回路都应该能扩充成欧拉 回路。反之，若G不是以v为始点的随 机欧拉图，则一定存在已经包含了v 所关联的所有边，却未包含G中所有 边的简单回路。 随机欧拉图的判定定理 欧拉图G是以v为始点的随机欧拉图当且仅 当G中任一回路均包含v。 推论 欧拉图G是以任一顶点为始点的随机欧拉图 当且仅当G本身是一个基本回路)中国邮递员问题：o 问题：邮递员从邮局出发，走过辖区内每条 街道至少一次，如何选择最短路线？ o 1）每街一次/至少一次 o 2）环游最短中国邮递员问题-模型 数学模型：n 构造无向权图G，以道
7、路为边，路长为权n 问题的解G中包含所有边的回路权最小，称为 最优回路(未必是简单回路)。n 当G是欧拉图，则最优回路即欧拉回路。n 若G不是欧拉图，则通过加边来消除G中的奇度顶点 ，要求使加边得到的欧拉图G中重复边的权和最小 。 周游世界的游戏o 1859 哈密尔顿 “周游世界”游戏：20个城市，每个城市恰游一次，回到出发地用一个正12面体的20个顶点代表20个城市，哈密尔顿图 o 定义：若图G中有经过所有顶点的基本回路，称为 哈密尔顿回路，若G中含哈密尔顿回路，则称G为 H_图。o 定义：经过图G中所有顶点的基本通路称为哈密尔顿通路，若G中含哈密尔顿通路，但不含哈密尔顿回路，则称G为半哈密
8、尔顿图。 周游世界的游戏的解哈密顿图哈密顿图哈密顿图无哈密顿 通路存在哈密 顿通路实例o 在上图中， o (1),(2) 是哈密顿图;实例o 已知有关人员a, b, c, d, e, f, g 的有关信息 o a：说英语； o b：说英语或西班牙语； o c；说英语，意大利语和俄语； o d：说日语和西班牙语 o e：说德语和意大利语； o f：说法语、日语和俄语； o g：说法语和德语. o 试问：上述7人中是否任意两人都能交谈？ o (可借助其余5人中组成的译员链帮助)解 设7个人为7个结点, 将两个懂同一语言的人之间连一条边 (即他们能直接交谈), 这样就得到一个简单图G, 问题就转化为
9、 G是否连通. 如图所示, 因为G的任意两个结点是连通的, 所以G是连通图. 因此, 上述7个人中任意两个人能交谈. a：说英语； b：说英语或西班牙语； C: 说英语,意大利语和俄语； d：说日语和西班牙语 e：说德语和意大利语； f：说法语、日语和俄语； g：说法语和德语. abcdefg解一解二abcdefg英英西日法德意如果题目改为：试问这7个人应如何安排座位, 才能使每个人都能与 他身边的人交谈？ 解：用结点表示人，用边表示连接的两个人能说讲一种语言，够造 出哈密顿图如右上图所示。a：说英语； b：说英语或西班牙语； c；说英语，意大利语和俄语； d：说日语和西班牙语 e：说德语和意
10、大利语； f：说法语、日语和俄语； g：说法语和德语. 判断H-图任何一个H_图都可以看成是一个基本回路，再 加上其他若干条边H_图的充分条件和必要条件均有，但尚无充要 条件H_图的必要条件 nG是H_图，则对VG的任意非空真子集S (S， SV，均有W(G-S)|S| 其中W(G)是G的分支数必要条件的应用证设C是G的H_回路 W(C-S)|S|(从一个基本回路上删除k个顶点，最多形成k个连通分支)又G S 与C S的点相同，而EG-S E C S W(G-S)|S|例o 图中A类点仅与B类点连o |A|=|v1,v3,v7|=3, |B|=|v2,v4,v5 ,v6 ,v8|=5o 选S=
11、 v1,v3,v7， |S|=3o 则W(G-S)=5 |S|=3必要条件的局限性只能判定一个图不是哈密尔顿图下图(Petersen图)满足上述必要条件。Petersen图不是H_图。H-通路/半哈密尔顿图 充分条件o 定理简单G有n(n 2)个节点，若G中任二点度数 和大于等于n-1，则G有H-通路o 例.有H_通路，无H_回路设 S= v1,v4， |S|=2W(G-S)=3 2 = |S|H-图的 充分条件o 定理简单G有n个结点，n3，若G中任二 点度数和大于等于n，则G有H-图o 例. N边形， n5 o 任一对结点度数和=4闭合图C(G)：o 在G中反复增添结点度数和|VG|的不相
12、邻的 节点对上的边，直至不能再添，得到的图为闭 合图C(G)o 图G的闭合图是唯一的例加成了完全图，故是H_图o “如果只在满足 d(u)+d(v) n 的 u,v 之间加边构造 闭合图，图的哈密尔顿性质不会改变”棋盘上的哈密尔顿回路问题o 在44或55的缩小了的国际象棋棋盘上，马 (Knight)不可能从某一格开始，跳过每个格 子一次，并返回起点。货郎担/旅行推销员(TSP)问题：o 在一个赋权的完全图中，找出一个具有最小权的H_回路，也即回路边的权之和最小o 对该赋权图上的边，满足三角不等式（距离不等式）W(a,b) W(a,c) + W(c,b) 数学模型q构造无向带权图G， VG中的元
13、素对应于每个城市， EG中每 个元素对应于城市之间的道路，道路长度用相应边的权表示 。q则问题的解对应于G中包含所有边的权最小的哈密尔顿回路 。qG是带权完全图，总共有n!/2条哈密尔顿回路。因此，问题 是如何从这n!/2条中找出最短的一条qeg：含20个顶点的完全图中不同的哈密尔顿回路有约6000万 亿条-(1.216451017)/2，若机械地检查，每秒处理10万条，需 2万年货郎担问题的近似算法1)由任一点v0开始，找一条与之相关联的权最小的边 (V0 ,V1 )，形成初始回路v0 v12)设v0 v1 vi 已选定，从V v0 v1 vi中找一点 vi+1 与 vi 距离最近3)重复2
14、)直到所有节点都在通路中4)连接始点与终点p 不一定是最佳解例8cd e abe14129567131110从a出发的“较好的”回路，148a d c e b a 765长度：40算法精度下限o 设算法所得的回路长度为d， d0 是最小H_回路的长度，G有n点，则o 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出发的“较好的”回路长度：40148aa dce b 765910aadceb 765910经改进的回路，长 度：37cd e abe14129567131110
