IB Mathematics: Definitions and Basic Properties of Graphs | IB数学：图的定义与基本性质

📚 IB Mathematics: Definitions and Basic Properties of Graphs | IB数学：图的定义与基本性质

Graph theory is a cornerstone of discrete mathematics and a key topic in the IB Mathematics Analysis and Approaches or Applications and Interpretation Higher Level option on discrete mathematics. It studies the relationships between objects, modeled as vertices and edges. This article introduces the fundamental definitions and basic properties you need for exam success.

图论是离散数学的基石，也是IB数学分析与方法或应用与解释高级水平中离散数学选项的重要主题。它通过顶点和边来研究对象之间的关系。本文系统介绍图的基本定义与性质，帮助你在考试中取得好成绩。

1. What is a Graph? | 什么是图？

A graph \(G\) is an ordered pair \(G = (V, E)\), where \(V\) is a non-empty set of elements called vertices (or nodes), and \(E\) is a set of unordered pairs of distinct vertices called edges. In a simple graph, each edge joins exactly two distinct vertices, and there is at most one edge between any two vertices.

图 \(G\) 是一个有序对 \(G = (V, E)\)，其中 \(V\) 是由称为顶点（或结点）的元素构成的非空集合，\(E\) 是由不同顶点的无序对构成的集合，这些无序对称为边。在简单图中，每条边恰好连接两个不同顶点，且任意两个顶点之间至多有一条边。

The order of a graph is \(|V|\), the number of vertices; the size is \(|E|\), the number of edges. We often write \(n = |V|\) and \(m = |E|\).

图的阶是 \(|V|\)，即顶点数；图的大小是 \(|E|\)，即边数。通常记作 \(n = |V|\)，\(m = |E|\)。

2. Vertices and Edges | 顶点与边

If an edge connects vertices \(u\) and \(v\), we write \(e = uv\) or \(e = \{u, v\}\). We say \(u\) and \(v\) are adjacent and that the edge \(e\) is incident to both \(u\) and \(v\). The two endpoints of an edge are called its endpoints.

如果一条边连接顶点 \(u\) 和 \(v\)，我们写作 \(e = uv\) 或 \(e = \{u, v\}\)。称 \(u\) 与 \(v\) 是相邻的，并称边 \(e\) 与 \(u\)、\(v\) 都关联。一条边的两个端点是它的端点。

In some graphs, called multigraphs, multiple edges may join the same pair of vertices. A loop is an edge whose endpoints are the same vertex. A graph with no loops and no multiple edges is a simple graph. In IB problems, unless stated otherwise, “graph” usually means a simple finite graph.

在某些图中，称为多重图，同一对顶点之间可能有多条边。环是连接同一顶点的边。没有环且没有多重边的图称为简单图。在IB习题中，除非特别说明，“图”通常指有限简单图。

Term 术语	Meaning 含义
V(G)	Set of vertices 顶点集合
E(G)	Set of edges 边集合
adjacent 相邻	Joined by an edge 被一条边连接
incident 关联	An edge meets a vertex 边与顶点相连

3. Degree of a Vertex | 顶点的度

The degree of a vertex \(v\), written \(\deg(v)\) or \(d(v)\), is the number of edges incident with \(v\). In a simple graph, this equals the number of neighbours of \(v\). A loop contributes 2 to the degree of a vertex.

顶点 \(v\) 的度，记作 \(\deg(v)\) 或 \(d(v)\)，是与 \(v\) 关联的边数。在简单图中，它等于 \(v\) 的邻居数。一个环对顶点度的贡献为2。

A vertex is even if its degree is even, and odd if its degree is odd. The minimum degree of a graph is denoted \(\delta(G)\), and the maximum degree is denoted \(\Delta(G)\).

度为偶数的顶点称为偶顶点，度为奇数的顶点称为奇顶点。图的最小度记为 \(\delta(G)\)，最大度记为 \(\Delta(G)\)。

For example, in a triangle with vertices \(A, B, C\) and edges \(AB, BC, CA\), we have \(\deg(A) = \deg(B) = \deg(C) = 2\).

例如，在顶点为 \(A, B, C\)、边为 \(AB, BC, CA\) 的三角形中，\(\deg(A) = \deg(B) = \deg(C) = 2\)。

4. The Handshaking Lemma | 握手引理

The handshaking lemma states that in any finite graph, the sum of the degrees of all vertices equals twice the number of edges:

握手引理指出：在任何有限图中，所有顶点度数之和等于边数的两倍：

∑_v∈V deg(v) = 2|E|

This result follows because each edge contributes exactly 2 to the total sum: one to each of its two endpoints. A direct consequence is that the number of odd-degree vertices in any graph is even.

