IB Mathematics: Trees – Concepts and Properties | IB数学：树的概念与性质

📚 IB Mathematics: Trees – Concepts and Properties | IB数学：树的概念与性质

Trees are one of the most fundamental structures in graph theory, appearing throughout the IB Mathematics curriculum in discrete mathematics. A tree is a connected graph with no cycles, but this simple definition leads to a rich set of properties and applications, from network design to decision processes. This article explores the key concepts and properties of trees, with clear examples and exam-style reasoning to help you master the topic.

树是图论中最基本的结构之一，在IB数学课程的离散数学部分中反复出现。树是没有回路的连通图，但这个简单的定义却衍生出丰富的性质与应用，从网络设计到决策过程都离不开树。本文将深入探讨树的核心概念与性质，配以清晰例题和考试风格推理，帮助你全面掌握这一主题。

1. Definition of a Tree | 树的定义

A tree is a connected graph that contains no cycles. “Connected” means there is a path between every pair of vertices, and “no cycles” means you cannot start at a vertex, follow distinct edges, and return to the starting vertex. A simple example is a chain of three vertices connected by two edges: it is connected and has no way to loop back.

树是一个连通图，且不包含任何回路。”连通”意味着任意两个顶点之间都存在一条路径；”无回路”意味着你不可能从一个顶点出发，沿着互不相同的边行走，最终回到起点。一个简单例子是由三个顶点和两条边组成的链：它是连通的，且没有任何方式绕回原点。

Equivalently, a tree can be defined as a graph in which there is exactly one path between any two vertices. This uniqueness of paths is a powerful idea: if two different paths existed between the same pair of vertices, their union would contain a cycle, contradicting the definition.

等价地，树也可以定义为任意两个顶点之间恰好存在一条路径的图。路径的唯一性是一个强有力的概念：如果同一对顶点之间存在两条不同的路径，它们的并集就会包含一个回路，这与定义相矛盾。

2. The Vertices and Edges Relationship | 顶点与边的关系

The single most important property of a tree is the relationship between its number of vertices v and its number of edges e. For any tree, the number of edges is always one less than the number of vertices:

树最重要的性质之一是其顶点数 v 与边数 e 之间的关系。对于任何树，边数总是等于顶点数减一：

e = v − 1

This formula is both intuitive and testable. Consider a tree with 6 vertices: it must have exactly 5 edges. If a connected graph with 6 vertices has 6 or more edges, it must contain a cycle. Conversely, if a connected graph with 6 vertices has only 4 edges, it cannot be connected because at least 5 edges are required to connect 6 vertices.

这个公式既直观又便于检验。考虑一个拥有6个顶点的树，它必然恰好有5条边。如果一个拥有6个顶点的连通图有6条或更多的边，它必然包含回路；反之，如果这个连通图只有4条边，它不可能连通，因为至少需要5条边才能把6个顶点连成一体。

A useful alternative way to remember this: a tree is a minimal connected graph. If you remove any edge from a tree, the graph becomes disconnected. If you add any new edge between two existing vertices, you create exactly one cycle. This “minimal connectivity” and “maximal acyclicity” characterises trees uniquely.

一个有助于记忆的等价说法：树是”极小的连通图”。如果你从树中移除任意一条边，图就会变得不连通；如果你在任意两个已有顶点之间添加一条新边，则会刚好产生一个回路。这种”最小连通”与”最大无回路”的双重特性唯一地刻画了树。

3. Leaves and Internal Vertices | 叶子与内部顶点

A leaf (also called a terminal vertex) is a vertex of degree 1 in a tree. Internal vertices have degree greater than 1. Every tree with at least two vertices has at least two leaves. This is a classic result: consider any longest path in the tree; its endpoints cannot have any additional neighbours, otherwise the path could be extended or a cycle would form.

叶子（也称为端顶点）是树中度数为1的顶点。内部顶点的度数大于1。任何至少包含两个顶点的树都至少有兩片叶子。这是一个经典结论：考虑树中任意一条最长路径，其端点不可能再有其它邻点，否则路径可以延长或形成回路。

