流网络 - 佐治亚理工学院 - 可计算性、复杂性、理论：算法

1. 公式
   观察依据

   黑板上在‘流网络’标题下写出 $G = (V, E)$。

2. 声音
   观察依据

   讲师指出，流网络包含有向图 G 等要素。

G

流网络中的有向图部分。

顶点集与边集构成的二元组 (V, E)。

1. 公式
   观察依据

   黑板上出现 $G = (V, E)$。

2. 声音
   观察依据

   讲座中提到了图中的顶点以及顶点对。

V

有向图 G 的顶点集。

一个有限的顶点集合。

1. 公式
   观察依据

   黑板上写出 $G = (V, E)$ 以及 (u,v) $\in E \Rightarrow (v,u) \notin E$。

2. 声音
   观察依据

   讲师指出不允许存在反平行边。

E

有向图 G 的边集。

一组顶点的有序对。

1. 公式
   观察依据

   黑板上使用 (u,v) ∈ E 和 $C(u,v)$。

2. 声音
   观察依据

   讲师谈到每一对顶点，以及两个顶点之间的流量。

(u,v)

一对有序顶点，用于表示一条有向边，或表示 u 与 v 之间的容量/流量值。

u、v 属于 V。

1. 公式
   观察依据

   黑板上写出“源点”s，并且对所有 $v \in V$，均有 (v,s),(t,v) ∉ E。

2. 图示
   观察依据

   最左侧的节点标记为 s。

3. 声音
   观察依据

   讲师说，源点通常标记为 s，是网络中流动事物的起始位置。

s

流网络中的源点顶点。

顶点集 V 中一个被特别指定的顶点。

1. 公式
   观察依据

   黑板上写出“汇点”t，并且对所有 $v \in V$，均有 (v,s),(t,v) ∉ E。

2. 图示
   观察依据

   最右侧的节点标记为 t。

3. 声音
   观察依据

   讲师说，汇点通常标记为 t，是流量最终到达的位置。

t

流网络中的汇点。

顶点集 V 中的一个特殊顶点。

1. 公式
   观察依据

   黑板上写出容量函数 C : $V \times V$ → ℕ ∪ {0}，且当 (u,v) ∉ E 时，$C(u,v) = 0$。

2. 声音
   观察依据

   讲师说，每一对顶点都关联一个容量。

C

为每一对有序顶点分配一个非负整数容量的容量函数。

C：$V \times V$ → 自然数集 ∪ {0}。

1. 公式
   观察依据

   黑板上写出流函数 f : $V \times V$ → [0,$\infty$)。

2. 声音
   观察依据

   讲师说，流本身是一个从顶点对到非负实数的函数。

f

定义在顶点有序对上的流函数。

f : $V \times V \to$ [0,$\infty$).

1. 公式
   观察依据

   黑板上写出 f^{in}(u) = $\sum _{v \in V} f(v,u)$。

2. 声音
   观察依据

   讲师将 f^{in} 定义为流入某一顶点的流。

f^{in}(u)

顶点 u 处的总流入量。

对每个 $u \in V$，通过对所有 $v \in V$ 求和来定义。

1. 公式
   观察依据

   黑板上写出 f^{out}(u) = $\sum_{v \in V} f(u,v)$。

2. 声音
   观察依据

   讲师将 f out 定义为流出量。

f^{out}(u)

顶点 u 处的总流出量。

对每个 $u \in V$，通过对所有 $v \in V$ 求和来定义。

1. 公式
   观察依据

   黑板上写出流值 |f| = f^{out}(s) = f^{in}(t)。

2. 声音
   观察依据

   讲师指出，流的整体值定义为从源点 s 流出的量，或等价地定义为流入汇点 t 的量。

|f|

流的值。

由流函数 f 决定的一个非负实数。

1. 公式
   观察依据

   黑板上展示 $G = (V, E)$；若 (u,v) ∈ E，则 (v,u) ∉ E。

2. 声音
   观察依据

   讲师指出，流网络包含有向图 G 等要素，并说明禁止反平行边以简化公式。

