离散数学是计算机专业基础课程之一。本课程重点讲解离散对象的计数问题、图论问题、网络流问题等计算机科学中的重要基本知识。本课程将为后续如数据结构、算法设计、复杂性理论提供必要的基础，课程内容在人工智能、机器学习、网络设计与分析等前沿领域有重要应用。课程重点培养学生逻辑思维能力及解决问题的能力。
握手定理与图同构
Loading...
Из курса от партнера Shanghai Jiao Tong University
离散数学
18 оценки
Познакомьтесь с преподавателями
Long Huan 龙环助理研究员
计算机系
[音乐]
[音乐] [音乐]
各位大家好
我们本次介绍图中的一个基本的，但是非常重要的定理叫做握手定理 并且介绍一个图中的重要概念，叫做图同构的概念
首先什么是握手定理？我们假设这样一个场景，在宴会上呢，一共有 n
个人 他们其中的一些人互相握手，已经知道每一个人他的握手次数都是
a 次，那么我们想问的是，总共的握手次数 S 有多少？
那么这个问题显然是比较简单的，我们说 S=n·a/2 为什么是
n·a/2 呢？我们说，每个人握了 a 次，那么 n 个人一共是握手了
n×a 次 但每一次握手是一个双方的行为，所以我们在计算握手次数的时候，会除以
2 那么我们现在如果把问题稍微改一下，我们说，不是每一个人的握手次数都是相等的
而是我们知道每一个人的握手次数，比如说第一个人是 h1 次，第二个人是 h2
次，第 n 个人是 hn 次 那么同样的问题，总共的握手次数 S 是多少呢？
我们说，它是 S 等于 h1+h2 一直加到 hn 的和，再除以
2 这个证明跟刚才显然是一样的，我们继续算所有的
每一个人的握手次数加起来，但是握手是一个两方参与的行为，所以最后的 S
次数要除以 2 这个非常简单的一个性质，但是在图论中是一个非常 基础但是又很重要的一个概念，是握手定理
那么，我们这里回忆一下顶点的度，度是说那个每个点它的相邻的边的个数
那么最小的度，我们也有定义，还有最大的度
那么我们可以也关于度数有一些基本的概念，比如说 每个点的度数一定是小于等于边数。
第二个是说如果图是一个 path，是一个路径的话，那么呢，度数是
1，要不然是 2 1 的话就是两头，路径的两端，2 的话就是中间节点。
那么如果是 cn 的话，它的 也就是说是一个环的话，n 大的环，它的度数是 2，kn
的话 也就是 n 大的完全图示化，它的度数显然是 n-1，每一个点都跟其余的
n-1 个点相连 那么我们把刚才的那个宴会握手的情况，抽象成一个数学的概念
这是欧拉在 1732 年给出的一个结论，他给了一个无向图 G 顶点是用 V
表示，边是用 E 表示的话，那么每个点的度数之和 等于边数的两倍。
这个证明呢，其实就是我们刚才那个宴会问题证明的一个数学化的版本
我们说，因为从边的定义我们知道，每一条边与两个顶点相关联
所以我们在对第一部分每个点的度数做累加的时候 其实每一条边会被用到两次
因为一条边的话，它对它的两个相关联的点的度数各贡献了 1
所以说，我们说，把度数之和加起来等于边数之和的两倍
那么 握手定理虽然简单，它有一些重要的一些推论，比如说第一个推论
是说，在无向图中，度数为奇数的点的个数一定是有偶数多个
这个怎么样证明呢？我们说了，既然所有的点的度数之和是一个偶数
那么如果现在反证法，如果度数为奇数的点的个数是有奇数个
那么我们把这所有点的度数加在一起，它的和必然是一个奇数，那么这跟握手定理相违背
换句话说，我们就得到，度数为奇数的点，一定是有偶数多个
好了，介绍了握手定理之后，我们想介绍一个重要的概念叫图同构的概念
什么是图同构呢？现在给了两个对象，两张图 G ，点是用 V
表示，边是用 E 来表示，以及第二张图 G' 它的点和边分别是用
V' 和 E' 来表示 我们什么时候说这两张图同构，就是说存在
一个双射函数，双射函数的定义域是 第一张图的顶点，值域是第二张图的顶点集，V
到 V' 它不但是一个双射函数，并且满足一个额外的限制是说 如果 {x，y} 是原图
G 中的一条边，当且仅当 它们的项 f(x)，f(y)
所对应的这个边，是第二张图 那个 G' 的一条边。
就是注意 图在同构的这个定义中 虽然 f，f
是双射函数，就相当于是对点的一个限制 双射就是单射并且是满射。
而在额外的这个边上的限制，就是要求了边之间的一个对应关系 我们用这样一个符号来表示 G 和 G'
是同构的 那么同构的图的直观是什么？ 同构的图，从某种意义上来说，它们就是一张图，从数学的
一个角度上，它们唯一的不同就是顶点的名字，或者顶点的排列方式不同 我们可以看一个例子，就增加我们的理解。
第一张图我们说顶点是 abcde 是五个顶点，五条边。
第二张图是一个星形图 它用到的顶点的名字，我们是用
1、 2、 3、 4、 5 这样来表示，当然也是包含了五条边
我们现在说这两张图其实是同构的 那么要说它们是同构的，怎么样证明的呢？就是说要找到这样一个
顶点之间的双射函数，并且它保持了边的对应关系 这里我们给出了一个这样的函数，f
它说我把 a 映射到 1 把 b 映射到 2，c 映射到 3，d 映射到 5，e
映射到 4 首先我们说这显然是一个双射函数，是一个单射
并且是一个满射函数，其次我们想要验证的是它 保持了边之间的一个对应关系。
我们不一一验证，举两个例子 我们比如说，a 和 e 是原图中的一条边，a
和 e 是原图中的一条边 那么在这个函数下，a 被映射到 1
c 被映射到 3 那么我们说，1 和
3 之间 在这个右边这个图之间，也确实是有一条边的
然后我们再说，也就是原图中的一条边，被映射到 在这个函数下被映射到星图中的一条边。
类似的我们说，比如说原图中，原始的 a 和 e 之间是没有边 那么在这个函数下，我们看一下，a
被映射到了 1 e 被映射到了 4，那么在
1 和 4 之间 在这个星图中也是没有边的。
就是原图中 没有边的地方，在这个函数下对应的对象也没有边
当然我们需要，如果你要证明它是一个同构的话，严格来讲你要验证所有的边都满足这样一个 当且仅当的一个关系，这是一个比较简单的例子。
我们说图同构的判定是一个很困难的问题 在 2015 年
11 月 10 号 芝加哥大学的 Babai
教授都还是 关于图同构问题做出了一个最新的结论
好了，我们介绍了图同构之后，我们想介绍一个 一个简单的计数概念，就是图的一个计数
假如说我们现在知道顶点集合的大小是 n，也就是图的
G 是 n 那么我们是问，用这 n 个顶点，一共能构成
多少个图？首先我们说，如果我们 假设了所有的顶点都不一样的话，这个问题其实是比较简单的
那么要，首先我们考虑包含了所有可能边的图 也就是说，kn，n
大的完全图的边上，边数有多少？ 它说，我们就是从
V 个顶点中任意选两个，这里是 V 个顶点中间任意选两个
我们说有多少种选法，那么显然是等于 n 选 2，n 选 2
那么我们是要问包含了 n 个顶点的图一共有多少，那么
这 n 选 2 个边，可能在图中，也可能不在图中，换句话说
以 n 个点为顶点的图，一共有 2 的 n 选 2
次方种 但是我们想说的是，这些图之间很多图其实是同构的
比如说我们当 n=3 的时候，我们说
n=3 并且只含有一条边的图，我们说，这三种 这下面的这个边存在
1、 2 之间，存在 1、 3 之间，或者存在 2、 3 之间 这三个图是同构的。
所以我们想问，如果考虑结构上的相似性，或者换句话讲 如果把所有同构的图都理解成一个图的话，那么
这样计数图的个数又有多少？这是我们的问题 比如说
含有三个顶点的彼此不同构的图，我们看一下，它一共有多少
它含有三个边的当然只有一个，含有两个边的也只有一个，含有一个边的
不同构的图只有一个，当然不含边的图，就是空图，也只有一个 换句话说，它是，一般来说，含有
n 个顶点的彼此不同构的图是小于 2 的 n 选 2
次方，在这里就是说四个，是小于 2 的 3 选 2 也就是八个。
这里就给出了，但是无论如何，2 的 n 选 2，给出了我们一个净量图的个数的一个上界
换句话说，不会超过 2 的 n 选 2 次方。
那么我们还想得到一个下界 我们任意给了一个图，我们想问的是，这个图它至多与多少个图
同构？我们说它至多只与 n!
个 图同构，这是，这也应该也是比较自然，因为我们说，我们把点
做排列，一共只可能有 n!，n 个点只可能有 n!
个排列 但是我们说，这个也是一个比较粗的一个估计。
比如说当 n=3 的时候，3!=6
但是，与只包含一个边的那个三阶图
它同构并且不相同的图没有六个，其实也只有 包括它本身，只有三种。
大家可以看到，这条边是可能在 1、 3 之间，也可能在 1、 2 之间，也可能在
2、 3 之间 换句话说，但是我们说，刚才这个东西，它虽然 n!
虽然也是一个比较粗略的估计，但是它们确实给了我们一个下界
就是说我们把所有的图做划分的话，划分的标准是两张图在同一个类中，当且仅当它们是同构的
我们说，每一个划分块它的大小最多是 n!。
换句话说，那么不同构的图 至少有多少个呢？至少有 2 的 n 选 2 除以 n!
种 因为它最多与 n!
个相同构，那么一共有多少个 不同构的可能，那就是 2 的 n 选 2 除以 n!。
换句话说，我们想要计量的 n 个顶点，并且不同构的图的 x
个数，一定是夹在红色和蓝色这两块之间 现在我们想估计一下 x 的大小。
这里我们把 上下界都取了一个对数，二维体的一个对数，为了方便我们的
我们的陈述，大家可以看到，我们对上界取了对数之后，它大概是 2
的 它大概是 2 分之 n 平方再乘以 1 减去 n 分之一，这样一个数量级
然后我们对下界，也是类似地取了一个对数 它是等于
n 选 2 减去 log₂n!，当然我们说 n!
是小于 nⁿ 所以我们把 n!
用 nⁿ 代替 得到一个新的一个下界，然后是整理之后 得到是
n² 除以 2，再乘以 1 减去 1 除以 n 再减去 二倍 log₂n
除以 n 这样一个值 注意到我们现在方框所表示出来的这个上界
或者下界也好，它们中间占主导的项 都是二分之
n 平方，或者比如说我们在上界中，这个随着 n 的增大 后面这个 1 减去
一分之 n，其实是可以忽略的，类似地在下界中 随着 n 的逐渐，比如说当 n
趋近于无穷的时候 n 分之一或者是 n 分之 log₂n 都是可以忽略的项。
换句话说，用我们之前介绍的 这样一个渐进比较的这样一个概念的话，我们说
x 是多少，我们给出了一个 x 的估计，大概是 Θ 的 2 的二分之 n 平方这样一个数量级。
就是说大概是按照 这个指数平方的，按照指数的这样一个数量级在增长
好了，我们本次课介绍了握手定理，以及介绍了 图同构，并且基于图同构，我们介绍了图上的一些比较简单的一些技术
谢谢大家
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
