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

Presentation on theme: "离散数学─图论初步 南京大学计算机科学与技术系"— Presentation transcript:

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

2 内容提要 欧拉通路/回路 欧拉图的充要条件 半欧拉图的充要条件 构造欧拉回路的Fleury算法 随机欧拉图

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

4 “一笔划”问题 ？

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

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

7 全偶度图中的回路 若图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两两均无公共边，于是，结论成立。

8 若干小回路串成欧拉回路 若连通图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进行。

9 关于欧拉图的等价命题 设G是非平凡连通图，以下三个命题等价： (1) G是欧拉图。 (2) G中每个顶点的度数均为偶数。

10 半欧拉图的判定 设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中的欧拉通路。(这表明：如果试图一笔画出一个半欧拉图，必须以两个奇度顶点为始点和终点。)

11 构造欧拉回路 思想：在画欧拉回路时，画过的边不能再用。因此，在构造欧拉回路过程中的任何时刻，假设将画过的边删除，剩下的边必须仍在同一连通分支当中。

12 构造欧拉回路-Fleury算法 算法： 输入：欧拉图G
输出：简单通路P = v0e1v1e2,…,eiviei+1,…,emvm, 其中包含了EG中所有的元素。 1. 任取v0VG, 令P0=v0; 2. 设Pi=v0e1v1e2,…,eivi, 按下列原则从EG-{e1,e2,…,ei}中选择ei+1。 (a) ei+1与vi相关联； (b) 除非别无选择，否则ei+1不应是G-{e1,e2,…,ei}中的割边。 3. 反复执行第2步，直到无法执行时终止。

13 Fleury算法的证明 算法的终止性显然。 设算法终止时，Pm= v0e1v1e2,…,eiviei+1,…,emvm,
(1) Pm是回路，即v0=vm。 (2) Pm包括了G中所有的边。 令Gi=G-{e1,e2,…,ei} (1) (证明是回路)假设v0vm。由算法终止条件，在Gm中已 没有边与vm相关联。假设除最后一次外，vm在Pm中出现 k次，则vm的度数是2k+1, 与G中顶点度数是偶数矛盾。

14 Fleury算法的证明(续) (2) (证明含所有边)假设Pm没有包括G中所有的边，令Gm中所有非零度顶点集合为S（非空）, 令S’=VG-S, 则vmS’。 考察序列e1,e2,…ej,ej+1,…,em。假设j是满足vjS, 而vj+1S’的最大下标。 如果没有这样的j，G就不连通，矛盾。另外，ej+1一定是Gj中的割边。 令e是在Gj中与vj相关联的异于ej+1的边(非零度点一定有), 根据算法选择 ej+1(割边)的原则，e也一定是割边。但是，Gm中任意顶点的度数必是偶 数，e在Gm中的连通分支是欧拉图，e在Gm的某个 欧拉回路中，不可能是Gj的割边。矛盾。 v e vj vj+1 ej+1 vm S’ S

15 有向欧拉图 有向图中含所有边的有向简单回路称为有向欧拉回路。 含有向欧拉回路的有向图称为有向欧拉图。
下面的等价命题可以用于有向欧拉图的判定： 若G是弱连通的有向图，则下列命题等价： G中含有向欧拉回路。 G中任一顶点的入度等于出度。 G中所有边位于若干条相互没有公共边的有向简单回路中。 (证明与无向欧拉图类似。)

16 作业 教材[9.5] 给定简单图G（|G|3），构造另一个图G’如下： p.497: 18, 20, 28

17 附：随机欧拉图 设G是欧拉图，vVG，从v开始，每一步从当前点所关联边中随机选边，均可构造欧拉回路，则G称为以v为始点的随机欧拉图。
的随机欧拉图，则一定存在已经包含 了v所关联的所有边，却未包含G中所 有边的简单回路。

18 随机欧拉图的判定 欧拉图G是以v为始点的随机欧拉图当且仅当 G中任一回路均包含v。
 若G是以v为始点的随机欧拉图，假设有回路C不包含v. 令G‘=G-C, (G’可能不连通)，G’中包含v的那个连通分支一定是欧拉图，相应的欧拉回路包含了v关联的所有边，但不包含G中的所有边，与G是以v为始点的随机欧拉图矛盾。  若欧拉图G中任意回路均包含v。假设G不是以v为始点的随机欧拉图，则一定存在已经包含了v所关联的所有边，却未包含G中所有边的简单回路C，假设e是不在C中的一条边，e的端点必异于v，设一个是u。令从G中删除C中所有边的图为G‘，显然在G’中v是孤立点。而包含u的连通分支是欧拉图，因此u必包含在一回路中，但此回路不含v，矛盾。 (易推知：欧拉图G是以任一顶点为始点的随机欧拉图 当且仅当G本身是一个初级回路)