开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 非标定的n阶无向图的非同构个数 -> 正文阅读

[数据结构与算法]非标定的n阶无向图的非同构个数

非标定的n阶无向图的非同构个数

特别鸣谢wp师兄跟我的讲解

问题分析：

1. 先不考虑同构，只管标定图的数量

首先我们先从标定图开始看，总共有多少个n阶标定图？

其实这就相当于固定了点数，数边的数量。共有 $n (n ? 1) / 2$ 条边，那么总共就有 $2^{\frac{n(n-1)}{2}}$ 个标定图（最后发现这个数量并没有用

2. 考虑同构，并将这些标定图进行分组

接下来我们来将这些图分类，我们不妨设共有 $t$ 个不同构的图记作 $G_1,G_2,...,G_t$ ，然后我们再设一个集合，取出所有标定图中与其同构的图，共同放入这个集合中，记作 $S\{G_i\}$ ：

$S\{G_1\}=\{G_{11},G_{12},G_{13},...,G_{1k_1}\}$

$S\{G_2\}=\{G_{21},G_{22},G_{23},...,G_{2k_2}\}$

$. . .$

$S\{G_t\}=\{G_{t1},G_{t2},G_{t3},...,G_{tk_t}\}$

因为这些图之间都是不同的，我们可以得到 $\sum_{i=1}^t|S\{G_i\}|=2^{\frac{n(n-1)}{2}}$

3. 观察被分到一起的标定图的组

然后我们取出其中一个集合进行观察，例如 $S\{G_1\}=\{G_{11},G_{12},G_{13},...,G_{1k_1}\}$

首先给定一个 $G_1$ 的非标定图，你给他任意标定，一定是与 $G_1$ 同构的。或者换一个说法，对于集合中的第一个元素 $G_{11}$ ，你对它的顶点做任意的置换，得到的图 $G_{11}'$ 一定是与 $G_{11}$ 同构的。

但是这里要注意，不是每次置换都会得到一个新的标定图。

例如下图中，左边为 $G_{11}$ 其六种置换中有两个与自身相同的，剩下的四种置换也只能得到两个不同的标定图。因此在这个例子中 $S\{G_1\}|=3$

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eWPhoRRN-1639494629532)(C:\Users\user\AppData\Roaming\Typora\typora-user-images\image-20211214170228179.png)]

因此， $S\{G_1\}$ 中就是 $G_{11}$ 的置换去同构之后剩下的部分。

那么究竟有多少个置换呢？我们用集合 $S_{ij}$ 表示从 $G_{1i}$ 变成 $G_{1j}$ 的所有置换。例如 $S_{12}$ 表示从 $G_{11}$ 可以映射到 $G_{12}$ 的所有可能的映射

我们知道所有的置换数相加应该等于 $n!$ ，那么我们以 $G_{11}$ 为置换的作用图，可以得到：

$\sum_{i=1}^{k_1}|S_{1i}|=n!$

通过上面的例子观察可以发现一个奇妙但是又比较自然的规律：

$S_{11}|=|S_{12}|=|S_{13}|=...$

即从 $G_{11}$ 出发得到自身和得到其他图的映射的数目相等。

那么接下来我们对它进行一个证明：

首先设我们的 $S_{11}| = x. S_{11}=\{f_1,f_2,...,f_x\}$ ，即我们自己置换到自己的数量为 $x$ ，接着我们来尝试推 $S_{12}$ 的数目

首先，我们一定会存在一个映射 $f$ ，使得 $f\cdot G_{11}=G_{12}$

那么我们可以得到 $\forall f_i\in S_{11},\ \ f\cdot f_i\cdot G_{11} = G_{12}$ ，同时 $f_i$ 互不相同可以推出 $f\cdot f_i$ 也互不相同，所以每有一个可以到自己的置换 $f_i$ ，就存在一个到 $G_{12}$ 的置换 $f\cdot f_i$ ，并且置换之间互不相同

那么也就是说， $\forall f_i\in S_{11},\ \ f\cdot f_i\in S_{12}$ ，因此 $|S_{12}|\ge|S_{11}|$

