IB Mathematics: Typical Examples of Common Graphs | IB数学：常见图的典型示例

📚 IB Mathematics: Typical Examples of Common Graphs | IB数学：常见图的典型示例

Graph theory is an essential topic in the IB Mathematics AI Higher Level syllabus, where students explore structures composed of vertices and edges. Understanding typical examples of common graphs helps learners recognise patterns, apply theorems, and solve problems involving networks, optimisation and connectivity.

图论是IB数学AI高级课程中的一个核心主题，学生将研究由顶点和边组成的结构。理解常见图的典型示例有助于学习者识别模式、运用定理，并解决涉及网络、优化和连通性的问题。

1. Simple Graph | 简单图

A simple graph is an unweighted, undirected graph containing no loops (edges from a vertex to itself) and no multiple edges between the same pair of vertices. It is the most fundamental type of graph studied at IB level.

简单图是一种无权、无向的图，不包含环（从顶点到自身的边），也不包含同一对顶点之间的多重边。这是IB阶段研究的最基本的图类型。

Example: A graph with vertices V = {A, B, C, D} and edges E = {AB, BC, CD, DA}. Each pair of vertices is connected by at most one edge, and no vertex is joined to itself.
示例：顶点集V = {A, B, C, D}，边集E = {AB, BC, CD, DA}的图。每一对顶点最多由一条边连接，且没有顶点与自身相连。

The degree of a vertex in a simple graph is the number of edges incident to it. For the example above, every vertex has degree 2, since each vertex connects to exactly two neighbours.

在简单图中，顶点的度是与它关联的边的数目。在上述示例中，每个顶点的度都是2，因为每个顶点恰好连接两个邻居。

2. Complete Graph Kₙ | 完全图 Kₙ

A complete graph, denoted Kₙ, is a simple graph in which every pair of distinct vertices is connected by exactly one edge. It has the maximum possible number of edges for a simple graph with n vertices.

完全图记作Kₙ，是一种简单图，其中每一对不同顶点恰好由一条边连接。对于具有n个顶点的简单图，它拥有最大可能的边数。

Number of edges in Kₙ = n(n − 1) / 2

For example, K₅ has 5 × 4 / 2 = 10 edges. Every vertex in Kₙ has degree n − 1, making it a regular graph as well.

例如，K₅有5 × 4 / 2 = 10条边。Kₙ中每个顶点的度都是n − 1，因此它也是一个正则图。

3. Bipartite Graph | 二部图

A bipartite graph is a graph whose vertex set can be partitioned into two disjoint sets U and V such that every edge connects a vertex in U to a vertex in V. No edge exists between two vertices within the same set.

二部图是这样一种图：其顶点集可以划分为两个不相交的集合U和V，使得每条边都连接U中的一个顶点和V中的一个顶点。同一集合内的两个顶点之间不存在边。

Example: Let U = {P, Q} and V = {R, S, T}. Edges include PR, PS, QT. No edges like PQ or RS exist because they lie within the same partition.
示例：设U = {P, Q}，V = {R, S, T}。边包括PR、PS、QT。不存在PQ或RS这样的边，因为它们位于同一分区内。

A bipartite graph can be recognised by the property that it contains no odd-length cycles. This is a useful criterion in IB exam questions involving graph colouring.

二部图可以通过“不含奇数长度环”的性质来识别。这是IB考试中涉及图着色问题时一个有用的判定准则。

4. Complete Bipartite Graph Kₘ,ₙ | 完全二部图 Kₘ,ₙ

A complete bipartite graph Kₘ,ₙ is a bipartite graph in which every vertex in partition U (of size m) is connected to every vertex in partition V (of size n). It contains exactly m × n edges.

完全二部图Kₘ,ₙ是这样一种二部图：分区U（大小为m）中的每个顶点都连接到分区V（大小为n）中的每个顶点。它恰好包含m × n条边。

Edge count of Kₘ,ₙ = m × n

For example, K₂,₃ has 2 × 3 = 6 edges. Vertices in U have degree 3, while vertices in V have degree 2. Complete bipartite graphs often appear in matching and assignment problems.

例如，K₂,₃有2 × 3 = 6条边。U中的顶点度为3，而V中的顶点度为2。完全二部图经常出现在匹配问题和指派问题中。

5. Tree | 树

A tree is a connected graph with no cycles. It is one of the most important structures in graph theory because of its simplicity and wide range of applications, from hierarchical data to network design.