视频首先通过指定其底层结构来介绍流网络：一个有向图 $G=(V,E)$，并附加限制条件——若 (u,v) 是一条边，则 (v,u) 不能是边。主讲人明确指出，这一限制仅为简化后续公式，并非实质性约束。

1. 该图是有向的。

2. 不允许存在反平行边。

3. 该限制被表述为一项简化假设。

1. 公式
   观察依据

   黑板上写着“源点”s、“汇点”t、“内部点”，以及对所有 $v \in V$，均有 (v,s),(t,v) ∉ E。

2. 图示
   观察依据

   最左侧的节点标记为 s，最右侧的节点标记为 t。

3. 声音
   观察依据

   主讲人区分出源点 s 和汇点 t，并将其余所有顶点称为内部顶点；他还假定 s 没有入边、t 没有出边。

流网络包含两个特殊顶点：源点 s 和汇点 t；其余所有顶点统称为内部顶点。视频进一步施加边界条件，使得没有边进入 s，也没有边从 t 出发。

1. s 是源点。

2. t 是汇点。

3. 其余所有顶点均为内部顶点。

4. 源点 s 没有入边。

5. 汇点 t 没有出边。

1. 流网络是一种不含反平行边的有向图

1. 公式
   观察依据

   黑板上写出容量函数 C : $V \times V$ → ℕ ∪ {0}，且当 (u,v) ∉ E 时，$C(u,v) = 0$。

2. 图示
   观察依据

   红色数字标在所画图的边上。

3. 声音
   观察依据

   讲师说明：每一对顶点都有一个容量，表示两点之间可直接传输的流量大小；容量为非负整数；若两点间无边，则容量为零。

每个有序顶点对都被赋予一个容量 $C(u,v)$。在本讲解中，容量为非负整数，且非边对应的顶点对容量为0。图中通过在有向边上标注红色数字来示意这一点。

1. 容量为非负整数。

2. 若 (u,v) 不是一条边，则 $C(u,v) = 0$。

3. 容量衡量两点之间可直接传输的流量大小。

1. 流网络是一种不含反平行边的有向图

1. 公式
   观察依据

   黑板上写出流函数 f : $V \times V$ → [0,$\infty$)，满足：1) $f(u,v) \le C(u,v)$，且2) $f(u,v) + f(v,u) = 0$。

2. 声音
   观察依据

   讲师指出，流是从顶点对到非负实数的函数，必须是非负的，不能超过容量，并且任意两个顶点之间至少有一个方向的流为零。

流是一个定义在顶点有序对上的函数 f，取值于非负实数。视频中指出两条直接约束：流不能超过容量；对任意一对顶点，两个相反方向中至少有一个方向的流为零。

1. f 是非负的。

2. $f(u,v)$ 不能超过 $C(u,v)$。

3. 对每一对 u,v，$f(u,v)$ 和 $f(v,u)$ 中至少有一个是0。

1. 定义在顶点对上的容量函数

1. 公式
   观察依据

   黑板上写出 f^{in}(u)=$\sum_{v \in V} f(v,u)$，f^{out}(u)=$\sum_{v \in V} f(u,v)$，以及对内部顶点 u 有 f^{in}(u)=f^{out}(u)。

2. 声音
   观察依据

   讲师指出流必须在每个内部顶点处守恒，定义了 f^{in} 和 f^{out}，并直观解释道：内部节点既不能产生流，也不能吸收流。

对每个内部顶点 u，总流入量等于总流出量。视频通过遍历所有顶点求和来定义这两个总量，并指出只有源点和汇点才可能产生或吸收净流。

1. 该等式仅对内部顶点 u 提出要求。

2. 流入量与流出量均通过对所有 $v \in V$ 求和来定义。

1. 源点、汇点与内部顶点
2. 流函数及其成对约束

1. 公式
   观察依据

   黑板上写着：流值 |f| = f^{out}(s) = f^{in}(t)。

