资源描述：
《欧拉图和哈密顿图.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、离散数学第四篇图论第九章欧拉图和哈密顿图9.1欧拉图9.2哈密顿图9.1欧拉图9.1.1欧拉图的引入和定义18世纪中叶，在东普鲁士哥尼斯堡城，有一条贯穿全城的普雷格尔河，河中有两个岛，通过七座桥彼此相连，如图9.1.1(a)所示。（a）（b）图9.1.1定义9.1.1设G是无孤立节点的图，若存在一条通路(回路)，经过图中每边一次且仅一次，则称此通路(回路)为该图的一条欧拉通路(回路)。若存在一个圈，此圈通过G中每条边一次且仅一次，则此圈成为欧拉圈。具有欧拉回路的图称为欧拉图，具有欧拉通路但无欧拉回路的图称为半欧拉图。规定：平凡图是欧拉图。以上定义既适合无向图，又适合有向图。例9.1.1
2、判断下图的6个图中，是否是欧拉图？是否存在欧拉通路。(a)(b)(c)(d)(e)(f)分析：如果说图中存在欧拉通路（回路），具体找出一条经过图中每边一次且仅一次的通路(回路)即可；如果说图中不存在欧拉通路(回路)，则要试遍了边的所有全排列，它们都不能构成通路（回路）。解：在6个图中，图(a)和(d)是欧拉图；图(b)和(e)不是欧拉图，但存在欧拉通路；图(c)和(f)不存在欧拉通路。9.1.2欧拉图的判定判断一个图（无向图或有向图）是否有欧拉通路（回路），要考察所有边的所有全排列，几乎是不可能的，所幸已有简单的判别法。定理9.1.1设无向图G=是连通的，则（1）当且仅当G的
3、每个顶点都是偶顶点时，G是欧拉图。（2）当且仅当G除两个顶点是奇顶点外，其它顶点都是偶顶点时，G有欧拉通路。图9.1.5例9.1.2图G如图9.1.5所示。问图G是否为欧拉图？若是，求出其欧拉圈。由于G中的六个节点均为偶顶点且G连通，根据欧拉定理可知G为欧拉图。在图9.1.5中任意找一简单圈C：(1,2,3,1)；发现还有七条边不在此圈中，边(3,4)不在C中且在圈中的节点3相关联，由节点3出发经过边(3,4)可得到一简单圈C’(3,4,5,3)，将C’并入C得到了一个新的更长的简单圈C：(1,2,3,4,5,3,1)。此时仍有四条边不在圈C中，边(4,6)不在C中且与节点4相关联，由
4、节点4出发经过边(4,6)又可得到一个简单圈C’’：(4,6,5,2,4)，将C’’并入C得到一个更长的简单圈C：(1,2,3,4,6,5,2,4,5,3,1)。可以看到，G中所有的边已全在C中了，故知此圈C即为G中的一条欧拉圈。定理9.1.2设G=是有向弱连通图，则（1）当且仅当G的每个顶点的入度等于出度时，G是欧拉图。（2）当且仅当G除两个顶点外，其它顶点的入度等于出度，而除外的两个顶点，一个的入度比出度多1，另一个的入度比出度少1时，G有欧拉通路。定理9.1.1和定理9.1.2提供了欧拉通路与欧拉回路的十分简便的判别准则。例如，由定理可知，下图(a)图为欧拉图，本图既可
5、以看成圈v1v2v8v1，v2v3v4v2，v4v5v6v4，v6v7v8v6之并(为清晰起见，将4个圈画在(b)中)，也可看成圈v1v2v3v4v5v6v7v8v1与圈v2v4v6v8v2之并(两个圈画在(c)中)。将(a)分解成若干个边不重的圈的并不是(a)图特有性质，任何欧拉图都有这个性质。（a）（b）（c）定理9.1.3G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈的并。9.1.3欧拉图的难点对于欧拉图，需要大家注意以下几点：1．仅有欧拉通路而无欧拉回路的图不是欧拉图。2.图中是否存在欧拉通路、欧拉回路的判定非常简单，只要数一下图中节点的度数即可。9.1.4欧拉图的应
6、用一笔画问题所谓“一笔画问题”就是画一个图形，笔不离纸，每条边只画一次而不许重复地画完该图。“一笔画问题”本质上就是一个无向图是否存在欧拉通路（回路）的问题。如果该图为欧拉图，则能够一笔画完该图，并且笔又回到出发点；如果该图只存在欧拉通路，则能够一笔画完该图，但笔回不到出发点；如果该图中不存在欧拉通路，则不能一笔画完该图。9.2哈密顿图9.2.1哈密顿图的引入和定义1859年威廉哈密顿爵士发明了一个小玩具，这个小玩具是一个木刻的正十二面体，每面系正五角形，三面交于一角，共有20个角，每角标有世界上一个重要城市，如图9.2.1所示。他提出一个问题：要求沿正十二面体的边寻找一条路通过20个
7、城市，而每个城市只通过一次，最后返回原地。哈密顿将此问题称为周游世界问题。图9.2.1上述周游世界问题可用图论语言描述为：能否在图9.2.1所示的图中找到一条包含所有节点的基本回路。按照图中所给城市的编号，容易找到一条从节点1到2，再到3，到4，……，最后到达20，再回到1的包含图中每个节点的基本回路，即周游世界是可行的。将这个问题加以推广，即在任意连通图中是否存在一条包含图中所有节点的基本通路或基本回路。定义9.2.1通过图中每个顶点一次且仅
