[音乐]
[音乐] [音乐]
[空白_音频] 各位同学大家好，本次课我们讲解握手定理的应用
这张图中所有点的度数之和加起来正好是
边数之和的两倍，我们说这不是一个个别的现象，而是一个定理保证的
任给无向图，其中顶点度数的个数之和一定是边数的两倍
一个简单的推论是说，在任何一个图中，无向图中 奇数点的个数一定是偶数个
我们看这样一个貌似简单的定理在实际中有什么样的应用呢 首先介绍握手定理在哈密顿图相关问题中的一些结论
第一个想介绍的定理是 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 定理中的应用
可以看到握手定理这样一个简单的定理在 看似非常困难的一个定理中发挥了非常重要的作用
在下次课，我们将继续介绍握手定理在其他重要定理中的作用，谢谢大家！
[音乐]
Long Huan 龙环助理研究员
