南京大学：《离散数学》课程教学资源（PPT课件讲稿）Lecture 20 欧拉图与汉密尔顿图

1 欧拉图与汉密尔顿图

欧拉图与汉密尔顿图 1

回顾 2 口内容1：通路与回路 口简单通路边不重复、初级通路点不重复 口内容2：无向图的连通性 口割点、割边，点/边连通度、K(G)≤入(G)≤δ(G), Whitney定理 口内容3：有向图的连通性 口强/单/弱连通，无向图的边定向

 内容1：通路与回路  简单通路边不重复、初级通路点不重复  内容2：无向图的连通性  割点、割边，点/边连通度、(G) (G)  (G)， Whitney定理  内容3：有向图的连通性  强/单/弱连通，无向图的边定向 2 回顾

本节提要 口内容1：欧拉图 口什么是欧拉图？ ▣欧拉图的充要条件？ 口如何构造欧拉回路？ ▣内容2：哈密尔顿图 口什么是汉密尔顿图？ 口哈密尔顿图的必要和充分条件？ 口哈密尔顿图有哪些应用？

 内容1：欧拉图  什么是欧拉图？  欧拉图的充要条件？  如何构造欧拉回路？  内容2：哈密尔顿图  什么是汉密尔顿图？  哈密尔顿图的必要和充分条件？  哈密尔顿图有哪些应用？ 本节提要

Kδnigsberg七桥问题（回顾） 4 K的NWGH莱U风 Leonhard Euler(1707-1783)

Königsberg七桥问题（回顾） 4 Leonhard Euler (1707 – 1783)

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

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

“一笔划”问题 7

“一笔划”问题 ？

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

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

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

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

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

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

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

欧拉图的充要条件  (2) 若连通图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进行