2. 声音
   观察依据

   讲师指出，流的整体值等于从源点流出的流量，也等于流入汇点的流量。

流的值定义为离开源点的流量，也等价于进入汇点的流量。此处使用了先前定义的出流函数与入流函数。

1. s 是源点。

2. t 是汇点。

3. 该定义依赖于此前对 f^{out} 和 f^{in} 的定义。

1. 内部顶点处的流守恒

1. 声音
   观察依据

   讲师指出，禁止反平行边是为了简化部分方程，且这一限制并非严重缺陷。

施加限制：若 (u,v) ∈ E，则 (v,u) ∉ E；此举旨在简化后续方程，并被表述为并非严重限制。

1. 我们正在定义本讲所使用的流网络类别。

针对本节所考虑的流网络。

1. 声音
   观察依据

   主讲人指出，容量被假定为非负整数，这使得论证更简便，且并非严重限制，因为后续算法将克服这一假设。

假设容量为非负整数可简化论证，且并非严重限制，因为后续算法将克服这一假设。

1. 在本次讲解中，容量取自 $\mathbb{N} \cup$ \{0\}。

针对本课程后续讨论的算法，依据主讲人的说法。

1. 声音
   观察依据

   主讲人直观解释道：这意味着内部节点既不能产生也不能吸收流动的‘物质’；这些任务仅由源点和汇点承担。

内部顶点处的流量守恒意味着内部节点既不能产生也不能吸收流量；只有源点和汇点承担该角色。

1. 守恒条件 f^{in}(u)=f^{out}(u) 对所有内部顶点 u 成立。

对每一个内部顶点 u。

1. 声音
   观察依据

   主讲人说：‘例如，在这个节点处，有四加二流入，五加一流出。两者均为六，因此我们称该顶点处流量守恒。’

2. 图示
   观察依据

   笔尖指向例题图中的一个内部顶点，同时讲解流入与流出的量。

1. 所指内部顶点的确切身份在视觉上仅为近似，但口述的算术运算清晰明确。

1. 公式

   $$4+2$$
   解释

   主讲人将选定内部顶点处的两个流入流量相加。

   步骤依据

   音频中直接陈述。

   视频直接表达
2. 公式

   $$5+1$$
   解释

   主讲人将同一顶点处的两个流出流量相加。

   步骤依据

   音频中直接陈述。

   视频直接表达
3. 公式

   $$6=6$$
   解释

   两个总和均等于6，因此该顶点满足守恒律。

   步骤依据

   对两个和进行算术比较。

   视频直接表达

在所引述的内部顶点处，流入流量等于流出流量，因此该处流量守恒。

1. 图示
   观察依据

   展示了一个含六个顶点的有向图，源点 s 位于左侧，汇点 t 位于右侧。

2. 公式
   观察依据

   红色边标签表示容量，蓝色标签表示流量，包括若干对形式如$5/8$、$6/6$、$7/10$、$4/7$、$1/2$、$2/9$、$3/5$、$5/6$以及$2/2$的标注。

3. 声音
   观察依据

   主讲人利用该图讲解容量、流量以及内部顶点处的守恒律。

1. 某些边与标签的对应关系在视觉上仅为近似，因为图板是手写的，且书写速度较快。

通过一个包含源点 s 和汇点 t 的具体有向图，阐释容量、流量与守恒律的定义。

1. 一个包含顶点 s 和 t 的有向图。

2. 边上用红色标注的容量值。

3. 边上用蓝色标注的流量值。

4. 其中一个内部顶点已验证：其入边流量分别为4和2，出边流量分别为5和1。

展示图中所显示的数字如何体现容量 C、流量 f 及守恒律的定义。

1. 公式

   $$C(u,v) \text{ shown as red edge labels}$$
   解释

   图中红色数字表示对应有向边的容量。

   步骤依据

   图示，外加主讲人对容量的定义。

   视频直接表达
2. 公式

   $$f(u,v) \text{ shown as blue edge labels}$$
   解释

   蓝色数字表示分配给每条有向边的实际流量。

   步骤依据

   图示，外加主讲人对流量的定义。

   视频直接表达
