4.2 最大流最小割定理

文档摘要

4.2 最大流最小割定理 4.2 最大流最小割定理：水流与瓶颈的奇妙邂逅想象一下，你是一个水利工程师，负责规划城市供水系统。水源地就像图中的“源点”，城市用水户就像“汇点”。水管就像图中的“边”，每根水管都有一个“容量”，代表它单位时间内能通过的最大水量。你的目标是：如何让水源地尽可能多地向城市输送水，这就是最大流问题！但是，总有一些地方的水管比较细，限制了整体的输水能力。这些“瓶颈”就是我们接下来要讨论的最小割。而最大流最小割定理，就像一座桥梁，将这两个概念紧密地联系在一起。 4.2.1 什么是割（Cut）？首先，我们需要明确“割”的概念。在一个网络流图中，一个割是将图中的所有顶点分成两个互不相交的集合S和T，其中源点s属于集合S，汇点t属于集合T。