第8章 几种典型图(1).pptVIP

第8章 几种典型图 8.1 欧拉图 8.2 哈密顿图 8.3 平面图 8.4 二分图 8.5 例题选解 习 题 八 8.1 欧 拉 图 欧拉图的概念是瑞士数学家欧拉（LeonhardEuler）在研究哥尼斯堡（K nigsberg）七桥问题时形成的。在当时的哥尼斯堡城，有七座桥将普莱格尔（Pregel）河中的两个小岛与河岸连接起来（见图8.1.1（a）），当时那里的居民热衷于一个难题：一个散步者从任何一处陆地出发，怎样才能走遍每座桥一次且仅一次，最后回到出发点？ 这个问题似乎不难，谁都想试着解决，但没有人成功。人们的失败使欧拉猜想：也许这样的解是不存在的，1936年他证明了自己的猜想。 ? 为了证明这个问题无解，欧拉用A，B，C，D四个顶点代表陆地，用连接两个顶点的一条弧线代表相应的桥，从而得到一个由四个顶点、七条边组成的图（见图8.1.1（b）），七桥问题便归结成：在图8.1.1（b）所示的图中，从任何一点出发每条边走一次且仅走一次的通路是否存在。 欧拉指出，从某点出发再回到该点，那么中间经过的顶点总有进入该点的一条边和走出该点的一条边，而且路的起点与终点重合，因此，如果满足条件的路存在，则图中每个顶点关联的边必为偶数。图8.1.1（b）中每个顶点关联的边均是奇数，故七桥问题无解。欧拉阐述七桥问题无解的论文通常被认为是图论这门数学学科的起源。 1.欧拉无向图 ?定义8.1.1 设G=〈V,E〉是连通图，经过G中每一条边一次且仅一次的通路（起点、终点不重合）称为欧拉通路（欧拉开迹），有欧拉通路的图称半欧拉图；经过每一条边一次且仅一次的回路称为欧拉回路（欧拉闭迹），有欧拉回路的图欧拉图。 一条欧拉通路即为一条行遍图中每条边的简单通路（迹），亦即一笔画问题。 定理8.1.1 设G是连通图，G是欧拉图当且仅当G的所有顶点均是偶度数点。 证明 先证必要性。 设G中有欧拉回路：v0e1v1e2v2…eiviei+1…ekv0，其中顶点可重复出现，边不可重复出现。在序列中，每出现一个顶点vi，它关联两条边，而vi可以重复出现，所以d（vi）为偶数。 再证充分性。 若图G是连通的，则可以按下列步骤构造一条欧拉回路： （1）从任一顶点v0开始，取关联于v0的边e1到v1，因为所有顶点为偶度数点，且G是连通的，所以可继续取关联于v1的边e2到v2……每条边均是前面未取过的，直到回到顶点v0，得一简单回路l1：v0e1v1e2v2…eiviei+1…ekv0。 （2）若l1行遍G中所有的边，则l1就是G中欧拉回路，即G为欧拉图，否则G-l1=G1不是空集，G1中每个顶点均是偶度数点，又G连通，G1与l1必有一个顶点vi重合，在G1中从vi出发重复步骤（1），可得一简单回路l2：vie′1u1e′2…vi。 （3）若l1∪l2=G，则G即为欧拉图，欧拉回路为l1∪l2：v0e1v1e2v2…eivie′1u1e′2…viei+1vi+1…ekv0，否则，重复步骤（2），直到构造一条行遍G中所有边的回路为止，此回路即为欧拉回路，G是欧拉图。 定理8.1.2 设G是连通图，则G是半欧拉图当且仅当G中有且仅有两个奇度数顶点。 证明 证法类同定理8.1.1。只是步骤（1）从一个奇度数顶点v0开始，取关联于v0的边e1到v1……直到另一个奇度数顶点vk为止，得一条简单通路l1。其他步骤与定理8.1.1同。最后构造出一条行遍G中所有边的简单通路，即为欧拉通路，G是半欧拉图。 定理提供了判断欧拉图和半欧拉图的方法，由此易知，哥尼斯堡七桥问题无解。 例如，图8.1.2中（a）是欧拉图，图（b）是半欧拉图，图（c）既非欧拉图也非半欧拉图。 当给定了一个欧拉图后，如何找出它的一条欧拉回路？下面的Fleury（于1921年提出）算法解决了这个问题，这个算法的实质是“避桥”。 设G是欧拉图。 （1）任选G的一个顶点v0为起点，并设零条边的通路为l0=v0。 （2）设已选