7.2 最小割

文档摘要

7.2 最小割图论的璀璨明珠：网络流与匹配之最小割在图论的浩瀚星空中，网络流与匹配问题犹如两颗璀璨的明珠，散发着迷人的光芒。而在这片领域中，最小割问题又如同一颗隐藏的宝石，蕴含着深刻的理论价值和广泛的应用前景。今天，就让我们一起揭开最小割的神秘面纱，探索其背后的奥秘。 7.2 最小割：连接与分离的艺术 7.2.1 引子：桥梁与瓶颈想象一下，一个城市由复杂的道路网络连接，物资需要从城市的供应中心（源点）运送到需求中心（汇点）。每条道路都有其运输容量的限制，就像一条河流的流量上限。现在，如果我们要破坏这个网络的运输能力，最有效的方法是什么？或许你会想到炸毁几座关键的桥梁，或者阻塞几条重要的道路。在图论中，这些“桥梁”和“道路”的集合就构成了一个割。