3. 公式

   $$4+2 = 5+1 = 6$$
   解释

   在所提及的内部顶点处，总流入量等于总流出量。

   步骤依据

   明确口述的数值验证。

   视频直接表达

该示例图通过为边赋予整数容量及非负流量，实例化了一个流网络，这些容量与流量满足前述约束条件，并在所提及的内部顶点处验证了守恒性。

讲师通过比较流入量之和与流出量之和，在一个内部顶点处进行了数值化的守恒性验证。

1. 图示
   观察依据

   黑板标题为“流网络”，右侧画有一个小型有向图，左侧写着公式 $G = (V, E)$；(u,v) $\in E \Rightarrow (v,u) \notin E$。

2. 动画
   观察依据

   一只手握着触控笔，一边指向公式与图示，一边由讲师引出定义。

1. 标题“流网络”

2. $G=(V,E)$ 的公式

3. 含六个顶点的小型有向图

1. 触控笔先指向公式，再指向图示。

1. 该图保持有向性。

2. 反平行边限制在图中持续可见。

开场画面表明，流网络构建于一个不含反平行边的有向图之上。

1. 图示
   观察依据

   绿色文字出现：“源点”s、“汇点”t、“内部点”，以及对所有$v\in V$，(v,s),(t,v)∉E。

2. 动画
   观察依据

   图中最左侧和最右侧的节点分别标记为s和t。

1. 图的顶点

2. 标签s和t

3. 绿色边界条件公式

1. 最左侧节点被标记为s。

2. 最右侧节点被标记为t。

3. 边界条件文字被添加在初始定义下方。

1. 底层有向图结构保持不变。

2. 无反向平行边条件仍然生效。

图示步骤区分了两个特殊顶点，并编码了‘没有边进入 s，也没有边离开 t’这一假设。

1. 图示
   观察依据

   红色数字出现在图的有向边旁。

2. 公式
   观察依据

   板书添加了容量函数 C : $V \times V$ → ℕ ∪ {0}，且当 (u,v) ∉ E 时，$C(u,v) = 0$。

1. 每个红色数字到特定有序对的精确映射在视觉上仅为近似。

1. 有向图

2. 红色数字边标签

3. 容量公式

1. 红色容量值被写在边上。

2. 容量函数定义被添加在左侧。

1. 图的拓扑结构及源点/汇点标签保持不变。

红色标签用于在选定的顶点对上可视化容量函数 C。

1. 图示
   观察依据

   蓝色数字添加在红色标签旁，形成成对标签，例如 $5/8$、$6/6$、$7/10$、$4/7$、$1/2$、$2/9$、$3/5$、$5/6$ 和 $2/2$。

2. 公式
   观察依据

   图板添加流函数 f : $V \times V$ → [0,$\infty$)，并附带约束条件：1) $f(u,v) \le C(u,v)$，2) $f(u,v)+f(v,u)=0$，以及后续的守恒公式。

1. 部分成对标签为手写，其与具体边的对应关系仅为近似。

1. 图的边

2. 蓝色流标签

3. 流的定义公式

4. 守恒公式

1. 蓝色流值与红色容量值并排书写。

2. 流函数的定义及其约束条件被添加。

3. 守恒方程书写在下方。

1. 容量标签保持可见。

2. 源点和汇点标签保持固定。

成对的红色/蓝色标签展示了一个具体的容量与流量分配，满足所陈述的约束条件。

1. 图示
   观察依据

   右下角出现一个带方框的标题“流量值”，其公式为〔|f|〕 = 〔f^{out}(s)〕 = 〔f^{in}(t)〕。

2. 动画
   观察依据

   手写笔指向该带方框的公式，讲师借此定义整个流量的总体值。

1. 带方框的标题“流量值”

2. 公式〔|f|〕 = 〔f^{out}(s)〕 = 〔f^{in}(t)〕

1. 右下角新增一个带方框的定义。

1. 先前的图示与定义仍保留在屏幕上。

