图个数问题与burnside引理

问题

一个图G（V,E），如果有8个顶点，一共有多少个这样的图？

这个问题涉及到一个有趣的burnside引理，今天我们借这个问题来学习下这个图论引理。

不考虑同构情况

在这种情况下，我们假设每个顶点和边都有id，也就是他们是独一无二的。

如果默认是无向简单图，也就是：

• 顶点已经固定为 8 个；
• 没有自环；
• 两个顶点之间最多一条边；
• 边没有方向。

那么 8 个顶点之间最多有

\binom{8}{2}=\frac{8\times 7}{2}=28

条可能的边。每条边都有两种选择：存在或不存在。所以一共有

2^{28}=268435456

个不同的图。

如果是有向简单图，则每一对不同顶点有两个方向，所以可能边数总数是

2^{56}

如果允许自环，还会更多，但是不是我们今天的主要讨论范围，我们的正题在下面。

如果考虑重合或者同构

此时问题就超过了初中的组合计数。这个数不是简单除以 (8!)，不同图的对称性不同。

对这个情况，我们要用 Burnside 引理 来“按重命名群平均”。

1. 问题本质：把同构图合并

8 个点的无向简单图，如果顶点带编号，有

2^{\binom{8}{2}}=2^{28}

个。

但如果图同构算同一个，就相当于让所有顶点重命名：

S_8

作用在这些图上。我们想数的是这个作用下有多少个等价类，也就是多少个非同构图。

Burnside 引理说：

\text{非同构图数量} = 

\frac{1}{|S_8|}
\sum_{\pi\in S_8}
\text{Fix}(\pi)

其中 \text{Fix}(\pi) 表示：在顶点置换 \pi 下保持不变的图有多少个。

因为：

|S_8|=8!

所以：

\text{答案} = 

\frac{1}{8!}
\sum_{\pi\in S_8}
\text{Fix}(\pi)

---

2. 一个置换固定多少个图？

一个置换 \pi 会把边也进行置换。

例如边 {1,2} 可能被映射成 {3,5}。

如果一个图在 \pi 下不变，那么同一个“边轨道”里的边必须一起出现，或者一起不出现。

所以：

\text{Fix}(\pi)=2^{c(\pi)}

其中 c(\pi) 是置换 \pi 在所有可能边集合上的轨道数量。

因为每个边轨道有两种选择：选或者不选。

所以 Burnside 公式变成：

\text{非同构图数量} =

\frac{1}{8!}
\sum_{\pi\in S_8}
2^{c(\pi)}

关键就是：对 S_8 中不同循环类型的置换，计算它们的边轨道数 c(\pi)。

---

3. 为什么按循环类型算？

在 S_8 里，置换很多，一共有：

8!=40320

个。

但同一种循环结构的置换，对边的作用本质一样，所以 c(\pi) 相同。

例如：

(1\ 2)(3\ 4)

和

(5\ 6)(7\ 8)

本质一样，都是两个 2-cycle 加四个不动点。

所以我们只需要按 8 的整数拆分来分类。

---

具体计算表

下面是 8 个顶点所有置换类型对应的计算结果。

顶点置换循环类型	这种置换有多少个	边轨道数 c(\pi)	固定图数 2^{c(\pi)}
1^8	1	28	2^{28}
2,1^6	28	22	2^{22}
2^2,1^4	210	18	2^{18}
2^3,1^2	420	16	2^{16}
2^4	105	16	2^{16}
3,1^5	112	12	2^{12}
3,2,1^3	1120	10	2^{10}
3,2^2,1	1680	10	2^{10}
3^2,1^2	1120	10	2^{10}
4,1^4	420	10	2^{10}
4,2,1^2	2520	8	2^8
4,2^2	1260	8	2^8
4,3,1	3360	6	2^6
4^2	1260	8	2^8
5,1^3	1344	8	2^8
5,2,1	4032	6	2^6
5,3	2688	4	2^4
6,1^2	3360	6	2^6
6,2	3360	6	2^6
7,1	5760	4	2^4
8	5040	4	2^4

然后代入：

\frac{1}{40320}
\sum
(\text{置换个数})\times 2^{c(\pi)}

结果就是：

\boxed{12346}

---

一个例子理解边轨道

假设置换是：

\pi=(1\ 2)

它交换 1 和 2，其他点不动。

看边：

{1,3}\mapsto {2,3}

所以 {1,3} 和 {2,3} 是同一个边轨道。

如果图在这个置换下不变，那么：

{1,3}

存在，当且仅当

{2,3}

也存在。

由于不能只选其中一条。因此每个边轨道只能整体选择，边轨道越少，被这个置换固定的图越少。

