图论算法：流量网络与伴随网络详解-ACM/ICPC竞赛实用教程

"《图论算法理论、实现及应用》是一本详细介绍图论基础及其在计算机科学中广泛应用的教材。该书由王桂平、王衍和任嘉辰编著，适合计算机及相关专业学生以及ACM/ICPC竞赛的参与者使用。全书共10章，首先从第一章的图论基本概念和邻接矩阵、邻接表两种存储表示方法开始，逐步深入探讨图的遍历、活动网络、树与生成树、最短路径、可行遍性、网络流问题、点与边的支配集、覆盖集、独立集、图的连通性、平面图和着色问题等核心概念。 图论的核心在于研究图，即由顶点和边组成的抽象结构，它可以用来刻画现实世界中的复杂关系。书中以经典的ACM/ICPC竞赛题目为例，展示图论算法的思维和应用技巧。作者强调了图论算法的实际编程实现，不仅教授理论知识，还提供了实践操作的指导，帮助读者理解和掌握这些关键算法。 在图6.32的例子中，涉及有上下界的流量网络，即在网络中每个弧都有其容量限制和流量上限。通过构建伴随网络，如图6.32(b)，可以分析网络的流量特性。在伴随网络中，添加的弧容量反映了原网络中缺失的连接，例如源点Vs和汇点Vt处的弧由于原网络中不存在，其容量设为0。通过求解伴随网络的大流，可以推断原网络是否存在可行流，如图6.33所示，其中sV流出的所有弧都达到了最大容量，表明原网络存在可行流，其流量为5。在原网络G的可行流图6.34(a)中，弧的流量用下界b(e)、上界c(e)和实际流量f(e)三个值表示，这展示了如何利用图论技术来量化和优化网络中的流量分配。 这本书不仅是理论学习的宝典，也是提高竞赛成绩和解决实际问题的实用工具，为学生和研究人员提供了丰富的图论知识体系，帮助他们理解和应用这一强大的数学工具。无论是理论研究还是工程实践，这本书都是不可或缺的参考资料。"