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