树是一个没有环的连通图。它是图论中最重要的结构之一，因为其简单性以及从层次数据到网络设计等广泛的应用。

For any tree with n vertices: number of edges = n − 1

Example: A tree with 6 vertices has exactly 5 edges. Adding any extra edge would create a cycle, and removing any edge would disconnect the graph.
示例：一个具有6个顶点的树恰好有5条边。添加任何额外边都会产生环，而移除任何边都会使图不连通。

A spanning tree of a connected graph G is a subgraph that is a tree and includes all vertices of G. IB problems often ask students to find a minimum spanning tree (MST) using Kruskal’s or Prim’s algorithm.

连通图G的生成树是G的一个子图，它是一棵树且包含G的所有顶点。IB题目经常要求学生使用Kruskal算法或Prim算法寻找最小生成树（MST）。

6. Regular Graph | 正则图

A regular graph is a graph in which every vertex has the same degree. If every vertex has degree k, the graph is called a k-regular graph. Regular graphs have strong symmetry properties.

正则图是每个顶点都具有相同度数的图。如果每个顶点的度都是k，则称该图为k-正则图。正则图具有很强的对称性。

Example: A 3-regular graph on 6 vertices has each vertex connected to exactly 3 others. The sum of degrees is 6 × 3 = 18, so the number of edges is 18 / 2 = 9.
示例：一个6顶点的3-正则图中，每个顶点恰好连接其他3个顶点。度数之和为6 × 3 = 18，因此边数为18 / 2 = 9。

By the handshaking lemma, the sum of all vertex degrees always equals twice the number of edges. This lemma is frequently tested in IB questions involving regular graphs.

根据握手引理，所有顶点度数之和总是等于边数的两倍。该引理在IB涉及正则图的题目中经常被考查。

7. Path and Cycle Graphs | 路径图与环图

A path graph Pₙ is a simple graph with n vertices arranged in a line, where consecutive vertices are connected. A cycle graph Cₙ is a simple graph with n vertices arranged in a closed loop.

路径图Pₙ是将n个顶点排成一条线、相邻顶点相连的简单图。环图Cₙ是将n个顶点排成一个闭合回路的简单图。

P₄: vertices A − B − C − D, containing 3 edges. The endpoints A and D have degree 1, while B and C have degree 2.
P₄：顶点A − B − C − D，包含3条边。端点A和D的度为1，而B和C的度为2。
C₄: vertices A − B − C − D − A, containing 4 edges. Every vertex has degree 2, making it a 2-regular graph.
C₄：顶点A − B − C − D − A，包含4条边。每个顶点的度为2，使其成为一个2-正则图。

These graphs serve as building blocks for more complex structures and are commonly used to illustrate the concepts of trails, circuits and graph colouring.

这些图是更复杂结构的构建块，常用于说明迹、回路和图着色等概念。

8. Planar Graph | 平面图

A planar graph is a graph that can be drawn in the plane without any edges crossing. The study of planar graphs involves Euler’s formula, which relates vertices, edges and faces.

平面图是可以在平面上绘制的图，且没有任何边相交。平面图的研究涉及欧拉公式，该公式将顶点、边和面联系起来。

Euler’s formula: V − E + F = 2

For a planar graph with V = 6, E = 10 and F = 6, we verify 6 − 10 + 6 = 2. The complete graph K₅ and the complete bipartite graph K₃,₃ are classic examples of non-planar graphs, as they cannot be drawn without crossings.

对于一个平面图，若V = 6，E = 10，F = 6，我们验证6 − 10 + 6 = 2。完全图K₅和完全二部图K₃,₃是不可平面图的经典示例，因为无法在无交叉的情况下绘制它们。

9. Eulerian and Hamiltonian Graphs | 欧拉图与哈密顿图

An Eulerian graph contains a closed trail that uses every edge exactly once; such a trail is called an Euler circuit. A connected graph is Eulerian if and only if every vertex has even degree.

欧拉图包含一条恰好经过每条边一次的闭合迹，这样的迹称为欧拉回路。一个连通图是欧拉图当且仅当每个顶点的度都是偶数。

In contrast, a Hamiltonian graph contains a cycle that visits every vertex exactly once, known as a Hamiltonian cycle. There is no simple necessary and sufficient condition to determine whether a graph is Hamiltonian.

