西安电子科技大学出版社：面向21世纪高等学校计算机类专业系列教材《离散数学》课程教学资源（PPT课件讲稿）第10章 几种典型图

第10章几种典型图 第10章几种典型图 0.1欧拉图 10.2哈密顿图 10.3平面图 10.4二分图 10.5例题选解 习题十 dBac

第10章 几种典型图 第10章 几种典型图 10.1 欧拉图 10.2 哈密顿图 10.3 平面图 10.4 二分图 10.5 例题选解 习 题 十

第10章几种典型图 10.1欧拉图 欧拉图的概念是瑞士数学家欧拉( Leonhardeuler) 在研究哥尼斯堡( K nigsberg)七桥问题时形成的。在 当时的哥尼斯堡城,有七座桥将普莱格尔( Pregel)河 中的两个小岛与河岸连接起来(见图10.1.1(a)) 当时那里的居民热衷于一个难题:一个散步者从任何 处陆地出发,怎样才能走遍每座桥一次且仅一次, 最后回到出发点?

第10章 几种典型图 10.1 欧 拉 图 欧拉图的概念是瑞士数学家欧拉（LeonhardEuler） 在研究哥尼斯堡（K nigsberg）七桥问题时形成的。在 当时的哥尼斯堡城，有七座桥将普莱格尔（Pregel）河 中的两个小岛与河岸连接起来（见图10.1.1（a））， 当时那里的居民热衷于一个难题：一个散步者从任何 一处陆地出发，怎样才能走遍每座桥一次且仅一次， 最后回到出发点？

第10章几种典型图 这个问题似乎不难,谁都想试着解决,但没有人 成功。人们的失败使欧拉猜想:也许这样的解是不存 在的,1936年他证明了自己的猜想。 为了证明这个问题无解,欧拉用A,B,C,D四个 顶点代表陆地,用连接两个顶点的一条弧线代表相应 的桥,从而得到一个由四个顶点、七条边组成的图 (见图10.1.1(b)),七桥问题便归结成:在图10.1.1 (b)所示的图中,从任何一点出发每条边走一次且仅 走一次的通路是否存在

第10章 几种典型图 这个问题似乎不难，谁都想试着解决，但没有人 成功。人们的失败使欧拉猜想：也许这样的解是不存 在的，1936年他证明了自己的猜想。 为了证明这个问题无解，欧拉用A，B，C，D四个 顶点代表陆地，用连接两个顶点的一条弧线代表相应 的桥，从而得到一个由四个顶点、七条边组成的图 （见图10.1.1（b）），七桥问题便归结成：在图10.1.1 （b）所示的图中，从任何一点出发每条边走一次且仅 走一次的通路是否存在

第10章几种典型图 欧拉指出,从某点出发再回到该点,那么中间经 过的顶点总有进入该点的一条边和走出该点的一条边, 而且路的起点与终点重合,因此,如果满足条件的路 存在,则图中每个顶点关联的边必为偶数。图10.1.1 (b)中每个顶点关联的边均是奇数,故七桥问题无解。 欧拉阐述七桥问题无解的论文通常被认为是图论这门 数学学科的起源

第10章 几种典型图 欧拉指出，从某点出发再回到该点，那么中间经 过的顶点总有进入该点的一条边和走出该点的一条边， 而且路的起点与终点重合，因此，如果满足条件的路 存在，则图中每个顶点关联的边必为偶数。图10.1.1 （b）中每个顶点关联的边均是奇数，故七桥问题无解。 欧拉阐述七桥问题无解的论文通常被认为是图论这门 数学学科的起源

第10章几种典型图 A A B 图10.1.1

第10章 几种典型图 图 10.1.1 B C (a) A D A B D C (b)

第10章几种典型图 1欧拉无向图 定义101.1设G=〈VE〉是连通图,经过G中每 条边一次且仅一次的通路(起点、终点不重合)称为 欧拉通路(欧拉开迹),有欧拉通路的图称半欧拉图; 经过每一条边一次且仅一次的回路称为欧拉回路(欧 拉闭迹),有欧拉回路的图称欧拉图。一条欧拉通路 即为一条行遍图中每条边的简单通路(迹),亦即 笔画问题

