在流网络中，符号 $c(u,v)$ 意味着什么？

适用条件

• 存在从 $u$ 到 $v$ 的有向边。
• 容量是分配给该特定边的定量属性。

理解与推导

1. 识别图中的有向边 $(u, v)$。
2. 将 $c(u,v)$ 识别为应用于该边的容量函数。
3. 理解该值设定了该边上流量的上限。
4. 将其与管道最大输水能力的物理类比联系起来。

例子

演讲者解释说，每条边 $(u, v)$ 都有一个给定的容量 $c(u,v)$，并使用水管类比，其中管道对应于边，它可以输送的水量对应于 $c(u,v)$。

容易误解的地方

• 认为 $c(u,v)$ 是当前通过该边的实际流量；它是最大限制。
• 假设容量是节点 $u$ 或 $v$ 的属性，而不是它们之间边的属性。
• 认为无向边的双向容量相同，而定义指定的是有向边 $(u,v)$。

观看对应讲解

继续追问

• 流量和容量有什么区别？
• 如何读取流网络图中边上的数字？
• 为什么 $(u,v)$ 中的顺序很重要？