中
预约试课

图论中的网络 · 中四

图论中的网络：例题（中等）

把基础用起来：从加权网络读取距离以比较路径、用完全图数握手次数，并用树的边规则决定要删除哪些边。适合已能串联两三步的学生。

由 spmmath.com.my 编辑团队撰写。

例题 1

图中显示五个城镇之间的道路，距离以公里计：A–B = 4、A–C = 3、B–C = 1、B–D = 6、C–D = 2、C–E = 9、D–E = 3。求从城镇 A 到城镇 E 的最短路径及其长度。

  1. 列出从 A 到 E 的合理路径，并把每条的距离加起来。
  2. A–C–E = 3 + 9 = 12 公里。
  3. A–C–D–E = 3 + 2 + 3 = 8 公里。
  4. A–B–C–D–E = 4 + 1 + 2 + 3 = 10 公里。
  5. A–B–D–E = 4 + 6 + 3 = 13 公里。
  6. 最小的总和是 8 公里，沿 A–C–D–E。

例题 2

六位朋友在聚会上，每人与其他每个人恰好握手一次。把每个人看作顶点、每次握手看作一条边，求每个顶点的度数和握手的总次数。

  1. 每人与其余 5 人握手，所以每个顶点的度数都是 5。
  2. 这构成 6 个顶点的完全图。
  3. 度数之和 = 6 × 5 = 30。
  4. 边数 = 度数之和 ÷ 2 = 30 ÷ 2 = 15。

例题 3

一个连通网络有 10 个顶点和 15 条边。请解释它为什么不可能是树，并求出至少要删除多少条边，才能使剩下的部分成为仍连接全部 10 个顶点的生成树。

  1. 10 个顶点的树恰好有 v − 1 = 10 − 1 = 9 条边。
  2. 这个网络有 15 条边，多于 9，所以它必含回路，不是树。
  3. 10 个顶点的生成树需要 9 条边，并且必须保持连通。
  4. 要删除的边 = 15 − 9 = 6，从每个回路中各删一条，且不使网络断开。

例题 4

一个图有 7 个顶点和 15 条边。其中六个顶点的度数都是 4。

求第七个顶点的度数。

  1. 所有度数之和 = 2 × 边数 = 2 × 15 = 30。
  2. 已知的六个顶点贡献 6 × 4 = 24。
  3. 第七个顶点的度数 = 30 − 24 = 6。

例题 5

加权网络显示宿舍 H 与图书馆 L 之间经过路口 A、B、C 的步行距离（米）：H–A = 120，H–B = 100，A–C = 90，B–C = 150，C–L = 80，B–L = 260。求 H 到 L 的最短距离并说明路线。

  1. 列出 H 到 L 的所有可能路线并把距离相加。
  2. H–A–C–L = 120 + 90 + 80 = 290。
  3. H–B–C–L = 100 + 150 + 80 = 330。
  4. H–B–L = 100 + 260 = 360。
  5. 最小的总和是 290，沿 H–A–C–L。

例题 6

一棵树有 8 个顶点。一个顶点的度数为 3，四个顶点的度数各为 2。

其余的顶点都是叶（度数 1）。求叶的数目。

  1. 8 个顶点的树有 8 − 1 = 7 条边，所以度数之和 = 2 × 7 = 14。
  2. 已知顶点贡献 3 + (4 × 2) = 3 + 8 = 11。
  3. 各叶合计贡献 14 − 11 = 3 的度数。
  4. 每片叶度数为 1，所以叶的数目 = 3 ÷ 1 = 3。

例题 7

某电脑网络通过节点 Y、Z 和路由器 R 将服务器 X 连接到客户端 C。各段传输时间（毫秒）为 X–Y = 5,X–R = 9,Y–R = 3,Y–Z = 8,R–Z = 2,R–C = 10,Z–C = 4。

求从 X 到 C 的最短总传输时间，并写出路线。

  1. 列出可能的路线及其总时间：
  2. X–Y–R–C = 5 + 3 + 10 = 18
  3. X–Y–Z–C = 5 + 8 + 4 = 17
  4. X–Y–R–Z–C = 5 + 3 + 2 + 4 = 14
  5. X–R–Z–C = 9 + 2 + 4 = 15
  6. 最小总时间为14，路线为 X–Y–R–Z–C

例题 8

一个连通图有9个顶点。其中6个顶点的度数各为3,2个顶点的度数各为4，余下1个顶点的度数为2。

求该图的边数总和。

  1. 度数之和 = 6(3) + 2(4) + 1(2)
  2. 度数之和 = 18 + 8 + 2 = 28
  3. 边数 = 度数之和 ÷ 2
  4. 边数 = 28 ÷ 2 = 14

资料来源:DSKP KSSM Mathematics Form 4 and 5 (Versi English)

预约试课一小时付费试课 · 当天回复 · 每小时RM50起

常见问题

中等难度的图论题目（涉及树和子图）该如何解答？

中等难度题目通常要求你辨认或画出一棵树(tree，即没有回路的连通图)或从较大网络中找出一个子图(subgraph)，有时还涉及边的权重(weighted edge)。建议按步骤进行：先列出所有顶点和边，画树时检查图中是否真的没有形成闭合回路，画子图时确保保留的每一条边都确实存在于原网络中，不要凭空添加。

处理这类题目中的加权边(weighted edge)时，常见的陷阱是什么？

学生有时会把整个网络中所有边的权重都加起来，而不是只加题目要求的那棵树或子图所包含的边。在求和之前，先圈出题目真正要求的边，是总距离、最短连接路径，还是特定路线，因为多算或少算一条边，最终答案就会完全不同，这是丢分的常见原因。

中等难度的图论题目需要展示多少运算过程？

应清楚标注最终图形，并把总数（例如权重之和）单独写成一行，而不是埋没在图中不易被看到。如果你尝试过不止一棵树或一条路线，只需保留最后正确的那一份，画得清晰整洁，阅卷人是根据标注清楚的最终答案给分，而不是根据散乱的草稿来判断。

预约试课

预约试课
一小时付费试课 · 当天回复每小时RM50起
预约试课