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

这要看你说的图是哪一种。最常见默认是无向简单图，也就是：

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

那么 8 个顶点之间最多有

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

条可能的边。

每条边都有两种选择：存在或不存在。

所以一共有

2^{28}=268435456

个不同的图。

所以答案是：

\boxed{268435456}

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

8\times 7=56

总数是

2^{56}

如果允许自环，还会更多。通常图论里问“8 个顶点一共有多少个图”，默认答案是无向简单图：

\boxed{2^{28}}

如果考虑重合或者同构呢

这个数不是简单除以 (8!)，因为不同图的对称性不同。

比如：

• 空图：怎么重命名 8 个点都还是自己，对称性极强；

• 一条边加 6 个孤立点：只有那条边的两个端点可以互换，孤立点之间可以任意换；

• 一个完全不规则的图：可能几乎没有对称性。

所以不能直接用：

\frac{2^{28}}{8!}

而要用 Burnside 引理 来“按重命名群平均”。

---

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

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

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

个。

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

S_8

作用在这些图上。

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

Burnside 引理说：

[

\text{非同构图数量}

\frac{1}{|S8|}
\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 的整数拆分来分类。

---

4. 具体计算表

下面是 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}

---

5. 举一个小例子理解边轨道

假设置换是：

\pi=(1\ 2)

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

看边：

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

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

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

{1,3}

存在，当且仅当

{2,3}

也存在。

不能只选其中一条。

因此每个边轨道只能整体选择，边轨道越少，被这个置换固定的图越少。

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

2^{22}

个图。

---

6. 总结

如果顶点带编号：

\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 引理就是专门处理这种“不均匀对称性”的。

---

1. 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. 为什么是“平均固定点数量”？

这个结论一开始看起来很神奇。

比如我们要把很多带编号图合并成非同构图。每个非同构图对应一个“轨道”。

一个轨道就是某个图经过所有重命名后得到的一整组图。

比如一个 8 点图 (H)，你把它的顶点重新标号，可能得到很多带编号图。所有这些图组成一个轨道。

Burnside 引理说：

\text{轨道数}=\text{平均固定点数}

也就是说：

[

\boxed{
\text{等价类数量}

\frac{\text{所有操作固定的对象数之和}}{\text{操作数量}}
}
]

---

3. 用一个小例子理解

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

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

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 种。

---

4. 回到图的问题

对于 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) 是一个顶点置换。

---

5. 什么叫一个图被置换固定？

比如有置换：

\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) 对所有可能边产生的轨道数量。

---

6. 一个具体例子：((1\ 2))

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}) 的来源。

---

7. 为什么不能直接除以 (8!)？

因为不是每个图重命名之后都会产生 (8!) 个不同图。

比如空图：

E=\varnothing

不管你怎么重命名顶点，它还是空图。

所以空图的轨道大小是 1，而不是 (8!)。

完全图也一样，怎么重命名都不变。

但一个非常不规则的图，可能几乎每种重命名都会得到不同的带编号图，它的轨道大小接近 (8!)。

所以如果直接算：

\frac{2^{28}}{8!}

就相当于假设每个非同构图都对应 (8!) 个带编号图，这是错的。

Burnside 引理的作用就是把这些对称性自动平均掉。

---

8. 一句话总结

Burnside 引理说：

[

\boxed{
\text{考虑对称后不同对象的数量}

\text{所有对称操作固定对象数量的平均值}
}
]

在图计数里，它变成：

[

\boxed{
\text{非同构图数量}

\frac{1}{n!}
\sum_{\pi\in S_n}
2^{c(\pi)}
}
]

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

对于 (n=8)，这个值最终是：

\boxed{12346}