📚 How Many Simple Graphs Are There? | 有多少种简单图？
Graph theory is one of the most elegant and rapidly growing fields in discrete mathematics. A question that often sparks curiosity in an IB Mathematics classroom is: given n distinct vertices, just how many different simple graphs can be drawn? The answer reveals not only a beautiful combinatorial formula but also a deep distinction between labeled and unlabeled structures. In this article, we will explore the counting principles behind simple graphs, examine small cases, and uncover why some of these numbers explode so quickly.
图论是离散数学中最优美、发展最快的领域之一。在IB数学课堂上，一个经常引发好奇心的问题是：给定 n 个不同的顶点，究竟能画出多少种不同的简单图？答案不仅揭示了一个优美的组合公式，也展示了标号结构与无标号结构之间的深刻区别。在这篇文章中，我们将探讨简单图背后的计数原理，考察小规模情形，并揭示为什么这些数字会如此迅速地爆炸式增长。
1. What Is a Simple Graph? | 什么是简单图？
A simple graph G = (V, E) consists of a finite set V of vertices and a set E of edges, where each edge is an unordered pair of distinct vertices. No edge connects a vertex to itself (no loops), and there is at most one edge between any two vertices (no multiple edges). This simplicity makes the counting problem both manageable and fundamental.
一个简单图 G = (V, E) 由一个有限顶点集 V 和一个边集 E 组成，其中每条边都是一对不同顶点的无序对。不允许边连接一个顶点到它自身（无自环），且任意两个顶点之间最多只有一条边（无重边）。这种简单性使得计数问题既易于处理又具有基础性。
2. Vertices, Edges, and the Possible Connections | 顶点、边与可能的连接
Suppose we have n labeled vertices v₁, v₂, …, vₙ. For any two distinct vertices, we must decide whether to put an edge between them. The decision for each pair is independent: we either include the edge or we do not. Therefore, the total number of possible simple graphs depends directly on the number of unordered vertex pairs.
假设我们有 n 个标号顶点 v₁, v₂, …, vₙ。对于任意两个不同的顶点，我们必须决定是否在它们之间连一条边。每一对的决定是独立的：我们或者放置这条边，或者不放。因此，可能构成的简单图总数直接取决于无序顶点对的数量。
3. The Number of Possible Edges in a Simple Graph | 简单图中可能的边数
In a graph with n vertices, the number of possible edges is exactly the number of ways to choose 2 vertices from n, which is the binomial coefficient C(n,2) = n(n − 1)/2. This is the maximum number of edges a simple graph on n vertices can have, and it is the total number of independent yes/no decisions we face when building a graph.
在一个有 n 个顶点的图中，可能的边数正是从 n 个顶点中选取2个的组合数，即二项式系数 C(n,2) = n(n − 1)/2。这是 n 个顶点上简单图所能拥有的最大边数，也是我们构建图时面临的总的独立“是/否”决策个数。
4. Counting Labeled Simple Graphs: The Basic Formula | 计数标号简单图：基本公式
Since each of the C(n,2) possible edges can independently be present or absent, the total number of labeled simple graphs on n vertices is exactly 2 raised to the power of the number of possible edges. This gives the fundamental counting formula:
由于每一条可能的边都可以独立地出现或不出现，n 个顶点上标号简单图的总数恰好是 2 的可能边数次方。由此得到基本的计数公式：
Number of labeled simple graphs = 2n(n−1)/2
This result assumes that the vertices have labels (1, 2, …, n), so that swapping vertex labels generally produces a different graph. For example, a graph with an edge between vertex 1 and vertex 2 is considered distinct from a graph with an edge between vertex 2 and vertex 3 when the labels differ.
这一结果假设顶点带有标号（1, 2, …, n），因此交换顶点标号通常会产生一个不同的图。例如，顶点1与顶点2之间有边的图，当标号变化时，与顶点2与顶点3之间有边的图被视为不同的图。
5. Worked Examples: Small Values of n | 示例：小的 n 值
Let us compute the number of labeled simple graphs for the first few values of n. For n = 1, the only vertex has no possible partner, so C(1,2) = 0 and 20 = 1 graph (the empty graph). For n = 2, there is only one possible edge, so 21 = 2 graphs: one without the edge, one with it. For n = 3, C(3,2) = 3 possible edges, giving 23 = 8 graphs. For n = 4, C(4,2) = 6, yielding 26 = 64 graphs. And for n = 5, C(5,2) = 10, producing 210 = 1024 graphs.
让我们计算最初几个 n 值的标号简单图数量。n = 1 时，唯一的顶点没有可配对的伙伴，因此 C(1,2) = 0，得到 20 = 1 个图（空图）。n = 2 时，仅有一条可能的边，因此 21 = 2个图：一个没有边，一个有边。n = 3 时，C(3,2) = 3 条可能的边，给出 23 = 8 个图。n = 4 时，C(4,2) = 6，得到 26 = 64 个图。n = 5 时，C(5,2) = 10，产生 210 = 1024 个图。
6. Visualising the Explosion: a Table of Graph Counts | 可视化增长：图数量表
The sequence grows at an astonishing rate. The table below shows how massive the numbers become even for relatively small vertex sets.
这一数列以惊人的速度增长。下表展示了即使在相对较小的顶点集上，数字也会变得多么庞大。
| n (vertices) | C(n,2) possible edges | Labeled simple graphs |
|---|---|---|
| 1 | 0 | 1 |
| 2 | 1 | 2 |
| 3 | 3 | 8 |
| 4 | 6 | 64 |
| 5 | 10 | 1 024 |
| 6 | 15 | 32 768 |
| 7 | 21 | 2 097 152 |
| 8 | 28 | 268 435 456 |
| 9 | 36 | 68 719 476 736 |
| 10 | 45 | 35 184 372 088 832 |
By the time we reach n = 10, the number of possible labeled simple graphs exceeds 35 trillion. This rapid growth illustrates the combinatorial power of independent choices.
当我们到达 n = 10 时，可能的标号简单图数量已超过 35 万亿。这种急速增长展示了独立选择的组合威力。
7. Understanding Growth Rate: Exponential Growth | 理解增长率：指数增长
The number of labeled simple graphs on n vertices grows like 2(n²)/2 for large n, which is exponential in the square of n. This is much faster than ordinary exponential functions like 2n. It explains why graph enumeration quickly becomes impractical for manual listing, even though the formula itself is extremely simple.
n 个顶点上标号简单图的数量在 n 很大时按 2(n²)/2 的规模增长，这是 n 的平方的指数函数。它比诸如 2n 这样的普通指数函数增长得更快。这就解释了为什么即使用手工列举，图计数也很快变得不切实际，尽管公式本身极其简单。
8. Labeled vs Unlabeled Graphs: Symmetry Matters | 标号图与无标号图：对称性的重要性
In many real-world problems we are not interested in which vertex is called ‘vertex 1’. Two labeled graphs that differ only by a permutation of vertex labels are considered isomorphic — essentially the same unlabeled graph. Counting unlabeled simple graphs, therefore, requires grouping labeled graphs into isomorphism classes.
在许多实际问题中，我们并不关心哪个顶点被称为“顶点1”。仅仅因为顶点标号置换而不同的两个标号图被认为是同构的——本质上是同一个无标号图。因此，计数无标号简单图需要将标号图归入同构类。
For n = 3, the 8 labeled graphs collapse into only 4 unlabeled simple graphs: the empty graph, the graph with one edge, the path of length 2, and the triangle. For n = 4, the 64 labeled graphs reduce to just 11 unlabeled graphs. These numbers are far smaller, but their counting is considerably more difficult.
对于 n = 3，8 个标号图折叠为仅仅 4 个无标号简单图：空图、一条边的图、长度为2的路和三角形。对于 n = 4，64 个标号图减少为只有 11 个无标号图。这些数字要小得多，但它们的计数要困难得多。
9. Why Unlabeled Graphs Are Harder to Count | 为何无标号图更难以计数
Counting unlabeled graphs is not simply a matter of dividing 2n(n−1)/2 by n!, because many graphs possess nontrivial symmetries (automorphisms) that reduce the number of distinct labelings. The correct approach uses Pólya’s enumeration theorem or Burnside’s lemma, taking into account the action of the symmetric group on the set of edges. This leads to a formula involving a sum over partitions of n, and no simple closed form exists.
计数无标号图并不只是简单地将 2n(n−1)/2 除以 n!，因为许多图具有非平凡的对称性（自同构），这减少了不同标号的数量。正确的做法是使用波利亚计数定理或伯恩赛德引理，考虑对称群在边集上的作用。这导致公式中包含对 n 的划分的求和，且不存在简单的封闭形式。
As a consequence, the number of unlabeled simple graphs on n vertices is given by a sequence known to begin 1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, … (for n=0,1,2,…), and it grows roughly like 2n(n−1)/2 / n! for large n, though the precise rate is more delicate.
因此，n 个顶点上的无标号简单图数量由一个已知序列给出，起首为 1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, …（对应 n = 0,1,2,…），并且对于大的 n，大致按 2n(n−1)/2 / n! 的速率增长，尽管精确的增长率更为复杂。
10. Applications of Simple Graph Counting | 简单图计数的应用
Knowing how many simple graphs exist underpins many areas of computer science, chemistry, and network theory. In algorithm analysis, the size of the space of possible input graphs gives a bound on worst-case complexity. In chemistry, counting alkanes and structural isomers is equivalent to counting certain types of graphs. In social network analysis, the enormous number of possible connection patterns reminds us how unique each real-world network truly is.
知道存在多少种简单图为计算机科学、化学和网络理论的许多领域奠定了基础。在算法分析中，可能输入图的空间大小给出了最坏情况复杂度的界限。在化学中，计数烷烃和结构异构体等价于计数某些类型的图。在社交网络分析中，庞大的可能连接模式数量提醒我们每一个真实世界的网络实际上是多么独一无二。
Moreover, the contrast between labeled and unlabeled counting teaches an important lesson: structure that ignores labels is often much richer than it first appears, and symmetry is a powerful tool for reducing complexity.
此外，标号与无标号计数之间的对比教会我们重要的一课：忽略标号的结构往往比最初看上去的丰富得多，而对称性是降低复杂度的一个有力工具。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导