This property is frequently used in proofs and in inductive arguments. For example, to prove that a tree with v vertices has v − 1 edges, we can pick a leaf, remove it along with its single incident edge, and apply induction on the smaller tree.

这一性质常用于证明和归纳论证。例如，为了证明一棵具有 v 个顶点的树有 v − 1 条边，我们可以选取一片叶子，将它与它唯一关联的边一起移除，然后对更小的树进行归纳。

In IB exam questions, you may be asked to count leaves given degree information. For instance, suppose a tree has 10 vertices and exactly 3 vertices of degree 3; all other vertices are leaves. How many leaves are there? Let L be the number of leaves. Summing degrees: 3 × 3 + 1 × L = 2e = 2(v − 1) = 18. Thus 9 + L = 18, so L = 9. Check: 3 internal vertices plus 9 leaves gives 12 vertices, not 10 — so the premise must be adjusted. A correct example: a tree with 10 vertices might have 2 vertices of degree 3 and 8 leaves. Sum of degrees: 6 + 8 = 14 = 2 × 7, and 7 edges matches 10 − 3? No — recheck carefully. In a tree with 10 vertices, edges = 9, so sum of degrees = 18. If 2 vertices have degree 3 and the rest have degree 1, then 6 + 8 = 14 ≠ 18. We would need additional internal vertices. This illustrates why the degree-sum formula is so powerful in tree problems.

在IB考试中，你可能会被要求根据度数信息计算叶子的数量。例如，假设一棵树有10个顶点，其中恰好有3个度数为3的顶点，其余顶点都是叶子。问有多少片叶子？设叶子数为 L。对所有度数求和：3 × 3 + 1 × L = 2e = 2(v − 1) = 18。于是 9 + L = 18，得 L = 9。但检验一下：3个内部顶点加9片叶子共12个顶点，不是10，因此前提需要调整。一个正确的例子：一棵有10个顶点的树可能有2个度数为3的顶点和8片叶子。度数之和为6 + 8 = 14 = 2 × 7，而7条边也不符合10 − 3？不对——要仔细重新计算。在一棵有10个顶点的树中，边数等于9，所以度数之和等于18。如果2个顶点度数为3，其余度数为1，则6 + 8 = 14 ≠ 18。我们需要额外的内部顶点才能满足条件。这说明度数求和公式在树的问题中何等有力。

4. Spanning Trees | 生成树

A spanning tree of a connected graph G is a subgraph that is a tree and that contains every vertex of G. Since a tree with v vertices has v − 1 edges, a spanning tree keeps the graph connected using exactly the minimum number of edges. Every connected graph has at least one spanning tree.

连通图 G 的生成树是指 G 的一个子图，它是一棵树，并且包含 G 的所有顶点。由于具有 v 个顶点的树有 v − 1 条边，生成树用恰好最少的边数保持图的连通性。每个连通图都至少存在一棵生成树。

Finding a spanning tree is simple: start with the whole graph, and repeatedly remove any edge that does not disconnect the graph, until no more such edges remain. The result is always a tree. Graphically, if you have a square (4 vertices, 4 edges), you can remove one edge to obtain a spanning tree with 3 edges — there are 4 possible spanning trees, one for each edge removed.

寻找生成树很简单：从整个图出发，反复移除任何不会使图断开的边，直到无法再移除为止。最终结果一定是一棵树。以正方形为例（4个顶点、4条边），你可以移除一条边得到有3条边的生成树——共有4种可能的生成树，分别对应移除不同的边。

In IB problems, you may be asked to draw a spanning tree, or to determine how many edges must be removed from a given graph to obtain a spanning tree. If the graph has v vertices and e edges, the number of edges to remove is e − (v − 1). For a graph with 8 vertices and 12 edges, you must remove 5 edges.

