通信网理论基础3通信网络设计基础3

3.4流量分配网的作用:业务流从源端送至宿端.网络利用原则:充分利用各种资源(线路,转接设备等),合理分配流量,总的流量尽可能大,传输代价尽可能小流量分配:网络运行的重要指标之一限制因素:网络的拓扑结构,边和端的容量流量:传信率(如电话路数,数据比特率等)3.4.1流量优化的一般性问题3.4.2最佳流问题2004-08-1513.4.1一概念.1网络:2004-08-1523.4.1一概念.22004-08-1533.4.2一概念.3单源单宿网络:2004-08-1543.4.1一概念.4流的概念:2004-08-1553.4.1一概念.5可行流(flow):2004-08-1563.4.1一概念.62004-08-1573.4.1一概念.7流的和:2004-08-1583.4.1一概念.8例2004-08-1593.4.1一概念.9最大流:2004-08-15103.4.1一概念.10割:割是分离源和宿的边的集合2004-08-15113.4.1一概念.112004-08-15123.4.1一概念.12割与割集的区别都是边的集合，但割:有向图割集:无向图2004-08-15133.4.1一概念.13定理2004-08-15143.4.1一概念.14证明2004-08-15153.4.1一概念.15或表示为:由于:有:其中:所以:2004-08-15163.4.1一概念.16意义:2004-08-15173.4.1一概念.17推论证明2004-08-15183.4.1一概念.18最小割最小割定理割的方向从源到宿前向边在图的割集中,与割方向一致的边2004-08-15193.4.1一概念.19在图的割集中,与割方向相反的边反向边饱和边非饱和边零流量边路注2004-08-15203.4.1一概念.20可增广路与不可增广路2004-08-15213.4.1一概念.21路中所有前向边都为非饱和边所有后向边都是非零流量的为可增广路2004-08-15223.4.1一概念.22所有前向边+1后向边-1可行流增加了1，变为62004-08-15233.4.1一概念.20可增广路中增量的确定方法2004-08-15243.4.1一概念.21可增广路例子2004-08-15253.4.1二流量优化.1最大流最小割定理在任何网络中,最大流的值等于最小割的容量,即证明2004-08-15263.4.1二流量优化.22004-08-15273.4.1二流量优化.32004-08-15283.4.1二流量优化.42004-08-15293.4.1二流量优化.52004-08-15303.4.1二流量优化.6寻找最大流的方法：标记法2004-08-15313.4.1二流量优化.6标记法步骤.22004-08-15323.4.1二流量优化.7标记法步骤.3B.增广过程2004-08-15333.4.1二流量优化.8标记法例题.1例题：求下列网络的最大流A.标记过程解：2004-08-15343.4.1二流量优化.9标记法例题.22004-08-15353.4.1二流量优化.10标记法例题.32004-08-15363.4.1二流量优化.11标记法例题.4任选已标记未检查的顶点2004-08-15373.4.1二流量优化.12标记法例题.52004-08-15383.4.1二流量优化.13标记法例题.62004-08-16393.4.1二流量优化.14标记法例题.72004-08-16403.4.1二流量优化.15标记法例题.8任选已标记未检查的顶点2004-08-16413.4.1二流量优化.16标记法例题.92004-08-16423.4.1二流量优化.17标记法例题.10计算各关联点的标记参数2004-08-16433.4.1二流量优化.18标记法例题.11标记2004-08-15443.4.1二流量优化.19标记法例题.12已标记已检查的顶点2004-08-16453.4.1二流量优化.20标记法例题.13新一轮计算任选已标记未检查的顶点2004-08-16463.4.1二流量优化.21标记法例题.142004-08-16473.4.1二流量优化.22标记法例题.15计算各关联点的标记参数2004-08-16483.4.1二流量优化.23标记法例题.16标记2004-08-16493.4.1二流量优化.24标记法例题.17已标记已检查的顶点2004-08-16503.4.1二流量优化.25标记法例题.182004-08-16513.4.1二流量优化.26标记法例题.19B.增广过程选一可增广路2004-08-16523.4.1二流量优化.27标记法例题.20选到的可增广路2004-08-15533.4.1二流量优化.28标记法例题.21增广过程步骤2004-08-16543.4.1二流量优化.29标记法例题.22增广过程的本质:从宿回溯到源,根据回溯历经的各顶点的标记决定各边的流增加值2004-08-16553.4.1二流量优化.30标记法例题.23可增广路中边的流值更改方法2004-08-16563.4.1二流量优化.31标记法例题.242004-08-15573.4.1二流量优化.32标记法例题.252004-08-16583.4.1二流量优化.33标记法例题.262004-08-16593.4.1