这个结果源于每条边恰好为总和贡献2：分别给它的两个端点各贡献1。直接推论是：任何图中奇度顶点的个数是偶数。

Example: A graph has 6 vertices with degrees 3, 3, 2, 2, 1, 1. The sum is \(3+3+2+2+1+1 = 12\), so \(|E| = 12/2 = 6\). Because there are four odd vertices, this is a valid degree sequence.

例：某图有6个顶点，度数分别为3, 3, 2, 2, 1, 1。其和为 \(3+3+2+2+1+1 = 12\)，所以 \(|E| = 12/2 = 6\)。由于有四个奇顶点，这是一个合法的度序列。

5. Types of Simple Graphs | 简单图的类型

Several basic families of graphs appear frequently in IB examinations.

几类基本图族在IB考试中经常出现。

Empty graph: a graph with no edges; if it has \(n\) vertices, it is often written as \(\overline{K_n}\).

空图：没有边的图；若有 \(n\) 个顶点，常记为 \(\overline{K_n}\)。
Complete graph \(K_n\): every pair of distinct vertices is connected by an edge. It has \(\binom{n}{2} = \frac{n(n-1)}{2}\) edges.

完全图 \(K_n\)：任意两个不同顶点之间都有一条边。它有 \(\binom{n}{2} = \frac{n(n-1)}{2}\) 条边。
Path graph \(P_n\): a sequence of \(n\) vertices connected by \(n-1\) edges in a line.

路径图 \(P_n\)： \(n\) 个顶点由 \(n-1\) 条边连成一条线。
Cycle graph \(C_n\): a graph with \(n \ge 3\) vertices arranged in a closed loop, each vertex of degree 2.

回路图 \(C_n\)： \(n \ge 3\) 个顶点排成一个闭合环，每个顶点度为2。
Star graph \(S_k\): one central vertex connected to \(k\) leaves; it is actually a complete bipartite graph \(K_{1,k}\).

星形图 \(S_k\)：一个中心顶点连接 \(k\) 个叶子；它实际上是完全二部图 \(K_{1,k}\)。

6. Complete Graphs, Bipartite Graphs and Complements | 完全图、二部图与补图

A complete bipartite graph \(K_{m,n}\) has its vertices split into two disjoint sets of sizes \(m\) and \(n\), with all possible edges between the sets, but no edges within each set. It has \(mn\) edges.

完全二部图 \(K_{m,n}\) 将顶点分成大小分别为 \(m\) 和 \(n\) 的两个不相交集合，两个集合之间所有可能的边都存在，但每个集合内部没有边。它有 \(mn\) 条边。

The complement of a simple graph \(G\), written \(\overline{G}\), has the same vertex set as \(G\). In \(\overline{G}\), two vertices are adjacent exactly when they are not adjacent in \(G\). The union of \(G\) and \(\overline{G}\) on the same vertex set forms a complete graph \(K_n\).

简单图 \(G\) 的补图，记作 \(\overline{G}\)，与 \(G\) 有相同的顶点集。在 \(\overline{G}\) 中，两个顶点相邻当且仅当它们在 \(G\) 中不相邻。在同一个顶点集上，\(G\) 与 \(\overline{G}\) 的并构成完全图 \(K_n\)。

Example: The complement of a cycle \(C_5\) is another cycle \(C_5\). The complement of a path \(P_4\) is a path \(P_4\) with the middle edge removed, i.e. a graph with edges between first-second, second-fourth? Let us check: \(P_4\) has edges \(12,23,34\); the complement has edges \(13,14,24\), which is actually a path \(1-3-2-4\).

例：五边形 \(C_5\) 的补图仍然是 \(C_5\)。路径 \(P_4\) 的补图：\(P_4\) 的边为 \(12,23,34\)；补图的边为 \(13,14,24\)，即路径 \(1-3-2-4\)。

7. Paths, Trails and Cycles | 通路、迹与回路

A walk in a graph is a sequence of vertices where each consecutive pair is joined by an edge. A trail is a walk with no repeated edges. A path is a trail with no repeated vertices. A cycle is a path with at least three vertices that starts and ends at the same vertex, with no other vertex repeated.

行走是图中的一个顶点序列，其中每两个连续顶点都由一条边连接。迹是没有重复边的行走。通路是没有重复顶点的迹。回路是至少三个顶点组成的通路，起点和终点相同，且没有其他顶点重复。

The length of a walk, trail, or path is the number of edges it contains. In a simple graph, the shortest path between two vertices is called a geodesic; its length is the distance between the vertices.

行走、迹或通路的长度是其中包含的边数。在简单图中，两个顶点之间的最短路径称为最短测地线；其长度就是这两个顶点之间的距离。

