图论中的网络 · 5.1.3
网络中的子图与树
子图是通过保留原图中部分或全部顶点与边、并保持其连接方式而形成的图。树则是一种特殊的连通子图，不含任何闭合回路，其边数恰好比顶点数少一。
学生须能在给定的图中识别这些特征，并自行画出有效的子图与树的例子。
官方学习标准 (5.1.3)
“识别并绘制子图与树。”
它的含义
子图是通过保留原图中部分或全部顶点与边、并保持其连接方式而形成的图。树则是一种特殊的连通子图，不含任何闭合回路，其边数恰好比顶点数少一。
学生须能在给定的图中识别这些特征，并自行画出有效的子图与树的例子。
如何考查
纸卷一可能展示一个图形，要求学生判断它是给定图的子图还是树。纸卷二的结构题则可能要求学生根据题目给出的网络图，绘制指定的子图，或使用给定顶点绘制一棵树。
例题
图中显示一个图 G，顶点为 P、Q、R、S，边为 PQ、QR、RS、SP 和 PR。(a) 画出 G 的一个具有 4 个顶点和 4 条边的子图。
(b) 画出一棵使用全部 4 个顶点、属于 G 的子图的树。
- 子图保留 G 中部分或全部顶点与边，且不改变原有的连接方式。
- 对于(a)，选取边 PQ、QR、RS、SP(去掉对角线 PR)：共用到全部 4 个顶点和 4 条边，形成一个 4 边的环。
- 具有 4 个顶点的树恰好需要 4 − 1 = 3 条边，且不能含有闭合回路。
- 对于(b)，选取边 PQ、QR、RS(去掉 SP 和 PR)：这以 3 条边、无回路的单一路径 P–Q–R–S 连接了全部 4 个顶点。
资料来源:DSKP KSSM Mathematics Form 4 and 5 (Versi English)
预约试课一小时付费试课 · 当天回复 · 每小时RM50起
常见问题
子图和树有什么区别？
子图是从原图中选取部分顶点和边、并保持相同连接方式所形成的任意图形。树则是一种特殊的子图，它必须是连通的、不含任何闭合回路，并且边数恰好比顶点数少一。
含有 n 个顶点的树必须有多少条边？
恰好 n − 1 条边。这是树的一个关键性质：它恰好用足够的边把全部 n 个顶点连接起来而不形成任何闭合回路，因此再去掉任何一条边都会使图不再连通。
树可以包含原图的所有顶点吗？
可以。使用原图中每一个顶点的树称为生成树，只要它保持连通、不含回路，且边数恰好比图中顶点总数少一即可。