离散数学是计算机专业基础课程之一。本课程重点讲解离散对象的计数问题、图论问题、网络流问题等计算机科学中的重要基本知识。本课程将为后续如数据结构、算法设计、复杂性理论提供必要的基础，课程内容在人工智能、机器学习、网络设计与分析等前沿领域有重要应用。课程重点培养学生逻辑思维能力及解决问题的能力。
Smith定理
Loading...
From the course by Shanghai Jiao Tong University
离散数学
17 ratings
Meet the Instructors
Long Huan 龙环助理研究员
计算机系
[音乐]
[音乐] [音乐]
[空白_音频] 各位同学大家好，本次课我们讲解握手定理的应用
这张图中所有点的度数之和加起来正好是
边数之和的两倍，我们说这不是一个个别的现象，而是一个定理保证的
任给无向图，其中顶点度数的个数之和一定是边数的两倍
一个简单的推论是说，在任何一个图中，无向图中 奇数点的个数一定是偶数个
我们看这样一个貌似简单的定理在实际中有什么样的应用呢 首先介绍握手定理在哈密顿图相关问题中的一些结论
第一个想介绍的定理是 Smith 定理。
Smith 定理对于所有的3-正则图 包含图上任意一条边 e
的哈密顿回路必有偶数条 我们看下面这两个 3-
正则图的例子，就是每一个点度数都是 3 左边这张 3-
正则图它不存在哈密顿回路 证明很简单，哈密顿回路如果是从左边的
菱形出发，为了遍历右边的菱形，它必须要经过蓝色这个点 但是为了回到初始点，它必须第二次经过蓝色点，也就是说除了
初始点以外，有两个点被访问了两次，所以不存在哈密顿回路 而右边这张
3- 正则图我们以最顶点的这个边 为
e，我们能够找到一条包含 e 的哈密顿回路，如红色所示
但是我们又同时能够找到另外一条包含 e 的 哈密顿回路是图中的这个蓝色的这样一个回路
我们想说这个现象也不是一般的，它是由 Smith 定理所保证的 Smith
定理的严格证明有 很多版本，我们这里讲的是 Thomason 在
1978 年给出的这样一个证明 他的证明思路是怎样的呢？他说我们先固定图 G
中的一条边 e 我们将构造一个新的图 G'，G' 中的顶点的度数要不然为
1，要不然为 2 当它顶点度数为 1 的时候，我们能够证明
原始图 G 中必然有一条包含 e 的哈密顿回路 由于
G' 必然受到握手定理的这样一个
限制，所以我们知道 G' 中必然存在第二个点它的度数是 1。
因为由于刚才 度数为 1 的点和原始图 G 中哈密顿回路的这样一个对应关系
我们知道，原始图 G 中必然存在另外一条哈密顿回路，这就是证明了
原始图 G 中如果有一条包含 e 的哈密顿回路，那么必然存在第二条包含
e 的哈密顿回路，换句话说，包含 e 的哈密顿回路一定是偶数条
我们这里看一下严格的证明 我们 e 的两个端点分别用
v1 和 v2 表示 不失一般性，我们假设原图中确实有包含
e 的哈密顿回路 当然，我们说如果没有的话，那么定理频繁成立
我们将从 G 出发，构造一个新的图 G' G'
构造包括两点，构造它的顶点集以及构造它的边集 V'
中的每一个点都将代表原始图 G 中 一条包含
e 的哈密顿路径，注意的是，这里是哈密顿路径，而不是哈密顿回路
但是我们知道 V' 一定不是空的，因为我们一开始假设了有一条包含
e 的哈密顿回路 那么我们怎么样构造 e'
呢？ 这里的第一张图还是强调的是点的构造，原始图
G 中的一条 包含 e 的哈密顿路径在 G' 中体现为一个点
理解为一个点，我们把它叫做 vp，但是我们又由于知道我们现在 G 它本身是一个
3- 正则图，所以我们知道 vn 必然跟除了 vn-1
以外的两个点相连 它可能跟 v1 相连，但是也可能不相连，但是它必然
跟 v2 到 vn-1 中的另外一个点相连，我们用绿色表示
从绿色的这条路径出发，我们可以构造一条新的哈密顿路径 是
v1 走到 v2，一直走到 vk，它直接跳到了 vn，然后
按照 vn-1 一直走回到 vk+1，显然这仍然是一条哈密顿
路径，并且跟原始的 v1 到 vn 这一条哈密顿路径是不一样的
那么什么时候说 G' 中的两个点之间有一条边呢？
我们把 vp，vp' 这个二元组放入 E'
中，当且仅当它们所对应的哈密顿路径能够由刚才的构造 所生成。
关于 G' 有一个很特殊的性质，G'
中的点的度数只能是 2 或者是 1 这是为什么呢？我们说，因为
vn，它会跟除 vn-1 之外的至多 正好两个点相邻。
所以第一种情况是 vn 不跟 v1 相邻，那么它必然跟 v2
到 vn-1 之间的另外两个点相邻，这里表现为图中
就有两个绿色的线，也就是说从原始的哈密顿路径出发，我们可以构造两个新的哈密顿路径 还有另外一种情况，就是
vn 已经跟 v1 连好了，它们已经是相邻的 这种时候，vn
只会跟 v2 到vn-1 之间的另外一个点相邻
也就是说从原始的哈密顿路径出发，我们只能够构造出一条新的哈密顿路径 注意这里度数为
1 和原始图 G 中有一个哈密顿回路是一个当且仅当的关系
但是从 G' 出发来说，我们说由握手定理 度数为奇数的点必然出现偶数次，所以我们知道
原始的图 G 中必然还存在另外一条哈密顿回路
这条哈密顿回路将在 G' 中被抽象为另外一个度数为 1
的点 这就证明了我们的定理 纯包含
e 的哈密顿回路必然有偶数条 为了加深对定理的理解，我们看一下下面这个例子
这里给出了一个 3- 正则图，我们说 e 是其中的 1-2
这一条边，蓝色表示出来 我们从 1-2 出发，我们有一个哈密顿回路它是
是12348765 回到
1，但是由于我们的构造是用哈密顿路径，所以我们把 1 打了一个括号，表示暂时不考虑
在这个时候，我们注意到，最末的这个点，这个路径上最末的这个点 5 是跟
8 相邻的 用刚才的构造，我们构造出一条新的哈密顿路径，它是
12348567 8567
这个做好之后，我们做同样的 观察 7 和另外哪两个点相邻，它是分别跟
8 和 3 相邻 那么重复证明中的构造。
我们可以看到比如说 7 和 8 我们可以找到另外一条哈密顿路径它是
123 48765，但是这条路径呢我们说
它跟 1 中所出现的这个路径是一样的，所以说 我们不考虑它，那么我们考虑
7 和 3 相邻，它会产生一条怎样的哈密顿路径呢？
我们说按照这个新的策略走，我们走的是 1237
然后是 6584，注意到在原图中，这个就是已经是一条哈密顿回路了
就是说从原始的哈密顿回路出发，我们找到了 第二条哈密顿回路。
本次我们介绍了握手定理在 Smith 定理中的应用
可以看到握手定理这样一个简单的定理在 看似非常困难的一个定理中发挥了非常重要的作用
在下次课，我们将继续介绍握手定理在其他重要定理中的作用，谢谢大家！
[音乐]
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
