📚 Counting Simple Graphs in IB Mathematics | IB数学：简单图的计数方法
In IB Mathematics, particularly in the Discrete Mathematics option, counting simple graphs involves determining the number of possible graphs under given constraints. This article explores structured methods for enumerating simple labelled and unlabelled graphs, applying degree sequence criteria, and using combinatorial tools such as the handshake lemma and Cayley’s formula.
在IB数学中，特别是离散数学选修部分，简单图的计数涉及在给定约束下确定可能图的数量。本文将探讨系统化方法，用于枚举有标号和无标号的简单图，应用度数序列判定准则，并利用握手引理和凯莱公式等组合工具。
1. What is a Simple Graph? | 什么是简单图？
A simple graph is an undirected graph with no loops and no multiple edges between the same pair of vertices. Each edge is uniquely determined by an unordered pair of distinct vertices.
简单图是无向图，不存在自环（环），也不存在同一对顶点之间的多重边。每条边由一对不同的无序顶点唯一确定。
Counting simple graphs often begins with fixing a set of \(n\) labelled vertices, say \(V = \{v_1, v_2, \ldots, v_n\}\). The number of possible edges is the number of 2-element subsets of \(V\), denoted \(\binom{n}{2}\).
计数简单图通常从固定一个有标号的顶点集 \(V = \{v_1, v_2, \ldots, v_n\}\) 开始。可能的边数是 \(V\) 的二元子集个数，记为 \(\binom{n}{2}\)。
Number of possible edges = C(n, 2) = n(n−1)/2
可能的边数 = C(n, 2) = n(n−1)/2
2. Counting Labelled Simple Graphs | 有标号简单图的计数
If vertices are distinguishable (labelled \(v_1, v_2, \ldots, v_n\)), each possible edge can be either present or absent independently. Therefore, the total number of labelled simple graphs on \(n\) vertices is:
如果顶点是可区分的（标记为 \(v_1, v_2, \ldots, v_n\)），每条可能的边可以独立地选择存在或不存在。因此，\(n\) 个顶点上有标号简单图的总数为：
Total labelled simple graphs = 2C(n,2)
有标号简单图总数 = 2C(n,2)
For \(n=3\), \(C(3,2)=3\), so there are \(2^3=8\) labelled simple graphs. For \(n=4\), there are \(2^6=64\) graphs; for \(n=5\), \(2^{10}=1024\).
例如 \(n=3\) 时，\(C(3,2)=3\)，所以有 \(2^3=8\) 个有标号简单图；\(n=4\) 时有 \(2^6=64\) 个；\(n=5\) 时有 \(2^{10}=1024\) 个。
3. Counting Edges in a Given Graph | 给定图中边数的计数
The handshake lemma states that the sum of all vertex degrees equals twice the number of edges. For a simple graph with degree sequence \(d_1, d_2, \ldots, d_n\):
握手引理指出：所有顶点度数之和等于边数的两倍。对于度序列为 \(d_1, d_2, \ldots, d_n\) 的简单图有：
Σ dᵢ = 2E
This lemma is essential when counting graphs with prescribed degrees, since the edge count must satisfy integrality and the handshake condition.
该引理在计数具有指定度数的图时至关重要，因为边数必须满足整数性和握手条件。
4. Degree Sequences and Graphicality | 度数序列与可图化
A sequence of non-negative integers \((d_1, d_2, \ldots, d_n)\) is called graphical if it is the degree sequence of some simple graph. Not every sequence with even sum is graphical.
非负整数序列 \((d_1, d_2, \ldots, d_n)\) 如果能够成为某个简单图的度数序列，则称其为可图化的。并非所有和为偶数的序列都可图化。
The Havel-Hakimi algorithm provides a constructive test: repeatedly sort the sequence in non-increasing order, remove the largest degree \(d\), subtract 1 from the next \(d\) degrees, and remove zeros. If all remaining degrees become zero, the sequence is graphical; if any negative value appears or not enough elements remain, it is not.
Havel-Hakimi 算法提供了一种构造性检验：反复将序列按非递增顺序排序，移除最大度数 \(d\)，将其后 \(d\) 个度数分别减 1，并移除零。若所有剩余度数都变为零，则序列可图化；若出现负值或剩余元素不足，则不可图化。
For example, sequence \((3, 3, 2, 2, 2)\) has sum 12, even, and is graphical. A simple graph with this sequence is a 5-vertex graph consisting of a 4-cycle plus an extra vertex connected to two opposite vertices? Let us check via the algorithm.
例如，序列 \((3, 3, 2, 2, 2)\) 之和为 12，是偶数，且可图化。实际上可以构造一个 5 顶点图满足该度序列。
5. Counting Graphs with a Given Degree Sequence | 给定度序列的图计数
Determining the exact number of labelled graphs with a prescribed degree sequence is nontrivial. In IB context, we often count graphs for small \(n\) by case analysis or by using the degree sequence to draw all non-isomorphic possibilities.
确定具有指定度序列的有标号图的确切数量并非易事。在IB范围内，我们通常通过分类讨论或利用度数序列绘制所有非同构可能来计数小规模图。
For example, on 4 vertices, the degree sequence \((2,2,2,2)\) corresponds to a 4-cycle. There are 3 labelled cycles on 4 vertices? Actually the number of distinct labelled cycles is 3 (since rotations/reflections are not identified when vertices are labelled). This is a common counting exercise.
例如，在 4 个顶点上，度序列 \((2,2,2,2)\) 对应一个 4 环。4 个顶点上不同的有标号环有 3 个（因为顶点有标号时旋转和反射不视为同一图）。这是一个常见的计数练习。
6. Unlabelled Simple Graphs and Isomorphism | 无标号简单图与同构
Two graphs are isomorphic if there exists a bijection between their vertex sets that preserves adjacency. Counting unlabelled simple graphs means counting isomorphism classes, not individual labelled graphs.
如果两个图的顶点集之间存在保持邻接关系的双射，则它们同构。计数无标号简单图就是计数同构类，而不是单独的标记图。
For \(n=3\), there are 4 unlabelled simple graphs: empty graph, one edge, two edges (path), and triangle. For \(n=4\), there are 11 unlabelled graphs. For \(n=5\), there are 34.
对于 \(n=3\)，有 4 个无标号简单图：空图、一条边、两条边（路径）、三角形。对于 \(n=4\)，有 11 个无标号图；对于 \(n=5\)，有 34 个。
These numbers grow extremely fast: the sequence of unlabelled simple graphs begins 1, 2, 4, 11, 34, 156, 1044, … for \(n=1,2,3,4,5,6,7\).
这些数字增长极快：无标号简单图的数列前几项为 \(n=1,2,3,4,5,6,7\) 时分别是 1, 2, 4, 11, 34, 156, 1044, …。
7. Counting Trees: Cayley’s Formula | 树的计数：凯莱公式
A tree is a connected acyclic simple graph. For labelled vertices, the number of distinct trees on \(n\) vertices is given by Cayley’s formula:
树是连通且无环的简单图。对于有标号顶点，\(n\) 个顶点上不同树的数量由凯莱公式给出：
Number of labelled trees = nn−2
For \(n=4\), there are \(4^{2}=16\) labelled trees. For \(n=5\), \(5^{3}=125\). This formula is a classic result in enumerative combinatorics.
例如 \(n=4\) 时有 \(4^{2}=16\) 棵有标号树；\(n=5\) 时有 \(5^{3}=125\) 棵。该公式是计数组合学中的经典结果。
8. Counting Spanning Trees | 生成树的计数
Given a specific labelled graph \(G\), the number of its spanning trees can be counted using the Matrix-Tree Theorem. For a graph with Laplacian matrix \(L\) (where \(L_{ii}=\deg(v_i)\) and \(L_{ij}=-1\) if \(ij\) is an edge, diagonal otherwise), the number of spanning trees is any cofactor of \(L\).
给定一个特定的有标号图 \(G\)，其生成树数量可用矩阵树定理计算。设拉普拉斯矩阵 \(L\) 满足 \(L_{ii}=\deg(v_i)\)，若 \(ij\) 是边则 \(L_{ij}=-1\)，否则为 0，则 \(L\) 的任意余子式即为生成树数量。
For the complete graph \(K_n\), the matrix-tree theorem yields \(n^{n-2}\), consistent with Cayley’s formula. For example, \(K_4\) has \(4^{2}=16\) spanning trees.
对于完全图 \(K_n\)，矩阵树定理给出 \(n^{n-2}\)，与凯莱公式一致。例如 \(K_4\) 有 \(4^{2}=16\) 棵生成树。
9. Counting Connected Simple Graphs | 连通简单图的计数
Counting connected labelled graphs on \(n\) vertices is more complex. Let \(c_n\) be the number of connected labelled simple graphs. The total number of labelled graphs \(g_n = 2^{C(n,2)}\) can be decomposed via exponential generating functions, leading to the recurrence:
计数连通有标号简单图更为复杂。设 \(c_n\) 表示连通有标号简单图的数量。有标号图总数 \(g_n = 2^{C(n,2)}\) 可通过指数生成函数分解，得到递推关系：
gₙ = Σₖ₌₁ⁿ C(n−1, k−1) · cₖ · gₙ₋ₖ
Here \(g_n = 2^{n(n−1)/2}\), and \(g_0=1\). Solving gives \(c_4=38\), \(c_5=728\), \(c_6=26704\).
其中 \(g_n = 2^{n(n−1)/2}\)，且 \(g_0=1\)。求解可得 \(c_4=38\)，\(c_5=728\)，\(c_6=26704\)。
10. Using Burnside’s Lemma for Unlabelled Graphs | 用伯恩赛德引理计数无标号图
To count unlabelled simple graphs on \(n\) vertices, one can use Burnside’s Lemma, averaging the number of graphs fixed by each permutation of the \(n\) vertices over the symmetric group \(S_n\).
为了计数 \(n\) 个顶点上的无标号简单图，可以使用伯恩赛德引理，在对称群 \(S_n\) 上对每个顶点置换所固定的图数求平均。
For a permutation \(\sigma\), a graph is fixed by \(\sigma\) if every edge orbit is either entirely present or entirely absent. The number of orbits of edges under \(\sigma\) can be computed from the cycle type of \(\sigma\). Burnside’s Lemma gives:
对于置换 \(\sigma\)，若每条边轨道要么全部存在要么全部不存在，则该图在 \(\sigma\) 下不变。\(\sigma\) 的边轨道数可由其轮换类型计算。伯恩赛德引理给出：
Unlabelled graphs = (1/n!) Σσ∈Sₙ 2e(σ)
where \(e(\sigma)\) is the number of edge orbits induced by \(\sigma\). This method is powerful but requires careful orbit counting; for \(n=4\) it reproduces 11.
其中 \(e(\sigma)\) 是 \(\sigma\) 诱导的边轨道数。该方法功能强大但需要仔细计数轨道；对于 \(n=4\) 可以重现 11。
11. Bipartite and Complete Graphs | 二分图与完全图
A simple graph is bipartite if its vertex set can be partitioned into two independent sets \(A\) and \(B\). Counting bipartite labelled graphs on a fixed partition \((a,b)\) is easy: there are \(a·b\) possible cross edges, so \(2^{ab}\) labelled bipartite graphs with that partition.
简单图是二分图，如果其顶点集可以划分为两个独立集 \(A\) 和 \(B\)。对于固定的划分 \((a,b)\)，计数有标号二分图很简单：交叉边共有 \(a·b\) 条，因此该划分下有 \(2^{ab}\) 个有标号二分图。
The complete graph \(K_n\) has \(C(n,2)\) edges, and thus exactly one graph for each \(n\) up to isomorphism. The complement of a simple graph is obtained by toggling edges; counting complements can simplify problems since the number of graphs equals the number of complements.
完全图 \(K_n\) 有 \(C(n,2)\) 条边，因此在同构意义下每个 \(n\) 只有一个完全图。简单图的补图通过切换边得到；计数补图有时能简化问题，因为图的数量等于补图的数量。
12. Practical Counting Strategies for IB Exam | IB考试中的实用计数策略
When solving counting problems in IB exams, first determine whether vertices are labelled or unlabelled. If labelled, use independent edge choices or formulas like Cayley’s formula. If unlabelled, draw non-isomorphic cases systematically by edge count \(m\), from 0 to \(C(n,2)\).
在IB考试中解决计数问题时，首先要判断顶点是有标号还是无标号。若为有标号，使用独立边选择或凯莱公式等；若为无标号，则按边数 \(m\) 从 0 到 \(C(n,2)\) 系统地绘制非同构图。
Always verify the handshake lemma and the maximum degree \(n-1\) for each degree sequence. Use Havel-Hakimi to test graphicality quickly. For spans of small \(n\), memorizing the small values (4, 11, 34) can save time.
始终验证握手引理以及每个度数序列的最大度不超过 \(n-1\)。使用Havel-Hakimi快速检验可图化。对于小的 \(n\)，记住小数值（4、11、34）可以节省时间。
Finally, practice with structured examples: count all labelled graphs with 0,1,2 edges on 4 vertices; then use complement symmetry to double-check results.
最后，通过结构化例子练习：计数 4 个顶点上具有 0、1、2 条边的所有有标号图；然后利用补图对称性检查结果。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply