图的同构计数

II.图的同构

\Large{1,2,4,11,34,156,1044\cdots}\\


\color{red}{\sf Part. 1}

在欣赏一个有趣的数列前,我们需要引入一个图论概念:同构

A,BA,B A,B 两图同构的意思是: AAA 图的顶点可以经过一定的重新标号,使得它的点集和边集与 BBB 相同。

例如,以下两个图是同构的:

因为如果将左图的 (3,4) 两点交换,两图的点集和边集是相等的。

再如,对于有 444 个顶点的简单无向图,共有 111111 种互不同构的图:

现在问题来了: nnn 个顶点组成的简单无向图中,有多少种图互不同构?

这个问题的答案便是文章开头的数列——A000088

Part.2\color{red}{\sf Part.2}\color{red}{\sf Part.2}

为了解决这个问题,我们需要求助于数学的另一领域:群论。

将图的顶点重新标号,就相当于对点集进行置换,所有的标号方式便构成了一个置换群 GGG 。我们要求的即是在 GGG 作用下本质不同的图的个数。对于有 nnn 个顶点的图,所有的标号方式便是顶点的全排列,即 |G|\=n!|G|=n!|G|=n! 。

现在隆重请出 Burnside{\rm Burnside}{\rm Burnside} 引理:

动图封面

|X/G||X/G||X/G| :集合 XXX 在群 GGG 作用下的轨道数(或本质不同元素数)

|Xg||X\^g||X\^g| :在变换 ggg 下, XXX 集合中的不动点数

举个例子

在本题中, XXX 即为 nnn 个顶点可以构成的 2n(n−1)/22\^{n(n-1)/2}2\^{n(n-1)/2} 个简单无向图的集合, |X/G||X/G||X/G| 即为所求。难点在于怎么求 |Xg||X\^g||X\^g|,即对于某个点集置换 ggg 而言,有多少张图在经历变换 ggg 后依然和原来的图相同?

Part.3\color{red}{\sf Part.3}\color{red}{\sf Part.3}

好了,让我们随机抽取一名幸运置换 ggg 进行研究,看看有多少张图在经历 ggg 后纹丝不动。

若隐若现的边太麻烦啦!不妨假设所有边都已存在,现在在我们面前的是一个 nnn 个节点的完全图,然后我们需要给边们染色,染成存在或不存在两种颜色,从而得到 XXX 中所有的图。

如何判断染成什么样子可以使得它成为置换 ggg 中的不动点呢?

注意到有些边是等价的,等价的边一定要染成同一个颜色,要么同时存在,要么同时不存在

例如一个三个顶点的三角形,如果置换 ggg 的作用是将三个顶点顺时针轮换,那么这三条边是等价的(同属一个等价类),要么同时存在(形成一个完整的三角形),要么同时不存在(形成三个孤立的顶点)。不可能出现有两条边存在,一条边不存在的情况,否则经过一次旋转,缺口便到了另外两个点间,与原来的图就不同了。注意到此时三边同属 11 个等价类,每个等价类要么染要么不染,因此在此置换 gg 下有 2\^1=22\^1=2 个不动点。

还是这个三角形,这回置换 gg 变为交换两个点,另一个点不动。那么两个动点间的边单独属于一个等价类,另外两条边属于另一等价类,一共有 22 个等价类。每个等价类要么染要么不染,因此再此置换 gg 下有 2\^2=42\^2=4 个不动点。

换句话说,对于置换 gg 如果存在 kk 个边的等价类,那么 XX 中就有 2\^k2\^k 个不动点。即:

|X\^g|=2\^k\\|X\^g|=2\^k\\

\color{red}{\sf Part.4}\color{red}{\sf Part.4}

好啦,接下来的问题就是求 kk ——置换 gg 下边的等价类个数。这部分是关键,而且有些绕,我们分两步走:

第一步,我们要将 gg 拆分为若干个不相交的循环置换。

