图论中的网络 · 中四

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

把图论思想藏在情境里的真实规划问题：以最低总成本铺设电缆、道路封闭时重新规划配送路线，以及检验一组拟定的连接是否可能存在。学生需自行选择方法。

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

例题 1

市议会将铺设光纤电缆，使五个住宅区 P、Q、R、S 和 T 以最低总成本全部连通（直接相连或经由其他区相连）。各区之间的电缆成本（以 RM'000 计）为 P–Q = 8、P–R = 5、Q–R = 6、Q–S = 9、R–S = 7、R–T = 6、S–T = 4、P–T = 12。

请决定要铺设哪些电缆，并求最低总成本。

要在无多余回路的情况下连通 5 个区，就构建生成树：它需要 5 − 1 = 4 条电缆且不含回路。
把电缆按从便宜到贵排序：S–T = 4、P–R = 5、Q–R = 6、R–T = 6、R–S = 7、P–Q = 8、Q–S = 9、P–T = 12。
选 S–T（4），再选 P–R（5），尚未形成回路。
选 Q–R（6）：把 Q 接入 P、R 组。选 R–T（6）：把 P-Q-R 组接到 S-T 组，五个区至此全部连通。
在 4 条电缆处停止；下一条最便宜的 R–S = 7 会形成回路，故跳过。
最低总成本 = 4 + 5 + 6 + 6 = 21（RM'000）。

例题 2

一名快递员从枢纽 H 出发，必须到达客户 F。道路距离（公里）为 H–A = 4、H–B = 9、A–B = 3、A–C = 8、B–C = 2、B–F = 10、C–F = 3。

（a）求从 H 到 F 的最短路径。（b）当天道路 A–B 因维修封闭，求新的最短路径，以及比原来长多少。

（a）把每条合理路径的距离加总：H–A–C–F = 4 + 8 + 3 = 15 公里。
H–B–C–F = 9 + 2 + 3 = 14 公里；H–A–B–C–F = 4 + 3 + 2 + 3 = 12 公里；H–A–B–F = 4 + 3 + 10 = 17 公里。
最小总和是 12 公里，所以最短路径是 H–A–B–C–F。
（b）A–B 封闭后，删去所有使用 A–B 路段的路径。
在剩下的路径中，H–B–C–F = 14 公里、H–A–C–F = 15 公里，所以新的最短路径是 H–B–C–F = 14 公里。
它比原路径长 14 − 12 = 2 公里。

例题 3

一所学校计划在 7 栋楼之间修建有盖走廊。草案说每栋楼连接的走廊数应为 4、4、3、3、2、2 和 1。

（a）用度数解释为什么这份草案无法实现。（b）规划者把度数为 1 的那栋楼改为度数 2。

请说明新方案可行，并求走廊的总数。

把每栋楼看作顶点、每条走廊看作边，所给的数字就是度数。
度数为奇数的顶点个数必须是偶数，因为所有度数之和等于 2 ×（边数）。
（a）草案中的奇数度数是 3、3 和 1，三栋奇度数的楼，个数为奇数，所以这样的网络不存在。
验证一下，总和 4 + 4 + 3 + 3 + 2 + 2 + 1 = 19 是奇数，但 2 × 边数必为偶数，再次说明不可行。
（b）把 1 改为 2，度数变为 4、4、3、3、2、2、2，现在只有两栋奇度数的楼，是允许的。
总和 = 4 + 4 + 3 + 3 + 2 + 2 + 2 = 20，所以走廊数 = 20 ÷ 2 = 10。

例题 4

一家度假村需铺设水管连接 5 间小屋 A、B、C、D 和 E。两间小屋之间水管的费用（以千令吉计）为：A–B 8，A–C 5，A–E 6，B–C 9，B–D 11，C–D 15，C–E 10，D–E 7。

(a) 求连接全部 5 间小屋且不产生多余环路的最低总费用，并列出所用的水管。(b) 一个较简单的方案把小屋连成一个环 A–B–C–D–E–A。

最低方案比这个环方案便宜多少？

无环路的连接是生成树；5 间小屋需要 5 − 1 = 4 根水管。
从最便宜且不构成环路的水管开始选（由小到大）：A–C 5，再 A–E 6，再 D–E 7，再 A–B 8。
这 4 根水管连接了全部 5 间小屋，所以最低费用 = 5 + 6 + 7 + 8 = 26（千）= RM26 000。
环方案 A–B–C–D–E–A = 8 + 9 + 15 + 7 + 6 = 45（千）= RM45 000。
节省 = 45 000 − 26 000 = RM19 000。

