2001-豫粤卷-12 单-网络流与最大流问题

本题导读

本题考查网络流与最大流问题，以及排列组合与运筹规划。

📌【题干】

Question

（2001年豫粤卷） 如图，小圆圈表示网络的结点，结点之间的连线表示它们有网线相联.连线标注的数字表示该段网线单位时间内可以通过的最大信息量.现从结点 $A$ 向结点 $B$ 传递信息，信息可以分开沿不同的路线同时传递.则单位时间内传递的最大信息量为()

A. 26　　　　　　　B. 24　　　　　　　C. 20　　　　　　　D. 19

🔍【思路分析】

破题导航

1. 识别结构的源与汇：信息从源点 $A$ 出发，最终汇聚到汇点 $B$。
2. 分析第一层分流（流出端）：观察源点 $A$，它直接向外引出两条网线，每条的最大信息量上限均为 12。因此，整个网络可能输入的总流量绝对上限为 $12+12=24$。
3. 路径解耦与瓶颈限流（木桶效应）：

• 将整个网络自上而下解耦拆分为相对独立的干路通道；
• 沿着每一条具体的路径追踪，根据“每条路径上能通过的最大流量取决于该路径上容量最小的那段网线（即瓶颈截面）”这一原则，计算各分支的实际最大流。

4. 累加各干路最大流：将所有不冲突的独立路径流速进行求和，即得全局最大信息量。

✅【答案】

Success

D

✍【详细解析】

Abstract

为了方便表述，对图中的中间结点进行字母标记。源点为 $A$，汇点为 $B$。

• 将 $A$ 上方直接相连的结点记为 $C$（网线 $AC=12$）；

• 将 $A$ 下方直接相连的结点记为 $D$（网线 $AD=12$）。

下面顺着流量的方向，分“上、下”两大主干区域进行瓶颈分析：

1. 分析由 $A\to C$（上干路，总容量为 12）流出的信息分配

从结点 $C$ 出发，信息流向汇点 $B$ 的路径分化为两条：

• 上分支干线：由 $C\to$ 顶端未名结点 $\to B$。
• 网线容量依次为： $5$ 和 $3$。
• 根据木桶效应，该分支的最大通过量为 $\min (5,3)=3$。
• 中上分支干线：由 $C\to$ 中间未名结点 $\to B$。
• 网线容量依次为： $6$ 和 $4$。
• 根据木桶效应，该分支的最大通过量为 $\min (6,4)=4$。

因此，经过 $C$ 结点向左成功分流并汇入 $B$ 的实际最大信息量总和为： $V_{\text{上总}}=3+4=7$ 由于 $7\le 12$（未超出输入端 $AC$ 网线的总负荷），故上干路的实际最大传输量为 7。

2. 分析由 $A\to D$（下干路，总容量为 12）流出的信息分配

从结点 $D$ 出发，信息流向汇点 $B$ 的路径同样分化为两条：

• 中下分支干线：由 $D\to$ 中间未名结点 $\to B$。
• 网线容量依次为： $6$ 和 $7$。
• 根据木桶效应，该分支的最大通过量为 $\min (6,7)=6$。
• 下分支干线：由 $D\to$ 底端未名结点 $\to B$。
• 网线容量依次为： $8$ 和 $6$。
• 根据木桶效应，该分支的最大通过量为 $\min (8,6)=6$。

因此，经过 $D$ 结点向左成功分流并汇入 $B$ 的实际最大信息量总和为： $V_{\text{下总}}=6+6=12$ 由于 $12\le 12$（恰好达到输入端 $AD$ 网线的总负荷满载上限），故下干路的实际最大传输量为 12。

3. 全局总最大信息量汇总

由于上、下两大干路在网络中互不重叠、互不干扰，将两部分的实际最大流量相加，得到单位时间内从 $A$ 传递到 $B$ 的最大信息量为： $V_{\text{全局最大}}=V_{\text{上总}}+V_{\text{下总}}=7+12=19$

D

💡【考点归纳与避坑指南】

Danger

1. 核心考点：运筹学图论基础；网络流的分流与管道瓶颈限流原理（最小割最大流定理的初等化表现）。
2. 核心方法：“干道解耦瓶颈法”。
3. 避坑指南：

• 两端简单求和陷阱：本题极易出现只看首尾两端的错误倾向。例如误认为最大量是流出端 $12+12=24$（从而误选 B），或者看流入汇点 $B$ 的四条线总和 $3+4+7+6=20$（从而误选 C）。
• 忽视中间瓶颈约束：必须牢记，虽然靠近 $B$ 结点的某段网线容量是 $7$，但是从前一级 $D$ 结点分配给它的最大可能信息流量只有 $6$，所以它实际只能通过 $6$ 的流量。网络中任意一条通路的实际流量永远被该通路上的“最小网线容量”所锁死。

📖【试题探源与推广】

Tip

1. 试题探源：本题属于高考数学中极具创新性的应用建模压轴选择题，将离散数学、图论与现代网络通信技术完美交汇。取材于高级数学思想中运筹学“网络流理论（Network Flow Theory）”下的经典最大流应用模型。
2. 结论推广： 网络流的最大流最小割定理指出：一个网络中从源点到汇点的最大流量，严格等于该网络中所有“割（Cut）”的最小容量总和。 在本题中，若在紧靠汇点 $B$ 的左侧切一刀（割），其容量总和为 $3+4+6+6=19$（注意中间的 7 被前级的 6 限流，实际等价截面容量为 6）。这个截面构成了整个网络的最小割，因此全局最大流必然为 12。

🔗【关联脉络】

Multi column

知识锚点 (Nodes)

• 22.01 计数原理、排列与组合
• 25.01 程序框图与基本逻辑结构

类题演练 (Links)

• 1981-全国文-03 解-排列与组合的计数
• 2014-四川卷理-06 单-分类加法计数原理
• 1960-全国-01 解-六小问综合（无理方程排列对数三角测孔径棱锥）