这是什么意思呢?举个例子, gg 可以把点 \{1,2,3,4,5,6\}\{1,2,3,4,5,6\} 置换成 \{2,3,1,5,4,6\}\{2,3,1,5,4,6\} ,可以记作: g= \begin{pmatrix} 1 \& 2 \& 3 \& 4 \& 5 \& 6\\ 2 \& 3 \& 1 \& 5 \& 4 \& 6 \end{pmatrix}g= \begin{pmatrix} 1 \& 2 \& 3 \& 4 \& 5 \& 6\\ 2 \& 3 \& 1 \& 5 \& 4 \& 6 \end{pmatrix} 。注意到这个置换可以分解成几个不相交的部分,其中每个部分都是一个循环:

\begin{pmatrix} 1 \& 2 \& 3 \& 4 \& 5 \& 6\\ 2 \& 3 \& 1 \& 5 \& 4 \& 6 \end{pmatrix}=\begin{pmatrix} 1 \& 2 \& 3\\ 2 \& 3 \& 1 \end{pmatrix} \circ \begin{pmatrix} 4 \& 5\\ 5 \& 4 \end{pmatrix} \circ \begin{pmatrix} 6\\ 6 \end{pmatrix}\\\begin{pmatrix} 1 \& 2 \& 3 \& 4 \& 5 \& 6\\ 2 \& 3 \& 1 \& 5 \& 4 \& 6 \end{pmatrix}=\begin{pmatrix} 1 \& 2 \& 3\\ 2 \& 3 \& 1 \end{pmatrix} \circ \begin{pmatrix} 4 \& 5\\ 5 \& 4 \end{pmatrix} \circ \begin{pmatrix} 6\\ 6 \end{pmatrix}\\

现在将我们当前研究的置换 gg 拆成 KK 个循环,长度分别为 b_1,b_2,\cdots,b_Kb_1,b_2,\cdots,b_K 。

第二步,将边按照端点分成两类

1.端点同时存在于同一循环内的边。设循环长度为 bb ,则次循环共有 \left \lfloor \frac{b}{2} \right \rfloor \left \lfloor \frac{b}{2} \right \rfloor 个等价类。例如对于长度为 66 的循环置换 \begin{pmatrix} 1 \& 2 \& 3 \& 4 \& 5 \& 6\\ 2 \& 3 \& 4 \& 5 \& 6 \& 1 \end{pmatrix}\begin{pmatrix} 1 \& 2 \& 3 \& 4 \& 5 \& 6\\ 2 \& 3 \& 4 \& 5 \& 6 \& 1 \end{pmatrix} ,我们把这 66 个点排成正六边形:

颜色相同的边同属于一个等价类

不难发现两条边等价当且仅当它们长度相等,等价的边必须同时染/不染,否则会导致图案不具有旋转对称性,经过循环置换后也必定与原图不同。而正 bb 边形中,共有 \left \lfloor \frac{b}{2} \right \rfloor \left \lfloor \frac{b}{2} \right \rfloor 种长度不同的线段,也就是对应\left \lfloor \frac{b}{2} \right \rfloor \left \lfloor \frac{b}{2} \right \rfloor 个边的等价类。得证。

因此这一类边一共贡献了 \sum_{i=1}\^K\left \lfloor \frac{b_i}{2} \right \rfloor \sum_{i=1}\^K\left \lfloor \frac{b_i}{2} \right \rfloor 个等价类。

2.端点存在于不同循环内的边。例如 \begin{pmatrix} 1 \& 2 \& 3\\ 2 \& 3 \& 1 \end{pmatrix} \circ \begin{pmatrix} 4 \& 5\\ 5 \& 4 \end{pmatrix} \circ \begin{pmatrix} 6\\ 6 \end{pmatrix}\begin{pmatrix} 1 \& 2 \& 3\\ 2 \& 3 \& 1 \end{pmatrix} \circ \begin{pmatrix} 4 \& 5\\ 5 \& 4 \end{pmatrix} \circ \begin{pmatrix} 6\\ 6 \end{pmatrix} ,则连接 3,43,4 的边不在同一循环内。这时,设两个循环的长度分别为 b_1,b_2b_1,b_2 ,那么两个循环间共有 b_1b_2b_1b_2 条这样的边。

循环(1,2,3)与(4,5)间共有6条边

