欧拉图和哈密尔顿图精

《欧拉图和哈密尔顿图精》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、欧拉图和哈密尔顿图信号处理中的数学方法第2-4讲一.欧拉回路：一般不限于简单图，一般指无向图原问题：“右边的图中是否存在包含每条边一次且恰好一次的回路？”原问题等价于：欧拉图CDABACBDEg.哥尼斯堡七桥问题<定义>欧拉回路，欧拉通路图G的一个回路/通路,它经过G中每条边恰好一次，则回路/通路称为欧拉回路/通路。定义：如果图G中含欧拉回路，则图G称为欧拉图。定义：如果图G中仅有欧拉通路，但没有欧拉回路，则图G称为半欧拉图。例“一笔划”问题——G中有欧拉通路？实例上图中，(1),(4)为欧拉图例多米诺骨牌，28块能否排成一圈使两两相邻的半边的

2、点数相同，问是否可能？将0-6看作7个结点，任2点的边看作一块骨牌这样,该问题转化为G有无欧拉回路的问题[定理]对连通图，下列命题等价1）G是欧拉图2）G的每个结点为偶度数3）G的边集能划分成为基本回路，即eg.[证]1)2)3)1)1)2):设Go为G的欧拉回路，可将Go表示为v1e1v2e2……envn+1(vn+1=v1)，其中vi的一次出现总关联于左右2条边，对应度数为2又Go的e1，e2，……en互不相同，且穷尽了所有的边，这样任一点vi的度数为vi在Go中出现的度数之和——必为2的倍数。//2)3):G连通，不妨设G是非平

3、凡图由2）每个结点度数至少为2，所以G中含一基回Z1，Z1的度数为偶度数，删去Z1的边得到G’，原G为偶度数，删去G’的每个点仍为偶度数除孤立点外其余点至少为2度，即余连通点所图至少2连通如法炮制，直至余图不含边{Z1}，{Z2}，…..,{Zk}为E的一个划分。//3)1)：Z1是划分中的一个基回，若{Z1}=E，则Z1就欧拉回路，G是欧拉图否则，存在另一回路Z2与Z1有公共点v构造简单回路，从v经Z1回到v，再经Z2回到v将Z1UZ2看作Z1，再重复上述过程，得到穷尽EG的简单回路。∴G—欧拉图。//提示全部是偶度点的连通图中的回路若干小

4、回路串成欧拉回路续例多米诺骨牌问题∴能构成回路，能够连成首尾圈。//[定理]连通图G，若G中仅有0或2个奇度数点G有欧拉通路。<证>0个奇度数，显然欧拉回路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)后得到欧拉回路，连上所删除的边，得到——得到欧拉通路。//续例.“一笔划”问题G连通，从一个奇度点开始画，图只有0或2个奇度点，则G可一笔画。//[定理

5、]对有向图，G有欧拉回路每一结点入度等于出度。安排国展中心参观路线ABCJEFIKHGDLNMOABCIJDKLMNHOEGF参观区域实景图G设E为起始点E,N,M,O,L,K,I,L,M,J,N,D,C,J,B,I,A,K,H,G,O,F,E<欧拉回路-Fleury算法>1)任取一点v0，置w0=v02)设简单回路wi=v0e1v1e2……eivi已选定，则从EG−{e1e2……ei}中选ei+1选择条件：i.ei与vi相邻ii.对EG−{e1e2……ei}而言非割边优先3)重复2)，直到不能执行讨论这种情况下，会否出现EG−{e1e2……

6、ei}中有边，而2)之条件i不成立的情况：如vi=v0，则必有某个jG是欧拉图，vVG，从v开始，每一步从当前点所关联边中随机选边，均可构造欧拉回路，则G称为以v为始点的随机欧拉图。注，若G是以v为始点的随机欧拉图，则任何一个以v为始点的不包含G中所有边的回路都应该能扩充成欧

7、拉回路。反之，若G不是以v为始点的随机欧拉图，则一定存在已经包含了v所关联的所有边，却未包含G中所有边的简单回路。随机欧拉图的判定[定理]欧拉图G是以v为始点的随机欧拉图当且仅当G中任一回路均包含v。[推论]欧拉图G是以任一顶点为始点的随机欧拉图当且仅当G本身是一个基本回路)中国邮递员问题：问题：邮递员从邮局出发，走过辖区内每条街道至少一次，如何选择最短路线？1）每街一次/至少一次2）环游最短中国邮递员问题-模型数学模型：构造无向权图G，以道路为边，路长为权问题的解——G中包含所有边的回路权最小，称为最优回路(未必是简单回路)。当G是欧拉图，则

8、最优回路即欧拉回路。若G不是欧拉图，则通过加边来消除G中的奇度顶点，要求使加边得到的欧拉图G'中重复边的权和最小。周游世界的游戏1859哈密尔顿“周游