speedrun2｜第2章 数学与工程基础·离散与图论速通

ONEPSOFT | 软考学习知识库

---

speedrun2｜第2章 数学与工程基础·离散与图论速通

一、章节定位

一句话概括：本章是系统分析师的 " 数学工具箱 "——图论（连通/最短路/最大流）、统计、预测决策、建模、工程伦理。选择题常考图论算法特点与复杂度。

• 题型覆盖：综合知识【✓】 ｜ 案例分析【△（最大流偶有出现）】 ｜ 论文【✗】
• 重要性等级：【3 星】——图论是计算/选择双高频；排队论、线性规划见本组对应笔记。
• 教材出处：第 2 章 数学与工程基础（2.1 统计、2.2 图论应用、2.3 预测与决策、2.4 数学建模、2.5 工程伦理）

二、本章在讲什么（系统性阐述）

信息系统分析离不开量化工具。本章把工程中常用的数学方法系统讲一遍：用图论解决 " 连通/路径/流量 " 类网络问题；用统计做不确定性分析（为排队论铺路）；用预测决策辅助方案选择；用建模把现实问题抽象成可计算模型；最后用工程伦理兜住 " 技术要对人负责 "。

将图论类比土木场景：把楼栋/路口/设备当 " 顶点 "，把路/管线/链路当 " 边（带权重=距离/造价/容量）"，于是 " 如何用最少造价把全小区连通 "=" 最小生成树 "，" 从料场运料到各工地怎么最省时 "=" 最短路径 "，" 一条供水管网最大能输多少水 "=" 最大流 "。

三、教材原文精摘

【最小生成树】 " 在连通的带权图的所有生成树中，权值和最小的生成树（包含图中所有顶点的树），称作最小生成树。"

【Prim 算法】 " 普里姆（Prim）算法……每次选边 (i,j) 使 i∈U, j∈V−U 且具有最小代价……特点：T 始终是一棵树，贪心策略；时间复杂度 O(n²)，与边数无关，适合稠密图。"

【Kruskal 算法】 " 克鲁斯卡尔（Kruskal）算法……按边长递增顺序选 E 中 n−1 条安全边（两端是森林中两棵树顶点的边）……时间复杂度 O(e log₂e)，与顶点数无关，适合稀疏图。"

【最短路径·Dijkstra】 " 迪杰斯特拉（Dijkstra）算法（单源最短路径）……初始化 SD(s)=0，S={s}；每次选蓝点集中 SD 最小者扩充进 S……D\[k] 即最短距离。"

【最大流量】 " 从节点①到节点⑥的最大流量应是各条路径上的最大流量之和，每条路径上的最大流量应是其各段流量的最小值。"

逐段讲解：

• 最小生成树：连通所有点、总权重最小、无环。" 造价最低的全连通管网 "。

• Prim：从某点出发，每次贪心选 " 已连集合到未连集合 " 的最短边，像 " 从一栋楼往外一圈圈接管 "。稠密图（边多）用 Prim 更划算（O(n²) 只看点数）。

• Kruskal：先把所有边按权排序，由小到大捡、不形成环就保留。像 " 先把最便宜的管段都列出来，依次接，接出环就跳过 "。稀疏图（边少）用 Kruskal 更划算（O(e log e) 只看边数）。

• Dijkstra：单源最短路，只支持非负权；本质是 " 红点（已确定最短路）不断吞并最近的蓝点 "。

• 最大流：从源到汇所有增广路径流量之和，每条路径流量受 " 最细的管子 " 限制（木桶短板）。、

四、核心知识树

第 2 章 数学基础

├── 图论应用

│ ├── 最小生成树 (Prim/Kruskal)

│ ├── 最短路径 (Dijkstra/Floyd)

│ └── 最大流

├── 统计与概率 (见#20)

├── 预测与决策 (见#21)

└── 建模与伦理

五、知识脑图总结

思维导图（结构化呈现）

• 第2章 数学基础
  • 图论
    • 最小生成树
      • Prim稠密
      • Kruskal稀疏
    • 最短路
      • Dijkstra
      • Floyd
    • 最大流
  • 概率统计
  • 预测决策
  • 建模伦理

六、关键概念速解

概念	教材定义（原文关键词）	大白话速解	考试怎么考
最小生成树	权值和最小的生成树	最省的管网连通所有楼	选择：算法适用/结果
Prim	O(n²)，适合稠密图	从一点往外圈圈接管	选择：复杂度/适用
Kruskal	O(e log e)，适合稀疏图	边排序由小捡、不环就留	选择：复杂度/适用
Dijkstra	单源最短路，非负权	红点吞并最近蓝点	选择：能否处理负权
最大流	各路径流量之和，受最小段限	水管网最大输水量	选择/案例

七、记忆口诀 & 类比

• 口诀：「密 Prim 疏 Kruskal，最短路Dijkstra（非负），最大流看短板」。
• 类比：最小生成树=用最少造价把小区所有楼栋接通自来水管；最短路=钢筋从料场运到各楼座的最短吨公里；最大流=市政供水干管能往小区泵进的最大水量（受最细管段卡脖子）。负权边 Dijkstra 算不了，就像 " 走某段路反而倒赚时间 " 在工程里不现实，需用 Bellman-Ford。

八、易混淆点对比

易混项 A	易混项 B	核心区别
Prim	Kruskal	前者 O(n²) 看点数、适合稠密；后者 O(e log e) 看边数、适合稀疏
最小生成树	最短路径	前者连通所有点总权最小；后者求某两点间最小权路径
Dijkstra	Floyd	前者单源；后者任意两点（动态规划）

九、与其他章节的关联

• 上游 / 前置：离散数学是图论基础；概率统计（#20）是排队论前置。
• 下游 / 依赖：第 8 章进度网络图（PDM/关键路径，#30）本质是 " 带权有向图最長路 "；运筹（#21）共用优化思想；运维服务（系规）里容量规划/流量调度也用最大流思想。
• 联动考点：最大流偶见于案例；图论算法特点几乎年年选择考。

十、本章一句话总结 & 备考提醒

图论三板斧——最小生成树（Prim 密 / Kruskal 疏）、最短路径（Dijkstra 单源非负权）、最大流（短板决定总量）；记清算法复杂度与适用图类型即可稳拿选择题。计算类排队论/线性规划见本组对应笔记。