每条边经过 {\rm lcm}(b_1,b_2){\rm lcm}(b_1,b_2) 次循环后会回归原位,所以每个等价类大小为 \\{\rm lcm}(b_1,b_2){\rm lcm}(b_1,b_2) 。也就是说,一共有 \frac{b_1b_2}{{\rm lcm}(b_1,b_2)}=\gcd(b_1,b_2)\frac{b_1b_2}{{\rm lcm}(b_1,b_2)}=\gcd(b_1,b_2) 个等价类。别忘了,这只是 gg 内其中两个循环产生的贡献,要把每对循环的贡献累加起来,也就是: \sum_{i=1}\^K\sum_{j=1}\^{i-1}\gcd(b_i,b_j)\sum_{i=1}\^K\sum_{j=1}\^{i-1}\gcd(b_i,b_j) 个等价类。

至此两种情况已经分类讨论完毕,边的等价类个数就等于两种情况数量之和:

k=\sum_{i=1}\^K\left \lfloor \frac{b_i}{2} \right \rfloor +\sum_{i=1}\^K\sum_{j=1}\^{i-1}\gcd(b_i,b_j)\\ |X/G|=\frac{1}{|G|}\sum_{g\in G}2\^k\\k=\sum_{i=1}\^K\left \lfloor \frac{b_i}{2} \right \rfloor +\sum_{i=1}\^K\sum_{j=1}\^{i-1}\gcd(b_i,b_j)\\ |X/G|=\frac{1}{|G|}\sum_{g\in G}2\^k\\

