南京大学：《离散数学 Discrete Mathmatics》课程教学资源（课件讲稿，2018）图论——第23章 欧拉图、哈密尔顿图

欧拉图 离散数学一图论初步 南京大学计算机科学与技术系

欧拉图 离散数学─图论初步 南京大学计算机科学与技术系

殼壁嘉 内容提要 ●欧拉通路/回路 ●欧拉图的充要条件 。构造欧拉回路的Fleury2算法 ●哈密尔顿通路回路 。哈密尔顿图的必要和充分条件 ·哈密尔顿图的应用

内容提要  欧拉通路/回路  欧拉图的充要条件  构造欧拉回路的Fleury算法  哈密尔顿通路/回路  哈密尔顿图的必要和充分条件  哈密尔顿图的应用

线兔 Konigsberg-七桥问题 707 。问题的抽象： ●用顶点表示对象“地块” 。用边表示对象之间的关系“有桥相连” 。原问题等价于：“右边的图中是否存在包含每条边 一次且恰好一次的回路？” B

Königsberg七桥问题  问题的抽象：  用顶点表示对象-“地块”  用边表示对象之间的关系-“有桥相连”  原问题等价于：“右边的图中是否存在包含每条边 一次且恰好一次的回路？” C D A B A C B D

售嘉 “一笔划”问题 ？

“一笔划”问题 ？

&线 欧拉通路和欧拉回路 ●定义：包含图（无向图或有向图)中每条边的简单通 路称为欧拉通路。 注意：欧拉通路是简单通路（边不重复），但顶点可重复 ●定义：包含图中每条边的简单回路称为欧拉回路。 ·如果图G中含欧拉回路，则G称为欢拉图。如果图G中 有欧拉通路，但没有欧拉回路，则G称为半欧拉图。 ∥备注：通常假设G是连通的

欧拉通路和欧拉回路  定义：包含图（无向图或有向图）中每条边的简单通 路称为欧拉通路。 注意：欧拉通路是简单通路（边不重复），但顶点可重复  定义：包含图中每条边的简单回路称为欧拉回路。  如果图G中含欧拉回路，则G称为欧拉图。如果图G中 有欧拉通路，但没有欧拉回路，则G称为半欧拉图。 //备注：通常假设G是连通的

欧拉图中的顶点度数 ·连通图G是欧拉图当且仅当G中每个顶点的度数均 为偶数。 ·证明： →设C是G中的欧拉回路，则veVc,d(y)必等于v在C上出 现数的2倍（起点与终点看成出现一次）。 可以证明： (1)G中所有的边可以分为若干边不相交的初级回路。 (2)这些回路可以串成一个欧拉回路

欧拉图中的顶点度数  连通图G是欧拉图 当且仅当 G中每个顶点的度数均 为偶数。  证明： 设C是G中的欧拉回路，则vVG , d(v)必等于v在C上出 现数的2倍(起点与终点看成出现一次)。 可以证明： （1）G中所有的边可以分为若干边不相交的初级回路。 （2）这些回路可以串成一个欧拉回路

急售扇 全偶度图中的回路 ·若图G中任一顶点均为偶度点，则G中所有的边包含在若干 边不相交的简单回路中。 。证明：对G的边数m施归纳法。 。当m=l,G是环，结论成立。 。对于k21,假设当m≤k时结论成立。 考虑m=k+1的情况：注意δc≥2，G中必含简单回路，记为 C,令G'=G-Ec,设G中含s个连通分支，显然，每个连 通分支内各点均为偶数，且边数不大于k。则根据归纳 假设，每个非平凡的连通分支中所有边含于没有公共边 的简单回路中，注意各连通分支以及C两两均无公共边， 于是，结论成立