相比之下，哈密顿图包含一个恰好访问每个顶点一次的环，称为哈密顿回路。目前没有简单的充要条件来确定一个图是否为哈密顿图。

Example: C₅ (a 5-cycle) is both Eulerian and Hamiltonian — every vertex has degree 2, and a 5-cycle itself is a Hamiltonian cycle.
示例：C₅（五边形环）既是欧拉图又是哈密顿图——每个顶点的度为2，且五边形环本身就是哈密顿回路。

10. Subgraph and Complement | 子图与补图

A subgraph of a graph G is a graph formed by a subset of vertices from G and a subset of edges among those vertices. The complement of G, denoted Ḡ, has the same vertices as G, but contains exactly the edges that are missing from G.

图G的子图是由G中一部分顶点和这些顶点之间的一部分边构成的图。G的补图记作Ḡ，它与G具有相同的顶点，但恰好包含G中缺失的边。

For a simple graph G with n vertices: edges in G + edges in Ḡ = n(n − 1)/2

If G is a graph with 5 vertices and 7 edges, then its complement Ḡ has 10 − 7 = 3 edges. Understanding complement graphs helps solve problems involving independence and clique structures.

如果G是具有5个顶点和7条边的图，那么其补图Ḡ有10 − 7 = 3条边。理解补图有助于解决涉及独立集和团结构的问题。

11. Isomorphic Graphs | 同构图

Two graphs G₁ and G₂ are isomorphic if there exists a bijection between their vertex sets that preserves adjacency. In simpler terms, two isomorphic graphs have the same structure, even if their vertices are labelled differently.

如果两个图G₁和G₂的顶点集之间存在保持邻接关系的双射，则它们同构。简而言之，两个同构图具有相同的结构，即使它们的顶点标记不同。

Example: Consider a square C₄ and a graph drawn as a diamond. Both have 4 vertices and 4 edges, with every vertex of degree 2 — they are isomorphic.
示例：考虑一个正方形C₄和一个画成菱形的图。两者都有4个顶点和4条边，每个顶点的度都是2——它们同构。

To show two graphs are not isomorphic, compare invariants such as the number of vertices, number of edges, degree sequence and the presence of cycles of certain lengths.

要证明两个图不同构，可以比较不变量，如顶点数、边数、度序列以及是否存在特定长度的环。

12. Applications in Real-World Problems | 实际应用问题

Graph theory extends far beyond pure mathematics. In IB exam contexts, graphs are used to model real-world systems such as transportation networks, social relationships, scheduling problems and electrical circuits.

图论远远超出了纯数学的范畴。在IB考试情境中，图被用来模拟现实世界系统，如交通网络、社交关系、排程问题和电路系统。

Minimum spanning trees are used to design cost-effective fibre-optic networks connecting several cities with minimum total cable length.
最小生成树用于设计连接多个城市且电缆总长度最小的低成本光纤网络。
Euler circuits are applied to route planning, such as a postman delivering mail along every street in a town while minimising repeated travel.
欧拉回路应用于路线规划，例如邮递员沿城镇每条街道投递邮件的同时最小化重复行程。
Bipartite graphs are used in matching problems, such as assigning applicants to jobs where each applicant qualifies for a specific set of positions.
二部图用于匹配问题，例如将申请者分配到符合特定岗位资格的工作中。

When tackling such problems, always begin by identifying the type of graph, then apply the appropriate algorithm: Dijkstra for shortest paths, Kruskal or Prim for minimum spanning trees, and the degree condition for Eulerian trails.

处理此类问题时，始终先识别图的类型，然后应用适当的算法：最短路用Dijkstra算法，最小生成树用Kruskal或Prim算法，欧拉迹则用度数条件判定。

Conclusion | 总结

Mastering the typical examples of common graphs is fundamental to success in the IB Mathematics AI graph theory topics. Each graph family has unique properties, formulas and applications that appear consistently in exam questions.

掌握常见图的典型示例是在IB数学AI图论专题中取得成功的基础。每个图族都有独特的性质、公式和应用，这些在考试题目中反复出现。

By recognising the structural features of complete graphs, trees, bipartite graphs, planar graphs and Eulerian graphs, students can approach advanced problems with confidence and precision.

通过识别完全图、树、二部图、平面图和欧拉图的结构特征，学生可以自信而精准地应对复杂问题。

Published by TutorHao | IB Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

IB Mathematics: Typical Examples of Common Graphs | IB数学：常见图的典型示例