图论中的网络
树
无回路的连通网络。
| English | Tree |
|---|---|
| Bahasa Melayu | Pokok |
| 中文 | 树 |
如何使用
四个城镇 A、B、C、D 按 A–B、B–C、B–D 连接构成一棵树，因为它们全部连通却不含回路。有 n 个顶点的树总是恰好有 n − 1 条边，所以 4 个城镇需要 4 − 1 = 3 条道路。
它在 SPM 中出现在哪里
出现在图论中的网络这一章（中五）。第二卷可能要求你辨认或画出一棵树，或求连接所有顶点所需的最少边数，利用有 n 个顶点的树含 n − 1 条边这一事实。
别与这些混淆
网络中的回路树完全没有回路，而含回路的网络有一圈闭合的边回到起点，所以它不是树。
树形图（概率）概率树形图列出结果并沿分支相乘概率，而这里的树是一种网络，其判定标准是连通且无回路。
常见问题
怎样判断一个网络是不是树？
检查两点：网络必须连通，即从任一顶点都能到达其他每个顶点；且必须无回路，即没有闭合的边圈。若两者都成立，它就是树，并且它的边数恰好比顶点数少一。
为什么有 n 个顶点的树有 n − 1 条边？
从一个顶点开始，你每加一条新边就恰好带入一个新顶点而不构成回路。要这样连接 n 个顶点需要 n − 1 条边；再加任何一条边都会形成回路，破坏树的结构。