在IB问题中，你可能会被要求画出生成树，或确定从给定图中移除多少条边才能得到生成树。如果图有 v 个顶点和 e 条边，需要移除的边数为 e − (v − 1)。对于一个有8个顶点和12条边的图，你必须移除5条边。

5. Minimum Spanning Tree (MST) | 最小生成树

When edges have weights — representing cost, distance, or time — a minimum spanning tree is a spanning tree whose total edge weight is as small as possible. Two famous algorithms are used to find an MST: Kruskal’s algorithm and Prim’s algorithm.

当边具有权重时——代表成本、距离或时间——最小生成树就是总边权尽可能小的生成树。寻找MST有两个著名算法：克鲁斯卡尔算法（Kruskal’s algorithm）和普里姆算法（Prim’s algorithm）。

Kruskal’s algorithm: Sort all edges by increasing weight. Add edges one by one, skipping any edge that would create a cycle, until v − 1 edges have been added.
Prim’s algorithm: Start from any vertex. Repeatedly add the cheapest edge that connects a vertex already in the tree to a vertex not yet in the tree, until all vertices are included.

克鲁斯卡尔算法：将所有边按权重从小到大排序。逐条加入边，跳过任何会形成回路的边，直到加入了 v − 1 条边为止。
普里姆算法：从任意一个顶点出发。反复加入连接”已在树中的顶点”与”尚未在树中的顶点”的最便宜边，直到所有顶点都被包含。

Both algorithms always produce a minimum spanning tree, though the specific tree may differ when edge weights are not unique. The total weight of the MST is unique even if the tree itself is not. In IB exams, you may be asked to apply either algorithm step by step and state the minimum total weight.

两种算法都一定能产生最小生成树，但当边权不唯一时，具体的树可能不同。MST的总权值是唯一的，即使树本身不唯一。在IB考试中，你可能会被要求逐步应用其中一种算法，并写出最小总权值。

Total weight of MST = sum of the chosen edges’ weights

最小生成树的总权值 = 所选各边的权值之和

6. Rooted Trees and Binary Trees | 有根树与二叉树

A rooted tree is a tree in which one vertex is designated as the root. This gives a natural hierarchy: the root is at level 0, its neighbours at level 1, and so on. Edges can be oriented away from the root, creating parent–child relationships. Rooted trees are used to model family trees, file systems, and decision processes.

有根树是指其中一个顶点被指定为根的树。这赋予树自然的层次结构：根位于第0层，其邻点位于第1层，依此类推。边可以指向远离根的方向，形成父子关系。有根树用于建模族谱、文件系统和决策过程。

A binary tree is a rooted tree in which every vertex has at most two children, commonly called the left child and the right child. If every vertex has either 0 or 2 children, the tree is called a full binary tree. A full binary tree with n leaves always has n − 1 internal vertices. This is a direct consequence of the general tree formula combined with the degree structure.

二叉树是一种有根树，其中每个顶点至多有两个子节点，通常称为左子节点和右子节点。如果每个顶点要么有0个子节点，要么有2个子节点，则称为满二叉树。具有 n 片叶子的满二叉树总是有 n − 1 个内部顶点。这是一般树公式结合度数结构的直接推论。

For a full binary tree: total vertices = internal vertices + leaves. Since every internal vertex has degree 3 except the root (degree 2), and leaves have degree 1, the degree-sum formula can be applied to prove the relationship. If there are I internal vertices and L leaves, then total vertices = I + L, and edges = I + L − 1. Sum of degrees: 2 (root) + 3(I − 1) + L = 2(I + L − 1). Simplifying gives L = I + 1, hence I = L − 1.

对于满二叉树：总顶点数 = 内部顶点数 + 叶子数。由于每个内部顶点除根外度数都为3，根的度数为2，叶子度数为1，可以利用度数求和公式证明这一关系。设内部顶点数为 I，叶子数为 L，则总顶点数 = I + L，边数 = I + L − 1。度数之和：2（根）+ 3(I − 1) + L = 2(I + L − 1)。化简得 L = I + 1，因此 I = L − 1。

