欧拉图和哈密尔顿图精课件

欧拉图和哈密尔顿图信号处理中的数学方法第2-4讲一.欧拉回路：一般不限于简单图，一般指无向图原问题：“右边的图中是否存在包含每条边一次且恰好一次的回路？”原问题等价于：欧拉图

CDABACBDEg.哥尼斯堡七桥问题<定义>欧拉回路，欧拉通路图G的一个回路/通路,它经过G中每条边恰好一次，则回路/通路称为欧拉回路/通路。定义：如果图G中含欧拉回路，则图G称为欧拉图。定义：如果图G中仅有欧拉通路，但没有欧拉回路，则图G称为半欧拉图。

实例上图中，(1),(4)为欧拉图例多米诺骨牌，28块能否排成一圈使两两相邻的半边的点数相同，问是否可能？将0-6看作7个结点，任2点的边看作一块骨牌这样,该问题转化为G有无欧拉回路的问题[证]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是非平凡图由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—欧拉图。//续例多米诺骨牌问题

∴能构成回路，能够连成首尾圈。//[定理]连通图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可一笔画。//[定理]对有向图，G有欧拉回路每一结点入度等于出度。<欧拉回路-Fleury算法>1)任取一点v0，置w0=v02)设简单回路wi=v0e1v1e2……eivi已选定，则从EG−{e1e2……ei}中选ei+1

选择条件：

i.ei与vi相邻

ii.对EG−{e1e2……ei}而言非割边优先3)重复2)，直到不能执行讨论这种情况下，会否出现EG−{e1e2……ei}中有边，而2)之条件i不成立的情况：如vi=v0，则必有某个j<i时刻选ej+1

边为割边

——与2）之ii条件相矛盾，∴不可能出现，即vi

≠v0如vi

≠v0，则vi

的度数为奇数

——与欧拉图相矛盾在画欧拉回路时，已经经过的边不能再用；在走回路中的任何时刻，将已经经过的边删除，剩下的边必须仍在同一连通分支当中提示：×随机欧拉图的判定[定理]欧拉图G是以v为始点的随机欧拉图当且仅当G中任一回路均包含v。[推论]欧拉图G是以任一顶点为始点的随机欧拉图当且仅当G本身是一个基本回路)中国邮递员问题：问题：邮递员从邮局出发，走过辖区内每条街道至少一次，如何选择最短路线？1）每街一次/至少一次2）环游最短中国邮递员问题-模型数学模型：构造无向权图G，以道路为边，路长为权问题的解——G中包含所有边的回路权最小，称为最优回路(未必是简单回路)。当G是欧拉图，则最优回路即欧拉回路。若G不是欧拉图，则通过加边来消除G中的奇度顶点，要求使加边得到的欧拉图G'中重复边的权和最小。哈密尔顿图定义：若图G中有经过所有顶点的基本回路，称为哈密尔顿回路，若G中含哈密尔顿回路，则称G为H_图。定义：经过图G中所有顶点的基本通路称为哈密尔顿通路，若G中含哈密尔顿通路，但不含哈密尔顿回路，则称

G为半哈密尔顿图。周游世界的游戏——的解实例

已知有关人员a,b,c,d,e,f,g的有关信息

a：说英语；

b：说英语或西班牙语；

c；说英语，意大利语和俄语；

d：说日语和西班牙语

e：说德语和意大利语；

f：说法语、日语和俄语；

g：说法语和德语.试问：上述7人中是否任意两人都能交谈？

(可借助其余5人中组成的译员链帮助) 解设7个人为7个结点,将两个懂同一语言的人之间连一条边(即他们能直接交谈),这样就得到一个简单图G,问题就转化为G是否连通.如图所示,因为G的任意两个结点是连通的,所以G是连通图.因此,上述7个人中任意两个人能交谈.

a：说英语；b：说英语或西班牙语；C:说英语,意大利语和俄语；d：说日语和西班牙语e：说德语和意大利语；f：说法语、日语和俄语；g：说法语和德语.abcdefg解一解二abcdefg英英西日法德意如果题目改为：试问这7个人应如何安排座位,才能使每个人都能与他身边的人交谈？解：用结点表示人，用边表示连接的两个人能说讲一种语言，够造出哈密顿图如右上图所示。a：说英语；b：说英语或西班牙语；c；说英语，意大利语和俄语；d：说日语和西班牙语e：说德语和意大利语；f：说法语、日语和俄语；g：说法语和德语.判断H-图任何一个H_图都可以看成是一个基本回路，再加上其他若干条边H_图的充分条件和必要条件均有，但尚无充要条件H_图的必要条件G是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

EC–S

∴W(G-S)|S|例图中A类点仅与B类点连|A|=|{v1,v3,v7}|=3,|B|=|{v2,v4,v5,v6,v8}|=5选S={v1,v3,v7}，|S|=3则W(G-S)=5

|S|=3必要条件的局限性

——只能判定一个图不是哈密尔顿图下图(Petersen图)满足上述必要条件。

Petersen图不是H_图。H-通路/半哈密尔顿图充分条件[定理]简单G有n(n2)个节点，若G中任二点度数和大于等于n-1，则G有H-通路例.有H_通路，无H_回路设S={v1,v4}，

|S|=2

W(G-S)=3

2

=

|S|H-图的充分条件[定理]简单G有n个结点，n3，若G中任二点度数和大于等于n，则G有H-图例.N边形，n5任一对结点度数和=4<5但它显然是H_图例.Kn是完全图

d(vi)+d(vj)=(n-1)+(n-1)=2n-2n(n3)∴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之间加边——构造闭合图，图的哈密尔顿性质不会改变”棋盘上的哈密尔顿回路问题在44或55的缩小了的国际象棋棋盘上，马(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.216451017)/2，若机械地检查，每秒处理10万条，需2万年货郎担问题的近似算法1)由任一点v0开始，找一条与之相关联的权最小的边(V0,V1)，形成初始回路v0v12)设v0v1vi

已选定，从V—{v0v1vi}中找一点vi+1与vi距离最近3)重复2)直到所有节点都在通路中4)连接始点与终点不一定是最佳解例8cde

abe14129567131110从a出发的“较好的”回路，148adceba765长度：40算法精度下限设算法所得的回路长度为d，d0

是最小H_回路的长度，G有n点，则

d/d0

½[ln(n)+1]+½改进：如果在已有回路