简单图

简单图，也称为严格图（Tutte 1998，第 2 页），是一个无权、无向的图，不包含图环或重边（Gibbons 1985，第 2 页；West 2000，第 2 页；Bronshtein 和 Semendyayev 2004，第 346 页）。简单图可以是连通的或非连通的。

除非另有说明，否则未限定的术语“图”通常指简单图。具有重边的简单图有时称为多重图（Skiena 1990，第 89 页）。

n 个节点上的非同构简单图的数量可以由下式给出NumberOfGraphs[n] 在 Wolfram 语言 包中Combinatorica`，并且 n=1, 2, ... 的值是 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, ... (OEIS A000088；参见上图)。King 和 Palmer（在 Read 1981 中引用）已计算出高达 n=24 的 ，其中

(1)

对于 n 条边的简单图，似乎没有标准术语，尽管“polynema”（Kyrmse）和“polyedge”（Muñiz 2011）这两个词已被提议用于 -边连通图。

可以使用以下命令枚举 n 个节点上的所有简单图ListGraphs[n] 在 Wolfram 语言 包中Combinatorica`，并且可以通过以下方式获得最多 n=7 个顶点的预计算列表GraphData[n]。可以使用程序进行更有效的枚举geng（一部分nauty），由 B. McKay 开发。然而，由于程序返回图的顺序geng随着改进的进行，会随时间变化，因此此处和以下位置使用了 McKay 网站上给出的规范排序GraphData.

可以在 Wolfram 语言 中测试图是否为简单图，使用SimpleGraphQ[g]。

一个多项式

(2)

它枚举了具有 个节点的不同图的数量（其中 是具有 条边的 个节点上的图的数量），可以使用 Pólya 枚举定理的相当复杂的应用找到。此过程给出的计数多项式为

(3)

其中 是作用于 的 2-子集的对群，由下式给出

(4)

（Harary 1994，第 185 页）。这里， 是向下取整函数， 是二项式系数，LCM 是最小公倍数，GCD 是最大公约数，和 遍布对称群 的循环指标 的所有指数向量，并且 是 中具有指数向量 的项的系数。前几个循环指标 是

			(5)
			(6)
			(7)
			(8)
			(9)

这些可以通过以下命令给出PairGroup[SymmetricGroup[n]], x] 在 Wolfram 语言 包中Combinatorica`。通过 归一化并令 ，然后得到 ，其中前几个是

			(10)
			(11)
			(12)
			(13)
			(14)

这些多项式实现为GraphPolynomial[n, x] 在 Wolfram 语言 包中Combinatorica` .

将 代入其中任何一个都会得到 n 个节点上的简单图的总数。可以使用以下命令枚举具有 条边的 个节点上的所有简单图ListGraphs[n, k] 在 Wolfram 语言 包中Combinatorica`。n 个节点和 条边的非同构简单图的数量可以由下式给出NumberOfGraphs[n, k] 在 Wolfram 语言 包中Combinatorica`，具有 个节点和 条边的图 的数量数组如下所示 (OEIS A008406)。

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	1
2	1	1
3	1	1	1	1
4	1	1	2	3	2	1	1
5	1	1	2	4	6	6	6	4	2	1	1
6	1	1	2	5	9	15	21	24	24	21	15	9	5	2	1	1

具有 个顶点的图的平均边数由 给出，对于 n=1, 2, ... 的序列为 0, 1/2, 3/2, 3, 5, 15/2, 21/2, 14, 18, ... (OEIS A064038 和 A014695)。这意味着阶数为 , 2, ... 的不同图中的边总数是 0, 1, 6, 33, 170, 1170, 10962, 172844, 4944024, 270116280, ... (OEIS A086314)。

上图显示了各种常见简单图类别的前几个成员：反棱柱图、完全图、圈图、空图、齿轮图、棱柱图、星图和轮图。