7. Applications of Trees | 树的应用

Trees are not just theoretical objects; they appear in many practical contexts. In computer science, binary search trees allow efficient searching, sorting, and data retrieval. In network design, minimum spanning trees minimise the total cable length needed to connect a set of computers. In biology, phylogenetic trees represent evolutionary relationships among species.

树不仅仅是理论对象，它们出现在许多实际场景中。在计算机科学中，二叉搜索树实现了高效的搜索、排序和数据检索。在网络设计中，最小生成树最小化连接一组计算机所需的总电缆长度。在生物学中，系统发育树表示物种之间的进化关系。

In IB Mathematics, tree diagrams are also used in probability to represent sequential events. Although these are not graph-theory trees in the formal sense, they share the same branching structure: a connected graph with no cycles, where each path from the root represents a sequence of outcomes. The probabilities along each branch multiply to give the probability of the final outcome.

在IB数学中，树形图也用于概率中表示顺序事件。虽然这些不是严格图论意义上的树，但它们具有相同的分支结构：一个无回路的连通图，从根到每条路径代表一个结果序列。沿每条分支的概率相乘，得到最终结果的概率。

A classic graph-theory application is the “minimum connector problem”: connect several cities by roads or cables at minimum total cost. The solution is exactly the minimum spanning tree of the weighted graph, which can be found using Kruskal’s or Prim’s algorithm.

一个经典的图论应用是”最小连接问题”：以最小总成本用道路或电缆连接若干城市。其解决方案正是加权图的最小生成树，可以用克鲁斯卡尔或普里姆算法求得。

8. Examples and Exam-Style Questions | 例题与考试风格题目

Let us work through a typical IB-style question. Consider the following weighted graph with vertices A, B, C, D, E and edges: AB = 4, AC = 2, AD = 5, BC = 3, CE = 6, DE = 1. Find a minimum spanning tree using Prim’s algorithm starting from A.

让我们完成一道典型IB风格题目。考虑如下带权图，顶点为A、B、C、D、E，边为：AB = 4, AC = 2, AD = 5, BC = 3, CE = 6, DE = 1。使用普里姆算法从A出发求最小生成树。

Start from A: the cheapest edge from A to an unvisited vertex is AC (2). Add C. Now the tree contains A and C. The cheapest edge connecting {A, C} to {B, D, E} is AB (4) or BC (3); BC = 3 is cheaper, so add B. The tree contains {A, C, B}. Next, the cheapest edge to an unvisited vertex: from A to D is 5, from C to E is 6, from B to D? — no edge listed. DE = 1 is between two unvisited vertices, so it cannot be used yet. We must connect D or E. From the tree, the available edges are AD = 5 and CE = 6, so add AD = 5. Now vertices A, C, B, D are in the tree. Finally, connect E: CE = 6 or DE = 1, but DE connects D (already in tree) to E, so add DE = 1. The MST has edges AC, BC, AD, DE, with total weight 2 + 3 + 5 + 1 = 11.

从A出发：从A到未访问顶点的最便宜边是AC（权2）。加入C。现在树包含A和C。连接{A, C}与{B, D, E}的最便宜边分别是AB（4）和BC（3）；BC = 3更便宜，所以加入B。树包含{A, C, B}。下一步，连接到未访问顶点的最便宜边：A到D为5，C到E为6，B到D没有列出边；DE = 1连接两个未访问顶点，因此暂时不能使用。我们必须连接D或E。从树中可用的边是AD = 5和CE = 6，所以加入AD = 5。现在树包含顶点A、C、B、D。最后连接E：CE = 6或DE = 1，但DE连接D（已在树中）到E，所以加入DE = 1。因此MST的边为AC、BC、AD、DE，总权重为2 + 3 + 5 + 1 = 11。

