离散数学是计算机专业基础课程之一。本课程重点讲解离散对象的计数问题、图论问题、网络流问题等计算机科学中的重要基本知识。本课程将为后续如数据结构、算法设计、复杂性理论提供必要的基础，课程内容在人工智能、机器学习、网络设计与分析等前沿领域有重要应用。课程重点培养学生逻辑思维能力及解决问题的能力。
欧拉图
Loading...
En provenance du cours de Shanghai Jiao Tong University
离散数学
15 notes
Rencontrer les enseignants
Long Huan 龙环助理研究员
计算机系
[音乐]
[音乐] [音乐]
大家好，本次我们介绍欧拉图
这是十八世纪哥尼斯堡镇的一个问题
这个镇上有一条河，就是在图中蓝色的部分表示一条河 它把这个地区呢分成了四块、
四个部分，分别用 A、 B、 C、 D 来表示。
为了 这个陆地之间的交通，他们修了七座桥，在图中用 七个黄色的方块表示。
当时的问题是：有没有一种方法 能够通过每一座桥一次且仅一次并且能够回到原点
这个问题当时有很长的一个争论 首次解决呢是欧拉在 1736
年，他为了解决这个问题，他首先把原始的问题抽象成 点和边。
这是第一次出现了点和边来描述图的这样一个概念 他用 ABCD
四个点来表示原始的四块陆地 然后两个点之间有一条边，当且仅当它们之间有一座桥
比如说我们看原来的两块陆地， A 和 D
之间有一条边 有一座桥的话，那么我们在新图中， A 和 D
中就有一条边 欧拉把这个问题抽象成，我们能否在右边这张图中有一种方法
笔从一个点出发，不离开纸张，经过 所有的边，一次且仅一次，然后回到了原始的出发点
我们把这个问题给它一个数学的一个描述，他说图 给了一个图
G ，包括两个元素：顶点集和边集。
那么从某一个特殊的点小 v 出发 我们问是否存在沿图中所有边一个连续的游走，这个游走呢要
用到当然会覆盖到所有的顶点，用到 边集中的每条边一次且仅一次，然后最后回到这个
v ，这个 v 你可以任意选了 只要存在这样一个能够回到原始顶点
并且用到所有边的这样一个方案的话，那么我们称原始图是一个欧拉图
而你这个用到的这样一个闭合的游走，就称为一个欧拉回路 我们看一个例子，这是一个新的图，我们说对这张
图而言，它是存在欧拉回路的，换句话说这张图是一个欧拉图，怎么样走呢？ 我们从最左边这个点小
v 开始出发，走第一个边第二个边 注意我这里加入了箭头只是为了强调我走的这个方向，并不是说它是一个有效图
接着走，大家可以看到，我们用到了所有的边一次 仅一次并且回到了原始的出发点
v ，所以说这是一个欧拉图 那么我们要解决哥尼斯堡七桥问题，一个最简单的方案，那么
我们说一共有七条边，那么我们却没举所有可能的七条边
的那个排列，那么是7的阶乘也就是5040种，五千零四十种
那么这在当时是一个很大的一个计算量，所以当时在欧拉之前没有人能够 给出这个问题肯定或者否定的结论
那么我们的问题是，欧拉当时是怎么样解决了这个问题的呢？他当然没有去尝试所有的504- 0种可能的走的路径
他是给了一个简单的一个定理，他给出了一个欧拉图的定理 他说原始的图 G 是欧拉图，当且仅当
图 G 是连通图，并且每个顶点的度数都是偶数 大家可以看到，欧拉定理它给出了
欧拉图这一个简单的判定条件，给了这样一个图我们只是首先去
游走一遍，或者是遍历一次，看它是否是 一个连通图。
如果是连通图的话，我们去检查每一个点的度数 如果点的度数都是偶数的话，那么欧拉定理告诉我们这个图一定是一个 欧拉回路图。
那么怎么样证明它？ 首先我们证明这个定理的必要性
也就说有欧拉图，是欧拉图的话那么每个点的度数 一定是偶数并且一定是一个连通图。
首先连通性是必然是显然的，因为 你的这个游走方案就告诉了你，你能够不离开原始的图
它必然是一个连通的这样一个性质。
第二个我们想要证的是每个顶点的 度数都是偶数，这个怎么样证明？这个证明其实也很简单，我们考虑其中任意一个点
我们说我们沿着欧拉回路去走
如果我们进入这个点一次，因为欧拉回路是要求我们要回到原始的出发点，所以我们必然会- 出去一次 否则它不是一个回路。
那么类似，如果它 这个点可能被重复用到，另外一次它再进来一次，它也必然出去一次
也就是我们沿着欧拉回路去走的话，每一个点 我进入一次，必然会出去一次，也就它度数一定是偶数
但这不是一个非常严格的证明，但是直观是比较清楚 我们这里重点想证一下的是这个定理的充分性
就是说我们已经知道图是连通图并且每个点的度数都是偶数的时候，我们怎么说明 它的图一定是欧拉图。
换句话说，怎么样说明原始的图中一定存在一个 用到所有边一次且仅一次的一个回路
这就是我们证明的目标 好了，我们为了证明它呢，我们
考虑图 G 中，最长的那个边不重复的一个游走方案 T
大家还记得游走的话，游走就是沿着这个图上的点和边的这样一个序列一个走的一个方案。
但是我们现在 选 T 呢有一个重要的性质，它不仅是一个边不重复的游走方案，并且是我们假设它是能够找到的最-
长的这一条 这个最长的性质非常重要，我们把这个游走方案用
v0,e1 然后 v1 一直到到 em,vm 表示出来，就是说我们从
v0 出发经过 e1 到 v1 ，类似 最后经过 到了 vm。
所以我们说 T ，因为它已经最长了 所以所有跟
vm，就 vm 这个点相关联的边呢，必然都已经含在
T 中 因为如果还有，还有边不在 T 中的话，那么我们可以从 vm
再走一次 但是我们说这个已经是没有的了，因为它已经是最长，并且我们已经知道
vm 的度数是偶数 因为前提说所有顶点的度数都是偶数。
那么我们说 vm 如果是出现在这个游走方案的中间
如果是出现在这个游走方案的中间 我们这里用蓝色表示了一次
vm 的出现 那么它出现在中间的时候
它的对它的度数贡献是多少？我们说 ei，假设它是
从 ei 进入 vm，然后通过 ei+1
出现 换句话说，我们每出现一次，如果是出现在这个游走序列中间的话
每出现一次它的度数是加二， vm 的度数是加二
但是我们现在又注意到， vm 又出现在了这个最长的游走方案的最末端
我们说这个部分 对它，对
vm 的度数贡献是加一 那么我们又知道
vm 的度数最后一定是一个偶数，那唯一的可能是什么呢？
唯一的可能是，一开始的这个 v0 和 vm，v0 和 vm 必然是同一个点 必然是同一个点。
也就是说， e1 对于 vm 的度数 贡献也是一的，换句话我们把原始的这个
划掉重新写，一开始的 v0 其实就是 vm ，所以这里有对它度数有加一
这最后对它度数有加一，中间如果 vm 出现度数是加二 这才可能使得 vm 的度数最后仍然是一个偶数。
换句话说 我们刚开始找到的这个最长的、 边不重复的这个游走方案，它其实是一个回路
因为它从 v0 出发，它最后又回到了它本身
那么我们现在证好的是什么？我们证好的，我们找到最长的这个边不重复的游走方案是一个回路
那么我们为了证明最后它是一个欧拉回路，那么我们还有什么需要做的？ 我们还需要做的是证明
T 中包含了所有的边 它不但是一个回路，并且是包含了所有的边
并且我们又知道它的边不重复的话，那么 T 其实就是我们要找的那个欧拉回路 反证法，假设
T 不是欧拉回路 我们又一开始知道了，那个因为我们现在是证的这个性质我们是已经知道它已经是一个连通图了
那么我们说，必然存在一个边 e
它不包含在这个，我们所找的这个 这个
T 中，但是它又跟 T 中的某一个点是相关联的，我们用图中表示
就说这后面这一整块我们都是表示的 是那个 T 的方案，现在我们说它
T 因为 它不是那个包含了所有的边，所以另外有一条
点啊，是一个，是一个诱点 它必然跟它是，跟这个 T
中的某一个点，我们是用蓝色表示出来这个点，它是相邻的 但是这个时候我们就会产生矛盾。
为什么呢？我们从右出发 我们进入这个 T ，T 在这个、
这个游走方案，我们沿着这个方案去走 大家可以看，沿着我红色所标记的这个方向去走。
我们其实是找到了什么 我其实是找到了一个新的游走方案
这个游走方案中，边仍然不会重复，但是这个游走方案包含了多 一条边，也就是说原始的
T 不是最长的 换句话说
我们就证明了，我们就证明了我们一开始找到的 T ，它确实是一个
包含了所有的边，一次且仅一次并且 是一个回路，也就说是一个欧拉回路。
至此我们也就证明了欧拉定理它的那个 定理中的那个充分必要性
那么我们用欧拉定理来看，回过头来看一下哥尼斯堡七桥问题 我们说马上能够得出结论，它不是一个欧拉图。
也就说不存在 一个方案能够经过所有的桥一次，且仅一次并且回到原始出发的那一块陆地
因为比如说这个 C 点的度数，我们说是 3 那个 D 点的度数也是 3
，它包含有度数为奇数，当然类似的你可以看到 那个
A、 B、 C、 D 他们都是奇度数的点 就这个定理虽然很简单，但是我们想说的是欧拉
图定理呢，它其实是开启了图论的这样一个 工作。
那么我们说，我们把这个问题稍微 改一下，就是原始的哥尼斯堡七桥问题改一下，就说我们不要求它是一个回路
我们只要要求经过所有的边，一次且仅一次。
换句话说，从形式化的方法讲 那个图 G 是 V 和 E 的话，问是否存在一个连续的游走方案
这个使得边，即大 E 中的每条边都用到正好一次
我们想说这显然，如果是非欧拉图的话如果 这样一个方案存在那么一定不是回路，因为它如果是回路，它就是欧拉图
现在你既然是，知道它不是欧拉图，又存在刚才 提的这个方案的话，那么一定不是一个回路。
我们看一个例子，这里是一个包含四个点的一个图 我们说它确实是存在满足前提的这样一个游走方案
我们从蓝色的点开始走，它首先走到下面这个黑色的点 然后接着到红色这点，接着走
大家可以看到，同样的我现在箭头只是表示我的一个游走的这样一个 方向，并没有说它是一个有向图。
换句话说我们确实存在一个从 蓝点出发，最后到达红点的这样一个游走方案，用到了所有的边 一次且仅一次。
而且在这个图中大家可以看到，蓝点的度数是 3 红点的度数是 3
，而另外的这两个黑点的度数，多少？ 从一个奇数点做到另外一个奇数点
我们把这样的一个游走方案取名为一个名字叫做"欧拉道路"，它不是一个回路，是一个-
欧拉道路 当然我们说任何一个欧拉回路的话，它必然也是一个欧拉道路
所以我们这里给出了有关判断 是否存在欧拉道路的一个定理。
它说图 G 中存在 欧拉道路，当且仅当图 G
是连通的，或者一 第一种情况，所有的顶点度数都是偶数，这种情况当然我们刚才已经讲过
其实就是存在欧拉回路，欧拉回路当然是用到了所有的边 一次且仅一次，它是满足要求的。
第二个 或者第二种情况，说除了两个顶点的度数为奇数以外，其它 顶点的度数都是偶数，那么这种情况它说也是存在欧拉道路的
并且我们能够马上得到度数为奇数的两个点，必然是欧拉道路的起点和终点
那么情况一的 证明呢，就是刚才讲的欧拉定理，我们现在只需要证明情况二
情况二的那个必要性，我们这里不再重复了，因为跟情况一的必要性证明其实是一样的
你把这个欧拉道路写出来你就能很快的得到，除了两个 除了起点和终点之外，其它点的度数都是偶数。
那么我们想 证明情况二的这样一个充分性 换句话说，我们说想证明除了两个顶点的
度数为基数之外，其它点都是偶数的情况下，并且是个连通图的话，我们想要构造出一个
欧拉道路，怎么样做呢？这是原始的图，下面这个图中给出了原始的图 G
它还拥有两个度数为奇数的点，分别是 U 和 V ，其它的点的度数都是偶数
现在我们做一件事，是在 U 和 V 之间连一条边，增加一条边，我们用小
e 来表示 大家注意，在这个 G
在这张新的图中，也就说 G 中增加了这个边 e
之后 这张图，它现在所有的点的度数都已经 是偶数了。
因为原始 U 和 V 的度数是基数，那么增加 e 之后 U 的度数和 V
的度数各增加了 e ，都变成了偶数，所以说 我们知道 G + e
这张图，它是一个欧拉图，存在一个欧拉回路 那么
我们说这个欧拉回路它必然会用到这条边 e 它必然会用到这条边 e。
那么我们把 e 去掉之后 去掉之后就得到了一条
就沿着原来的那个欧拉回路走，就得到了一条以 U 和 V 为起点和终点的这样一条欧拉道路
好了我们在用欧拉道路的判定条件来 再来看一次哥尼斯堡七桥问题，我们问有没有一种方案它经过所有的
边，一次且仅一次 其实我们不要求回到原始的出发目的，只要求它用到所有的边一次且仅一次
那么我们说，可以看到在这个欧拉当年抽象出来的图中 它的点的度数
它含有四个点的度数都是基数，所以我们用 那个 刚刚证明的判定条件马上能得到，它甚至也不含有欧拉道路
好了，我们刚才无论是欧拉道路问题，或者是欧拉回路问题
我们想说的是呢，它其实在日常生活中，大家给它取了一个名字叫做一笔画问题
就是我们是否能够把笔放在纸上，从一点出发，能够不离开纸的 把所有的边变了一次，所以叫一笔画。
总结一下我们本次课主要讲了两个定理，其实 第一个是欧拉图定理，什么是欧拉图呢？当且仅当
是连通图，并且所有的点的度数都是偶数。
这是一个非常容易判定的条件，所以使得 哥尼斯堡七桥问题，当年迎刃而解。
第二个我们说，我们现在不要求回路 只要求点不重复使用的情况下，并且所有的边都要被使用到的情况下，那么就是欧拉道路定理
所以说，就同样的给出了一个简单的判定条件，好了这就是本次课的内容
谢谢大家
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
