第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）既非欧拉图也非半欧拉图