接着我们设 $S_{12}=\{g_1,g_2,...,g_y\}$

那么 $S_{12}$ 中的映射满足 $\forall g_i\in S_{12},\ \ g_i\cdot G_{11} = G_{12}$ ，同时对于刚刚的满足 $f\cdot G_{11}=G_{12}$ 的映射 $f$ ，我们可以找到它的逆映射 $f^{-1}$ ，那么我们就有 $f^{-1}\cdot G_{12}=G_{11}$

那么我们可以得到 $\forall g_i\in S_{12},\ \ f^{-1}\cdot g_i\cdot G_{11} = G_{11}$ ，同时 $g_i$ 互不相同可以推出 $f^{-1}\cdot g_i$ 也互不相同，所以每有一个可以到 $G_{12}$ 的置换$ g_i $，就存在一个到自己的置换$ f^{-1}\cdot g_i$，并且置换之间互不相同

那么也就是说， $\forall g_i\in S_{12},\ \ f^{-1}\cdot g_i\in S_{11}$ ，因此 $|S_{12}|\le|S_{11}|$

综上可得： $S_{11}|=|S_{12}|$

同理可得：

$S_{11}|=|S_{12}|=|S_{13}|=...=|S_{1k_1}|$

$S_{22}|=|S_{21}|=|S_{23}|=...=|S_{2k_1}|$

$. . .$

$S_{k_1k_1}|=|S_{k_11}|=|S_{k_12}|=...=|S_{k_1k_1-1}|$

同时，只需要一组逆映射，则可以推出 $S_{ij}|=|S_{ji}|$ ，即从图 $G_{1i}$ 到图 $G_{1j}$ 的映射数量一定等于从图 $G_{1j}$ 到图 $G_{1i}$ 的映射数量

因此我们可以将那个从 $G_{11}$ 出发的式子转化为

$\sum_{i=1}^{k_1}|S_{ii}|=n!$

4. 回到组与组之间

我们对第一组进行了一定的分析，得到了上面的式子 $\sum_{i=1}^{k_1}|S_{ii}|=n!$

为了方便区分这是第几组，我们给 $S$ 加上上标 $^{(1)}$ ： $\sum_{i=1}^{k_1}|S_{ii}^{(1)}|=n!$

那么对于所有的 $t$ 组同构所构成的集合，我们都可以得到一个这样的等式： $\forall 1\le p\le t,\sum_{i=1}^{k_p}|S_{ii}^{(p)}|=n!$

那我们将这里所有的等式加起来就可以得到：
$\sum_{p=1}^{t}\sum_{i=1}^{k_p}|S^{(p)}_{ii}|=t*n!\\ t=\frac{\sum_{p=1}^{t}\sum_{i=1}^{k_p}|S^{(p)}_{ii}|}{n!}$
而我们回顾我们分组的过程，就可以发现 $\sum_{p=1}^{t}\sum_{i=1}^{k_p}$ 其实就是对所有的标定图 $G$ ， $|S^{(p)}_{ii}|$ 就是对于这个图 $G$ 它的能置换到自己的置换的数目。

那么这个求和，其实就是找到所有的特定的置换与图组成的二元组 $(f, G)$ ，其中 $f\cdot G=G$

那么在计算机中，枚举每个图的代价是巨大的，正如之前算的是 $2^{\frac{n(n-1)}{2}}$ ，但是我们换一种思路，我们可以来枚举所有的置换 $f$ ，找到所有的满足 $f\cdot G=G$ 的图G，设 $S_G\{f\}$ 表示满足的图的集合，这样我们可以得到下面的式子
$t=\frac{\sum_f|S_G\{f\}|}{n!}$
而枚举置换的复杂度就只有 $O (n!)$ 了（其实和之前那个一样都是指数级的，只是那个显然更高阶

5. 计算给定了置换 $f$ 之后有多少个图满足 $f\cdot G=G$

首先我们知道图是通过边集的来定义的

而这里的点集的置换一定对应一个边集的置换

例如