Notice that during Prim’s algorithm, the tree grows as a single connected component from the root. In Kruskal’s algorithm, we would sort all edges: DE (1), AC (2), BC (3), AB (4), AD (5), CE (6). Then add DE, AC, BC. The next cheapest edge AB would create a cycle (A–C–B–A), so skip it. Then add AD. The total is again 11.

注意在普里姆算法的过程中，树从根开始作为一个连通整体不断生长。而在克鲁斯卡尔算法中，我们先对所有边排序：DE（1）、AC（2）、BC（3）、AB（4）、AD（5）、CE（6）。然后依次加入DE、AC、BC。下一条最便宜的边AB会形成回路（A–C–B–A），因此跳过。再加入AD。总权值仍然是11。

9. Common Pitfalls and Key Takeaways | 常见误区与核心要点

Students often confuse the conditions for a tree. A graph with no cycles but disconnected is a forest, not a tree. A graph that is connected but contains a cycle is not a tree. Both conditions — connectivity and acyclicity — must hold simultaneously.

学生经常混淆树的判定条件。没有回路但不连通的图是森林（forest），而不是树。连通但包含回路的图也不是树。”连通”和”无回路”这两个条件必须同时满足。

Another common error is misapplying the edge formula. The formula e = v − 1 only applies to trees, not to all connected graphs. However, if you know a connected graph with v vertices and e = v − 1 edges, you can conclude it is a tree. This “if and only if” relationship is worth memorising.

另一个常见错误是误用边数公式。e = v − 1 仅适用于树，而非所有连通图。但如果已知一个连通图有 v 个顶点且 e = v − 1 条边，则可以断定它是一棵树。这种”当且仅当”的关系值得牢记。

Key takeaways: (1) A tree is a connected acyclic graph. (2) For a tree, e = v − 1. (3) Every tree with at least two vertices has at least two leaves. (4) A spanning tree of a connected graph has v − 1 edges. (5) Kruskal’s and Prim’s algorithms both find a minimum spanning tree. (6) The degree-sum formula is a reliable tool for solving tree problems involving vertex degrees.

核心要点：（1）树是连通的无回路图。（2）对于树，e = v − 1。（3）每个至少有两个顶点的树都至少有两片叶子。（4）连通图的生成树有 v − 1 条边。（5）克鲁斯卡尔算法和普里姆算法都能找到最小生成树。（6）度数求和公式是解决涉及顶点度数的树问题的可靠工具。

10. Practice Problem | 练习题目

Question: A tree has 12 vertices. Three vertices have degree 4, two vertices have degree 2, and all the others are leaves. Find the number of leaves.

问题：一棵树有12个顶点。其中3个顶点度数为4，2个顶点度数为2，其余顶点都是叶子。求叶子的数量。

Solution: Let L be the number of leaves. The number of edges is 12 − 1 = 11. Sum of degrees = 2 × 11 = 22. We have 3 × 4 + 2 × 2 + 1 × L = 22. Thus 12 + 4 + L = 22, so L = 6. Checking the total vertices: 3 + 2 + 6 = 11, not 12. This indicates an inconsistency in the given statement. In a valid problem, the number of vertices would need to be 11, or the degrees adjusted to satisfy the vertex count.

解答：设叶子数为 L。边数为 12 − 1 = 11。度数之和 = 2 × 11 = 22。我们有 3 × 4 + 2 × 2 + 1 × L = 22，即 12 + 4 + L = 22，所以 L = 6。检验总顶点数：3 + 2 + 6 = 11，不等于12。这说明题设条件存在矛盾。在有效问题中，顶点总数应为11，或需要对度数条件进行调整。

This example demonstrates the importance of consistency checks. The degree-sum formula provides an equation, but you must also ensure that the total number of vertices matches. In an exam, be prepared to detect such contradictions and state that the situation is impossible.

这个例子说明了一致性检验的重要性。度数求和公式给出了一个方程，但你还需要确保总顶点数吻合。在考试中，要准备好发现这类矛盾并指出该情形不可能成立。

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

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

IB Mathematics: Trees – Concepts and Properties | IB数学：树的概念与性质