结束画面总结了与整个流量相关联的标量数量。

1. 声音
   观察依据

   讲师指出，从一个顶点向另一个顶点发送流量，又立即将其送回，这是没有意义的。

2. 公式
   观察依据

   黑板上写着 $f(u,v)+f(v,u)=0$。

有人可能设想在同一对顶点之间双向发送正向流量。

视频中规定 $f(u,v)+f(v,u)=0$，因此至少一个方向的流量必须为零；反向同时存在正向流量的情形被排除。

1. 声音
   观察依据

   讲师指出，中间节点不能产生或吸收任何流动的量；产生和吸收的任务由源点与汇点承担。

读者可能误以为中间顶点可以增加或减少流量。

守恒性要求在中间顶点 u 处满足 f^{in}(u)=f^{out}(u)，因此只有源点 s 和汇点 t 才负责净产生或净吸收。

1. 公式
   观察依据

   源点/汇点标记直接加在初始图定义的下方。

2. 声音
   观察依据

   讲师首先定义有向图，再从中区分出特殊顶点 s 和 t。

流网络的定义是在有向图基础上，额外指定源点与汇点顶点，并对关联边施加边界条件。

1. 公式
   观察依据

   守恒条款写在源点/汇点/中间顶点区分之后，表述为‘对中间顶点 u’。

2. 声音
   观察依据

   主讲人指出，每个内部顶点处的流量必须守恒，并随后将内部节点与源点和汇点进行对比。

理解守恒性需要明确哪些顶点是内部顶点，哪些是源点和汇点。

1. 公式
   观察依据

   流量约束 $f(u,v) \le C(u,v)$ 直接引用了容量函数。

2. 声音
   观察依据

   主讲人指出，对于任意一对顶点，流量均不可超过其容量。

流量的定义依赖于容量，因为其中一条约束是以 $C(u,v)$ 为上界的限制条件。

1. 公式
   观察依据

   最终框出的公式 |f| = f^{out}(s) = f^{in}(t) 使用了先前定义的 f^{out} 和 f^{in}。

2. 声音
   观察依据

   主讲人使用源点的出流量和汇点的入流量来定义流量的整体值。

流量值这一概念，是将入流量/出流量的机制应用于特殊顶点 s 和 t。

1. 公式
   观察依据

   开场板书显示 $G = (V, E)$；若 (u,v) ∈ E，则 (v,u) ∉ E。

2. 声音
   观察依据

   主讲人从流网络的定义开始讲解。

1. 流网络是一种不含反平行边的有向图

1. 声音
   观察依据

   主讲人指出，为简化部分方程，不允许存在反平行边。

1. 流网络是一种不含反平行边的有向图
2. 禁止反平行边是一种简化假设。

1. 公式
   观察依据

   黑板上标出源点 s、汇点 t 和内部顶点，并写出边界条件。

2. 声音
   观察依据

   讲师说明了流的起点和终点。

1. 源点、汇点与内部顶点

1. 公式
   观察依据

   黑板上写出：若 (u,v) ∉ E，则 $C(u,v) = 0$。

2. 声音
   观察依据

   讲师指出，若图中不存在该边，则其容量定义为零。

1. 定义在顶点对上的容量函数

1. 公式
   观察依据

   黑板上列出：$f(u,v) \le C(u,v)$，且 $f(u,v) + f(v,u) = 0$。

2. 声音
   观察依据

   讲师陈述了非负性、容量约束和单向为零这三项要求。

1. 流函数及其成对约束

1. 声音
   观察依据

   讲师给出 $4+2$ 与 $5+1$ 的例子，并指出内部节点既不能产生流，也不能吸收流。

1. 内部顶点处的流守恒
2. 对内部顶点处守恒律的数值验证
3. 中间顶点既不产生也不销毁流量。

1. 公式
   观察依据

   方框中的公式为 |f| = f^{out}(s) = f^{in}(t)。

2. 声音
   观察依据

   主讲人定义了流的整体值。

1. 流的值