全偶度图中的回路  若图G中任一顶点均为偶度点，则G中所有的边包含在若干 边不相交的简单回路中。  证明：对G的边数m施归纳法。  当m=1, G是环，结论成立。  对于k1，假设当mk时结论成立。  考虑m=k+1的情况：注意G2, G中必含简单回路，记为 C，令G’=G-EC , 设G’中含s个连通分支，显然，每个连 通分支内各点均为偶数，且边数不大于k。则根据归纳 假设，每个非平凡的连通分支中所有边含于没有公共边 的简单回路中，注意各连通分支以及C两两均无公共边， 于是，结论成立

若干小回路串成欧拉回路 。若连通图G中所有的边包含在若干边不相交的简单回路中， 则G中含欧拉回路。 ●证明：对G中简单回路个数施归纳法。当=1时显然。 。假设k(21)时结论成立。考虑=k+1. 按某种方式对k+1个简单回路排序，令G=G-E(Ck+),设G 中含s个连通分支，则每个非平凡分支所有的边包含在相互 没有公共边的简单回路中，且回路个数不大于k。由归纳假 设，每个非平凡连通分支G均为欧拉图，设其欧拉回路是 C;'。因G连通，故Ck与诸C:都有公共点。 ● G中的欧拉回路构造如下：从Ck+1上任一点（设为vo)出发遍 历Ck1上的边，每当遇到一个尚未遍历的C与Ck+1的交点 (设为v),则转而遍历C:'上的边，回到继续沿Ck+1进行

若干小回路串成欧拉回路  若连通图G中所有的边包含在若干边不相交的简单回路中， 则G中含欧拉回路。  证明：对G中简单回路个数d施归纳法。当d=1时显然。  假设dk(k1)时结论成立。考虑d=k+1.  按某种方式对k+1个简单回路排序，令G‘=G-E(Ck+1)，设G’ 中含s个连通分支，则每个非平凡分支所有的边包含在相互 没有公共边的简单回路中，且回路个数不大于k。由归纳假 设，每个非平凡连通分支Gi均为欧拉图，设其欧拉回路是 Ci '。因G连通，故Ck+1与诸Ci ’都有公共点。  G中的欧拉回路构造如下：从Ck+1上任一点(设为v0 )出发遍 历Ck+1上的边，每当遇到一个尚未遍历的Ci '与Ck+1的交点 (设为vi '), 则转而遍历Ci '上的边，回到vi '继续沿Ck+1进行

关于欧拉图的等价命题 0 设G是非平凡连通图，以下三个命题等价： (1)G是欧拉图。 (2)G中每个顶点的度数均为偶数。 (3)G中所有的边包含在相互没有公共边的简单回路中

关于欧拉图的等价命题  设G是非平凡连通图，以下三个命题等价： (1) G是欧拉图。 (2) G中每个顶点的度数均为偶数。 (3) G中所有的边包含在相互没有公共边的简单回路中

半欧拉图的判定 ●设G是连通图，G是半欧拉图当且仅当G恰有两个奇度点。 ●证明： →设P是G中的欧拉通路（非回路），设P的始点与终点分别 是u,V,则对G中任何一点x,若x非u,V,则x的度数等于在 P中出现次数的2倍，而u,V的度数则是它们分别在P中 间位置出现的次数的两倍再加1。 ∈设G中两个奇度顶点是u,V,则G+v是欧拉图，设欧拉 回路是C,则C中含uv边，∴.C-uv是G中的欧拉通路。 (这表明：如果试图一笔画出一个半欧拉图，必须以两 个奇度顶点为始点和终点。)

半欧拉图的判定  设G是连通图，G是半欧拉图 当且仅当 G恰有两个奇度点。  证明:  设P是G中的欧拉通路(非回路)，设P的始点与终点分别 是u,v, 则对G中任何一点x, 若x非u,v，则x的度数等于在 P中出现次数的2倍，而u,v的度数则是它们分别在P中 间位置出现的次数的两倍再加1。  设G中两个奇度顶点是u,v, 则G+uv是欧拉图，设欧拉 回路是C, 则C中含uv边，C-uv是G中的欧拉通路。 (这表明：如果试图一笔画出一个半欧拉图，必须以两 个奇度顶点为始点和终点。)