用图论术语来说，什么是流网络？

适用条件

• 图是有向的。
• 存在一个源顶点 $s$ 和一个汇顶点 $t$。
• 每条有向边 $(u, v)$ 都有一个相关的容量 $c(u,v)$。

理解与推导

1. 将图识别为有向图 $G(V, E)$。
2. 定位两个特殊顶点：源点 $s$ 和汇点 $t$。
3. 认识到 $V$ 是顶点集，$E$ 是有向边集。
4. 注意到每条边 $(u, v)$ 都带有一个容量值 $c(u,v)$。

例子

视频将流网络定义为写为 $G(V, E)$ 的有向图，带有源点 $s$ 和汇点 $t$，其中每条边 $(u, v)$ 都有一个给定的容量 $c(u,v)$。

容易误解的地方

• 假设图是无向的；定义明确要求是有向图。
• 认为容量是顶点的属性而不是边的属性。
• 认为在这个基本定义中，流网络可以有多个源点或汇点，而没有指定单一的 $s$ 和 $t$。

观看对应讲解

继续追问

• 符号 $c(u,v)$ 意味着什么？
• 为什么 $(u,v)$ 中的顺序很重要？
• 流量和容量有什么区别？