$\{1,2,3,4\} \rightarrow \{2,3,1,4\}$ 的点集置换 $f$ 就可以得到一个相应的边集置换 $f^{'}$ ：

$\{(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)\} \rightarrow \{(2,3), (1,2), (2,4), (1,3), (3,4), (1,4)\}$

那么我们考虑这个点集所对应的满足自己映射到自己的所有的图，其实就是看这个边集置换下的能映射到自己的图：

那么我们就需要找到的图会在拥有了一条边之后，就一定拥有了其映射之后得到的另一条边，以此类推，直至形成环形。

那么我们先选择集合中的一条边 $e_1$ 对其进行边集置换得到 $e_2$ ，再依次进行，直到得到第一个等于之前出现过的边 $e_{k+1}$ 为止，这样我们就得到了 $k$ 条不同的边构成了一个置换的循环。然后继续选择集合中不同于这 $k$ 条边的其它边几次进行这个操作。

首先我们可以证明 $e_{k+1}=e_1$

因为假设 $e_{k+1}=e_i,(i>1)$ ，那么根据 $f'\cdot e_{i-1}=e_i$ ，就有 $f'^{-1}\cdot e_i=e_{i-1}$ ，那么根据 $e_i=e_{k+1}$ 就有 $f'^{-1}*e_{k+1}=e_{i-1}$ 也即 $e_k=e_{i-1}$ 那么违反了 $e_{k+1}$ 是第一个与之前重复的假设。所以 $e_{k+1}$ 一定等于 $e_1$ 。

例如上面这个例子：

我们先选择 $(1, 2)$ 这条边

$\rightarrow (2,3) \rightarrow (1,3) \rightarrow (1,2)}$

再选择 $(1, 4)$ 这条边

$\rightarrow (2,4) \rightarrow (3,4) \rightarrow (1,4)}$

因此我们就得到了两个长度为 $3$ 的循环节

那么在这样一个映射下，这两个循环节里的边要么都选要么都不选，因此我们一共有 $2^2=4$ 种方法

更加通式的情况，对于一个点集映射 $f$ ，我们可以得到它的边集映射 $f^{'}$ ，在 $f^{'}$ 中我们可以通过遍历的方法得到它的循环节个数，设这个个数为 $I (f^{'})$

那么对于点集映射 $f$ 的满足 $f\cdot G=G$ 的 $G$ 的个数就等于 $2^{I(f')}$

6. 最终公式

$t=\frac{\sum_f2^{I(f')}}{n!}$

7. 实现代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
    
const int maxn = 13;

int n;
long long sum = 0;
long long lv[maxn];
int f[maxn];
bool visEdge[maxn][maxn];
bool vis[maxn];

void calculate(){
    int cnt = 0;
    memset(visEdge, 0, sizeof(visEdge));
	for(int i = 1; i <= n; i++){
		for(int j = i+1; j <= n; j++)
        	if(!visEdge[i][j]){
                int ni = i, nj = j;
                do{
                	visEdge[ni][nj] = true;    
                	ni = f[ni], j = f[nj];
                    if(ni > nj) swap(ni, nj);
                }while(visEdge[ni][nj] == false);
        		cnt ++;
            }
    }
    long long s = 1;
    for(int i = 0; i < cnt; i++)
		s <<= 1;
    sum += s;
}

void search(int t){
	if(t == n + 1){
		calculate();
    	return ;
    }
    for(int i = 1; i <= n; i ++)
        if(!vis[i]){
			vis[i] = true;
            f[t] = i;
            search(t + 1);
            vis[i] = false;
        }
}

int main(){
	scanf("%d", &n);
    lv[0] = 1;
    for(int i = 1; i <= n; i++)
        lv[i] = lv[i - 1] * i;
    search(1);
    printf("%lld", sum/lv[n]);
    return 0;
}

/*
时间复杂度：O(n!*n^2) = O(n!)
运行结果：
1: 1
2: 2
3: 4
4: 11
5: 34
6: 156
7: 1044
8: 12346
9: 274668
10: 12005168
*/