[音乐]
[音乐] [音乐]
各位大家好
我们本次介绍图中的一个基本的,但是非常重要的定理叫做握手定理 并且介绍一个图中的重要概念,叫做图同构的概念
首先什么是握手定理?我们假设这样一个场景,在宴会上呢,一共有 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 平方这样一个数量级。
就是说大概是按照 这个指数平方的,按照指数的这样一个数量级在增长
好了,我们本次课介绍了握手定理,以及介绍了 图同构,并且基于图同构,我们介绍了图上的一些比较简单的一些技术
谢谢大家