《有上下界的流量网络及其伴随网络》是一篇关于通信系统中的图论分析,特别是在网络流量管理和优化方面的核心内容。该主题由作者Haykin探讨,具体关注于图6.32所示的网络模型,其中网络具有特定的容量限制,并通过构建伴随网络来理解和分析流量特性。
图6.32(a)是一个具有上下界流量限制的网络,它的容量由每条弧上的两个数字表示,第一个数字代表弧的容量上限,第二个数字则表示流量的当前值。网络中存在源点Vs和汇点Vt,它们各自对应的弧容量可能为零,因为原网络中没有相应的出弧到Vt或入弧到Vs。
在图6.32(b)中,作者详细描述了如何构造伴随网络。伴随网络的目的是为了辅助理解原始网络的流量分布情况。在构建过程中,针对原网络中不存在的弧,如从Vt出发和到达Vs的弧,新加入的弧容量被设定为零。通过这种方式,可以简化问题并找到网络的最大流。
图6.33展示了在伴随网络中计算出的大流,所有附加源点sv流出的弧都达到其最大容量,表明原网络G确实存在可行流。这个可行流的流量大小为5,对应于图6.34(a)中的实际流量分配,每条弧的流量不仅标注了下界b(e)和上界c(e),还提供了实际流量f(e)的具体数值。
网络流问题是图论中的一个重要课题,它涉及到如何在满足容量限制的前提下,最大化或最小化流量的传输。通过这种方式,可以应用于诸如交通网络设计、通信网络调度等实际问题中,确保资源的有效利用。在《图论算法理论、实现及应用》这本书中,作者王桂平、王衍和任嘉辰深入讲解了图论基础、遍历、树与生成树、最短路径、可行流等问题,并且强调了图论在ACM/ICPC竞赛中的应用,将其作为计算机和相关专业图论课程的重要教材,同时也适用于竞赛训练。
图论的研究始于瑞士数学家欧拉对哥尼斯堡七桥问题的解决,这标志着图论作为一门学科的诞生。欧拉的方法将实际问题转化为图论模型,证明了该问题无解,并发展出了更一般化的“ Eulerian trail”概念,即无重复路径遍历所有边的条件。后续的图论研究逐渐扩展到更广泛的领域,如图的连通性、平面图和着色问题等,这些理论不仅在学术界受到重视,也在现实世界的诸多问题中发挥着关键作用。