例题 5

一名推销员从 P 镇开车到 T 镇。每条路都有距离和过路费。

汽油费为每公里 RM0.50。各条路为：P–Q（40 km，过路费 RM6）、Q–T（30 km，过路费 RM4）、P–R（50 km，无过路费）、R–T（35 km，过路费 RM3）、Q–R（10 km，过路费 RM1）。

求从 P 到 T 总旅费（汽油加过路费）最低的路线，并说明该费用。

每条路费用 = 距离 × RM0.50 + 过路费。
P–Q = 40 × 0.50 + 6 = 26；Q–T = 30 × 0.50 + 4 = 19；P–R = 50 × 0.50 + 0 = 25；R–T = 35 × 0.50 + 3 = 20.50；Q–R = 10 × 0.50 + 1 = 6。
P–Q–T = 26 + 19 = 45.00。
P–R–T = 25 + 20.50 = 45.50；P–R–Q–T = 25 + 6 + 19 = 50.00。
最低总费用是 RM45.00，沿 P–Q–T。

例题 6

一所学校想建造有盖走道，使 7 座楼形成一个无环路的连通网络（一棵树）。(a) 求所需走道的最少数目。

(b) 一份草案给出各楼的走道数：A 3、B 1、C 2、D 2、E 1、F 2、G 1。证明这与 (a) 中走道数目的树相符。

(a) n 个顶点的树有 n − 1 条边，所以 7 座楼需要 7 − 1 = 6 条走道。
(b) 度数之和 = 3 + 1 + 2 + 2 + 1 + 2 + 1 = 12，边数 = 12 ÷ 2 = 6，与树的 6 条走道相符。
(c) 加建一条走道使边数变为 6 + 1 = 7。
有 7 个顶点和 7 条边的连通图比树（恰需 6 条边）多出一条边，因此必含环路，不能是树。

例题 7

市议会计划修建人行天桥连接6个公园，每个公园相接的天桥数分别为3、3、3、2、2和1。(a) 利用度数之和，判断此方案是否可行。

(b) 若可行，求所需天桥的总数。

度数之和 = 3 + 3 + 3 + 2 + 2 + 1 = 14
14 是偶数，满足“任何图的度数之和必为偶数”这一条件，该方案可行
天桥数 = 度数之和 ÷ 2
天桥数 = 14 ÷ 2 = 7

例题 8

一架送货无人机需要从仓库 W 经中继塔飞往客户所在的公寓 C，因为它无法直接穿越禁飞区。各段可行飞行距离（公里）为 W–P = 3,W–Q = 5,P–Q = 2,P–R = 6,Q–R = 3,Q–C = 8,R–C = 4。

(a) 求从 W 到 C 的最短飞行路线及其总距离。(b) 该无人机电池最多支持飞行11公里便须返回基地充电。

判断无人机能否沿此路线完成送货而无需中途充电。

列出可能的路线及总距离：
W–Q–C = 5 + 8 = 13
W–P–R–C = 3 + 6 + 4 = 13
W–P–Q–R–C = 3 + 2 + 3 + 4 = 12
W–Q–R–C = 5 + 3 + 4 = 12
最短距离为12公里，例如路线 W–Q–R–C
由于 12公里 > 11公里，无人机无法沿此路线完成送货而不中途充电

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

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

常见问题

图论网络的KBAT题目与普通练习题有何不同？

KBAT题目会把网络图放进真实情境中，例如规划送货路线、电缆连接方案或活动配对，并要求你说明理由，比如连接所有顶点所需的最少边数。这类题目不能套用死记的公式，而是要从基本定义（树、度数、连通图）出发进行推理，并用文字清楚解释你的答案，展示逻辑而不仅仅是最终数字。

如何用文字为图论KBAT题目的答案作出合理说明？

先写出你所依据的定义(例如“连接n个顶点的树恰好需要n−1条边”)，再把它套用到题目给出的数字上，并清楚写出结论。用一两句话把规则和题目情境联系起来的说明，比单纯写一个最终数字更容易拿到完整分数。

当图论KBAT题目问“最少需要多少连接”时，常见的陷阱是什么？

学生常常画出一个虽然连通、但并非最简的网络，图中还有一条多余的边，即使去掉它，所有顶点仍然保持连通。在确定最终答案前，检查一下：去掉图中任意一条边是否会使某个顶点失去连接？

如果去掉后仍然连通，说明还有边可以继续删减，答案还没到最简状态。