第10章 几种典型图 1.欧拉无向图 定义10.1.1 设G=〈V,E〉是连通图，经过G中每一 条边一次且仅一次的通路（起点、终点不重合）称为 欧拉通路（欧拉开迹），有欧拉通路的图称半欧拉图； 经过每一条边一次且仅一次的回路称为欧拉回路（欧 拉闭迹），有欧拉回路的图称欧拉图。一条欧拉通路 即为一条行遍图中每条边的简单通路（迹），亦即一 笔画问题

第10章几种典型图 定理10.1.1设G是连通图,G是欧拉图当且仅当G 的所有顶点均是偶度数点 证明先证必要性。 设G中有欧拉回路:vee22.ee1#1!ekVo,其中 顶点可重复出现,边不可重复出现。在序列中,每出 现一个顶点v,它关联两条边,而v可以重复出现,所 以d(v;)为偶数

第10章 几种典型图 定理10.1.1 设G是连通图，G是欧拉图当且仅当G 的所有顶点均是偶度数点。 证明 先证必要性。 设G中有欧拉回路：v0e1v1e2v2…eiviei+1…ekv0，其中 顶点可重复出现，边不可重复出现。在序列中，每出 现一个顶点vi，它关联两条边，而vi可以重复出现，所 以d（vi）为偶数

第10章几种典型图 再证充分性 若图G是连通的,则可以按下列步骤构造一条欧拉 回路: (1)从任一顶点v开始,取关联于v的边e1到v1 因为所有顶点为偶度数点,且G是连通的,所以可继续 取关联于v1的边e2到v2…每条边均是前面未取过的,直 到回到顶点v,得一简单回路l1:ve1ve22,epve1hv

第10章 几种典型图 再证充分性。 若图G是连通的，则可以按下列步骤构造一条欧拉 回路： （1）从任一顶点v0开始，取关联于v0的边e1到v1， 因为所有顶点为偶度数点，且G是连通的，所以可继续 取关联于v1的边e2到v2……每条边均是前面未取过的，直 到回到顶点v0，得一简单回路l1：v0e1v1e2v2…eiviei+1…ekv0

第10章几种典型图 (2)若l1行遍G中所有的边,则l就是G中欧拉回 路,即G为欧拉图,否则G-l1=G1不是空集,G1中每个 顶点均是偶度数点,又G连通,G1与1必有一个顶点v 重合,在G1中从v出发重复步骤(1),可得一简单回 路l2:ve'1li巳2…V; (3)若l1Ul2=G,则G即为欧拉图,欧拉回路为 h1Ul2:We1wve22.ee1l1e2ve+1v1!ekv,否则,重 复步骤(2),直到构造一条行遍G中所有边的回路为 止,此回路即为欧拉回路,G是欧拉图

第10章 几种典型图 （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是欧拉图

第10章几种典型图 定理10.12设G是连通图,则G是半欧拉图当且仅 当G中有且仅有两个奇度数顶点 证明证法类同定理10.1.1。只是步骤(1)从一个 奇度数顶点v开始,取关联于v的边e到v…,直到另 个奇度数顶点v为止,得一条简单通路l1。其他步骤与 定理10.1.1同。最后构造出一条行遍G中所有边的简单 通路,即为欧拉通路,G是半欧拉图。 定理提供了判断欧拉图和半欧拉图的方法,由此 易知,哥尼斯堡七桥问题无解。 例如,图10.1.2中(a)是欧拉图,图(b)是半欧 拉图,图(c)既非欧拉图也非半欧拉图

第10章 几种典型图 定理10.1.2 设G是连通图，则G是半欧拉图当且仅 当G中有且仅有两个奇度数顶点。 证明 证法类同定理10.1.1。只是步骤（1）从一个 奇度数顶点v0开始，取关联于v0的边e1到v1……直到另一 个奇度数顶点vk为止，得一条简单通路l1。其他步骤与 定理10.1.1同。最后构造出一条行遍G中所有边的简单 通路，即为欧拉通路，G是半欧拉图。 定理提供了判断欧拉图和半欧拉图的方法，由此 易知，哥尼斯堡七桥问题无解。 例如，图10.1.2中（a）是欧拉图，图（b）是半欧 拉图，图（c）既非欧拉图也非半欧拉图