是不是感觉离成功不远了呢(

\color{red}{\sf Part.5}\color{red}{\sf Part.5}

其实到了这里,我们已经找到计算文章开头数列的方法了。但是,别忘了 |G|=n!|G|=n! ,枚举每一个置换 gg ,时间复杂度少说也得 O(n!)O(n!) 。我们是否以优化一下计算方法呢?

注意到有许多置换会被重复计算,如下面两个置换:

\begin{pmatrix} 1 \& 2 \& 3\\ 2 \& 3 \& 1 \end{pmatrix} \circ \begin{pmatrix} 4 \& 5\\ 5 \& 4 \end{pmatrix} \circ \begin{pmatrix} 6\\ 6 \end{pmatrix}\qquad\begin{pmatrix} 1 \\ 1 \end{pmatrix} \circ \begin{pmatrix} 2 \& 3\\ 3 \& 2 \end{pmatrix} \circ \begin{pmatrix} 4 \& 5 \& 6\\ 6 \& 4 \& 5 \end{pmatrix}\\\begin{pmatrix} 1 \& 2 \& 3\\ 2 \& 3 \& 1 \end{pmatrix} \circ \begin{pmatrix} 4 \& 5\\ 5 \& 4 \end{pmatrix} \circ \begin{pmatrix} 6\\ 6 \end{pmatrix}\qquad\begin{pmatrix} 1 \\ 1 \end{pmatrix} \circ \begin{pmatrix} 2 \& 3\\ 3 \& 2 \end{pmatrix} \circ \begin{pmatrix} 4 \& 5 \& 6\\ 6 \& 4 \& 5 \end{pmatrix}\\

它们间没有本质上的区别,对应的 kk 值都相等(因为 bb 都是 1,2,31,2,3 ),本可以统一计算。

一般地,如果两个置换的循环长度排序后一一相等,那么两者对答案的贡献 2\^k2\^k 是相等的。因此,与其枚举每一种置换再拆分,不如枚举 nn 的拆分代表一类置换,再统一计算贡献。

例如 n=5n=5 时,它的拆分有 (1,1,1,1,1),(1,1,1,2),(1,1,3),(1,2,2),(1,4),(2,3),(5)(1,1,1,1,1),(1,1,1,2),(1,1,3),(1,2,2),(1,4),(2,3),(5) ,其中 (1,2,2)(1,2,2) 统一代表了形如

\begin{pmatrix} * \\ * \end{pmatrix} \circ \begin{pmatrix} * \& *\\ * \& * \end{pmatrix} \circ \begin{pmatrix} * \& *\\ * \& * \end{pmatrix}\\\begin{pmatrix} * \\ * \end{pmatrix} \circ \begin{pmatrix} * \& *\\ * \& * \end{pmatrix} \circ \begin{pmatrix} * \& *\\ * \& * \end{pmatrix}\\

的置换。也就是循环长度 b=\{1,2,2\}b=\{1,2,2\} 的置换。

那么对于某个拆分,如何计算有多少对应的置换呢?

首先 1\sim n1\sim n 随便放一共有 n!n! 种方案,但长度为 bb 的循环会贡献 b!b! 倍重复方案。所以单是分配每个元素在哪个循环中就有 \frac{n!}{\prod(b_i!)}\frac{n!}{\prod(b_i!)} 种方案。

接着是循环的内部分配,也就是 b_ib_i 个元素的圆排列,有 \prod(b_i-1)!\prod(b_i-1)! 种方案。

但事实上,对于长度相等的循环它们之间可以彼此交换,本质上是一样的,因此还是会算重。设 cc 表示表某个长度的循环的个数,则会算重 c!c! 倍。因此答案还需除以 \prod(c_i!)\prod(c_i!) 。

结合上述三项,可以得到,拆分 b_ib_i 所对应的置换个数为:

\frac{n!}{\prod(b_i)\prod(c_i!)}\\\frac{n!}{\prod(b_i)\prod(c_i!)}\\

用这个式子改进之前的 n!n! 枚举算法,可以得到:

|X/G|=\frac{1}{|G|}\sum_b \frac{n!}{\prod(b_i)\prod(c_i!)} 2\^k\\|X/G|=\frac{1}{|G|}\sum_b \frac{n!}{\prod(b_i)\prod(c_i!)} 2\^k\\

|G|=n!|G|=n! ,里外两项正好抵消,得到最终的形式:

\large{|X/G|=\sum_b \frac{2\^k}{\prod(b_i)\prod(c_i!)}\\ k=\sum_{i=1}\^K\left \lfloor \frac{b_i}{2} \right \rfloor +\sum_{i=1}\^K\sum_{j=1}\^{i-1}\gcd(b_i,b_j)}\\\large{|X/G|=\sum_b \frac{2\^k}{\prod(b_i)\prod(c_i!)}\\ k=\sum_{i=1}\^K\left \lfloor \frac{b_i}{2} \right \rfloor +\sum_{i=1}\^K\sum_{j=1}\^{i-1}\gcd(b_i,b_j)}\\

大功告成。

最后再提一下时间复杂度。DFS枚举 nn 的拆分 bb ,再 O(K\^2)O(K\^2) 求 kk 。增长速度是 A000041A296010 的乘积。前者增速是 O\left (\frac{e\^{\sqrt{n}}}{n}\right )O\left (\frac{e\^{\sqrt{n}}}{n}\right ),后者不知道。估计总复杂度大概在 O(10\^{\sqrt{x}})O(10\^{\sqrt{x}}) 左右。

\color{red}{\sf Part.6}\color{red}{\sf Part.6}

不妨思考形式更一般的问题:

nn 个节点的完全无向图,用 mm 种颜色给每条边染色,可以染出几种互不同构的图?

答案十分简单,只需要将上述式子中的 22 改为 mm 即可:

\large{|X/G|=\sum_b \frac{\color{red}m\^k}{\prod(b_i)\prod(c_i!)}\\ k=\sum_{i=1}\^K\left \lfloor \frac{b_i}{2} \right \rfloor +\sum_{i=1}\^K\sum_{j=1}\^{i-1}\gcd(b_i,b_j)}\\\large{|X/G|=\sum_b \frac{\color{red}m\^k}{\prod(b_i)\prod(c_i!)}\\ k=\sum_{i=1}\^K\left \lfloor \frac{b_i}{2} \right \rfloor +\sum_{i=1}\^K\sum_{j=1}\^{i-1}\gcd(b_i,b_j)}\\

因为在原问题中,每条边有存在/不存在两种情况,这等价于用两种颜色给每条边染色,不动点数为 2\^k2\^k 。现在改为用 mm 种颜色染色,自然就是 m\^km\^k 了。
**

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