For example, in the graph \(A-B-C-D\), the sequence \(A-B-C\) is a path of length 2, while \(A-B-C-B\) is a walk that is not a trail because edge \(BC\) is used twice.

例如，在图 \(A-B-C-D\) 中，序列 \(A-B-C\) 是长度为2的通路，而 \(A-B-C-B\) 是行走但不是迹，因为边 \(BC\) 被使用了两次。

8. Connectivity | 连通性

A graph is connected if there is a path between any two of its vertices. If not, the graph is disconnected, and its maximal connected subgraphs are called connected components.

如果图中任意两个顶点之间都存在通路，则称该图是连通的；否则称其为不连通的，其极大连通子图称为连通分量。

A bridge (or cut edge) is an edge whose removal increases the number of connected components. Identifying bridges is important in network design and appears in IB discrete mathematics questions.

桥（或割边）是指删除后会使连通分量数量增加的边。识别桥在网络设计中非常重要，并且在IB离散数学题中经常出现。

The diameter of a graph is the maximum distance between any two vertices. For a connected graph with \(n\) vertices, the diameter is at most \(n-1\).

图的直径是任意两个顶点之间距离的最大值。对于有 \(n\) 个顶点的连通图，直径至多为 \(n-1\)。

Example: The graph \(A-B-C\) is connected. Adding an isolated vertex \(D\) gives two components: \(\{A,B,C\}\) and \(\{D\}\). The edge \(A-B\) is a bridge in the path \(A-B-C\).

例：图 \(A-B-C\) 是连通的。加入一个孤立顶点 \(D\) 后得到两个分量：\(\{A,B,C\}\) 和 \(\{D\}\)。在路径 \(A-B-C\) 中，边 \(A-B\) 是桥。

9. Trees and Forests | 树与森林

A tree is a connected graph with no cycles. A graph with no cycles but possibly disconnected is called a forest; each connected component is a tree.

树是没有回路的连通图。没有回路但可能不连通的图称为森林；其每个连通分量都是一棵树。

Important properties of a tree with \(n\) vertices:

具有 \(n\) 个顶点的树的重要性质：

It has exactly \(n-1\) edges.

它恰好有 \(n-1\) 条边。
There is exactly one path between any two vertices.

任意两个顶点之间有且仅有一条通路。
Adding any new edge between two non-adjacent vertices creates exactly one cycle.

在任意两个不相邻顶点之间添加一条新边，会恰好产生一个回路。
A tree with \(n \ge 2\) always has at least two vertices of degree 1, called leaves.

当 \(n \ge 2\) 时，树至少有两个度为1的顶点，称为叶子。

These properties are often used as equivalent characterisations in IB exam questions. If a connected graph with \(n\) vertices has \(n-1\) edges, then it is automatically a tree.

这些性质在IB考题中常被用作等价刻画。如果一个具有 \(n\) 个顶点的连通图有 \(n-1\) 条边，那么它自动就是树。

10. Graph Isomorphism | 图的同构

Two graphs \(G\) and \(H\) are isomorphic if there exists a bijection \(f: V(G) \to V(H)\) such that two vertices \(u,v\) are adjacent in \(G\) exactly when \(f(u), f(v)\) are adjacent in \(H\). The bijection is called an isomorphism.

如果存在一个双射 \(f: V(G) \to V(H)\)，使得 \(G\) 中相邻的顶点 \(u,v\) 当且仅当 \(f(u), f(v)\) 在 \(H\) 中相邻，则称两个图 \(G\) 和 \(H\) 同构。该双射称为同构映射。

Isomorphic graphs have the same number of vertices, the same number of edges, and the same degree sequence, but the converse is not always true: two graphs with the same degree sequence need not be isomorphic.

同构的图具有相同的顶点数、相同的边数和相同的度序列，但反之不一定成立：具有相同度序列的两个图未必同构。

Example: The path \(P_4\) (edges \(12,23,34\)) and the graph with edges \(13,32,24\) are isomorphic because we can relabel the vertices by the mapping \(f(1)=1, f(2)=3, f(3)=2, f(4)=4\). Both are paths of length 3.

例：路径 \(P_4\)（边为 \(12,23,34\)）与边为 \(13,32,24\) 的图同构，因为通过映射 \(f(1)=1, f(2)=3, f(3)=2, f(4)=4\) 可以重新标记顶点。两者都是长度为3的路径。

To prove two graphs are not isomorphic, consider graph invariants such as degree sequence, number of cycles of each length, connectivity, or the lengths of paths between vertices of the same degree.

要证明两个图不同构，可以考虑图的不变量，例如度序列、各长度回路的数量、连通性，或者同度顶点之间通路的长度。

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

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

IB Mathematics: Definitions and Basic Properties of Graphs | IB数学：图的定义与基本性质