对于 ((1\ 2))，边轨道数是 22，所以它固定：

2^{22}

个图。

---

总结

如果顶点带编号：

\boxed{2^{28}=268435456}

如果同构图算同一个，也就是“考虑重合”：

\boxed{12346}

这个 (12346) 是通过 Burnside 引理算出来的：

\boxed{
\frac{1}{8!}
\sum_{\pi\in S_8}
2^{c(\pi)}

12346
}

其中 c(\pi) 是顶点置换 \pi 对 28 条可能边造成的边轨道数量。

Burnside 引理是一个用来数“考虑对称/重命名后有多少种本质不同对象”的工具。

在你的问题里，它用来数：

8 个点的图，如果只是顶点名字不同但结构一样，就算同一个，那么一共有多少种？

这种问题不能直接除以 (8!)，因为有些图自己的对称性很多，有些图几乎没有对称性。Burnside 引理就是专门处理这种“不均匀对称性”的。

---

Burnside 引理在说什么

设有一个集合 (X)，里面是所有“带编号”的对象。

例如：

X={\text{所有 8 个带编号顶点的无向简单图}}

然后有一个群 (G) 作用在 (X) 上。

在图的问题里，G=S_8，也就是所有 8 个顶点的重命名方式。

Burnside 引理说：

\boxed{
\text{本质不同的对象数量}

\frac{1}{|G|}
\sum_{g\in G} |\mathrm{Fix}(g)|
}

其中：

\mathrm{Fix}(g)={x\in X: g\cdot x=x}

意思是：被操作 (g) 之后仍然不变的对象数量。

所以 Burnside 引理可以理解为：

本质不同的结构数量 = 所有对称操作下“不变对象数量”的平均值。

---

用一个小例子理解

假设我们有两个珠子位置，每个位置可以涂黑或白。

如果区分左右位置，一共有：

2^2=4

种：

WW,\ WB,\ BW,\ BB  

现在如果左右翻转后相同就算同一种，那么 (WB) 和 (BW) 算同一个。

所以本质不同的有：

WW,\ BB,\ WB/BW  

共 3 种。

我们用 Burnside 引理算一下。

这里的对称群 (G) 有两个元素：

1. 不动操作 (e)

2. 左右交换操作 (s)

对于不动操作 (e)，所有 4 种都不变：

|\mathrm{Fix}(e)|=4

对于左右交换 (s)：

WW \to WW

BB \to BB

WB \to BW

BW \to WB

所以只有 (WW,BB) 不变：

|\mathrm{Fix}(s)|=2

Burnside 引理给出：

\frac{4+2}{2}=3

正好是本质不同的 3 种。

---

回到图的问题

对于 8 个顶点的图：

X={\text{所有带编号的 8 点图}}

带编号时共有：

2^{\binom{8}{2}}=2^{28}

个。

重命名群是：

G=S_8

有：

8!=40320

种顶点重命名方式。

Burnside 引理说：

\text{非同构 8 点图数量}

\frac{1}{8!}
\sum_{\pi\in S_8}
|\mathrm{Fix}(\pi)|

这里 \pi 是一个顶点置换。

---

一个图被置换固定的含义

比如有置换：

\pi=(1\ 2)

它交换顶点 1 和 2。

如果一个图在交换 1 和 2 后完全不变，那么它就被 \pi 固定。

例如边：

{1,3}

会被映射成：

{2,3}

所以如果图要在 ((1 2)) 下不变，那么它必须满足：

{1,3}\text{存在}
\iff
{2,3}\text{存在}

也就是说，这两条边必须一起出现，或者一起不出现。

类似地，所有边会被顶点置换分成若干个“边轨道”。

每个边轨道只能整体选或不选。

所以：

|\mathrm{Fix}(\pi)|=2^{c(\pi)}

其中 c(\pi) 是 \pi 对所有可能边产生的轨道数量。

比如8 个点里所有可能边有 28 条。

置换 ((1 2)) 会让一些边互相对应：

{1,3}\leftrightarrow {2,3}

{1,4}\leftrightarrow {2,4}

一直到：

{1,8}\leftrightarrow {2,8}

这些成对绑定，一共有 6 对。

边：

{1,2}

交换后还是自己。

其他不涉及 1 和 2 的边，比如：

{3,4},{3,5},\dots

也都不变。

所以边轨道数量是：

1 + 6 + \binom{6}{2}

= 1+6+15

= 22

因此被 ((1 2)) 固定的图有：

2^{22}

个。

这就是前面表格里 (2,1^6) 类型对应 2^{22} 的来源。