离散数学第七章

7.4欧拉图与哈密尔顿图7.4 欧拉图与汉密尔顿图 哥尼斯堡七桥问题： 18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如图1所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成A、B、C、D，4个点，7座桥表示成7条连接这4个点的线，如图所示。于是“七桥问题”就等价于图中所画图形的一笔画问题了。欧拉注意到，每个点如果有进去的边就必须有出来的边，从而每个点连接的边数必须有偶数个才能完成一笔画。上图的每个点都连接着奇数条边，因此不可能一笔画出，这就说明不存在一次走遍7座桥，而每座桥只许通过一次的走法。欧拉对“七桥问题”的研究是图论研究的开始，同时也为拓扑学的研究提供了一个初等的例子。一、基本概念：1、欧拉图：给定无孤立结点图G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉路；若存在一条回路，经过图中每边一次且仅一次，该回路称为欧拉回路。 具有欧拉回路的图称为欧拉图。v2v3v4v1C（V1、V2、V3、V1、V4、V3）定理1：无向图G有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数度结点。v2v3v4v1推论：给定无向连通图G，G是欧拉图，当且仅当G是连通的且图中每个结点都是偶数度结点。一笔画问题与七桥问题类似的还有一笔画的判别问题，要判定一个图是否可一笔画出，有两种情况：一是从图G中某一结点出发，经过图中的每一边一次且仅一次到达另一结点；另一种情况是从G的某个结点出发，经过G的每一边一次且仅一次再回到该结点。 上述两种情况分别可由欧拉路和欧拉回路的判定条件予以解决。定义：给定有向图G，通过图中每边一次且仅一次的一条单向路（回路），称作单向欧拉路（回路）。定理2：有向图G具有一条单向欧拉回路，当且仅当是连通的，且每个结点入度等于出度。一个有向图G中具有单向欧拉路，当且仅当它是连通的，而且除两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度小1，一个结点的入度比出度大1。有向图中欧拉图例：从图中找一条欧拉路。解奇数度顶点是:v1和v9。{v1,v2}和{v4,v6}是桥。L=v1,v2,v3,v4,v5,v2,v4,v6,v7,v8,v9,v10,v6,v8,v10,v7,v9是一条欧拉路。欧拉回路问题既是一个有趣的游戏问题,又是一个有实用价值的问题。邮递员一般的邮递路线是需要遍历某些特定的街道,理想地,他应该走一条欧拉路,即不重复地走遍图中的每一条边。一般邮递路线感兴趣的是图中的边。但有的邮递任务是联系某些特定的收发点,不要求走遍每一条边,只要求不重复地遍历图中的每一个顶点,此时感兴趣的是图中的顶点,这就是下面研究的汉密尔顿图。1859年,爱尔兰数学家汉密尔顿(Halmiton)提出一个“周游世界”的游戏,它把图(a)所示的正十二面体的二十个顶点当作是地球上的二十个城市,要求旅游者从某个城市出发,沿棱走过每个城市一次且仅一次,最后回到出发点。(b)图中粗线所构成的回路就是问题的答案汉密尔顿图ab二、汉密尔顿图1、定义：给定图G，若存在一条路，经过图中的每个结点恰好一次，这条路称作汉密尔顿路。若存在一条回路，经过图中的每个结点恰好一次，这条回路称作汉密尔顿回路。具有汉密尔顿回路的图称作汉密尔顿图。例：(a)存在汉密尔顿回路,(a)是汉密尔顿图。(b)存在汉密尔顿路但不存在汉密尔顿回路,(b)不是汉密尔顿图。(c)不存在汉密尔顿路且不存在汉密尔顿回路,(c)不是汉密尔顿图。（a）（b）（c）欧拉图、欧拉回路和汉密尔顿图、汉密尔顿回路之间的区别。(1)欧拉回路是一条闭迹,而汉密尔顿图是一个圈。闭迹：各边全不相同的回路。圈：除终点与始点外，各结点全不相同的回路。(2)欧拉图遍历边,而汉密尔顿图遍历顶点。联系它们之间几乎没有什么联系。 有的图只是欧拉图， 有的图只是汉密尔顿图, 有的图既是欧拉图又是汉密尔顿图, 有的图则两者皆不是。虽然