第3章通信网结构第3节.pptVIP

§3 流量问题 ;一、一般问题 对G={V,E} (n,m) : Cij——边容量 fij——边流量 {fij}——一组流，可行流 F——源宿间{fij}的总流量 流满足二条件： a)非负有界：0≤fij≤Cij 边上，共有2m个条件 b)连续性: ;对端vi有： 式中 Γ（vi）={vj: ( vi, vj)∈E} 流入vi Γˊ(vi）={vj: ( vj, vi)∈E} 流出vi 有n个连续性条件 共有2m+n个限制条件 满足上述二限制条件的流称为可行流。可行流不止一个。（举例）;流量优化所研究的问题： a)?网络拓扑已定，cij已知，给定源vs与宿vt在二个限制条件下，求vs→vt的最大流量Fmax(2m+n-2个条件) （最大流量问题（源宿间）） b)?网络拓扑已定，cij已知，单位流量通过边( vi, vj) 所需的代价αij(代价系数)已知，给定流量F。寻求总代价中最小的可行流{fij}，其中 φ=∑αij?fij （最小代价流，或最佳流量分配问题） ▲若αij 与fij无关，即常数，φ为fij的线性函数，求φmin仍是线性规划问题 ▲若αij 是fij的函数，则φ与fij 为非线性关系，求解φmin 复杂; c)网络拓扑未定，给定端集V及端间流量 F1,F2,......,Fn ，要求以最小代价规划边集E ——更广泛的问题 ? 一般，a）、b)前二问题除线性规划外，还有一些图论算法，易于计算机编程。问题c)较为困难。 ;二、源宿间的最大流量 1.割量：设X是V的真子集，且vs∈X，vt∈ （X, ）表示使vs,vt分离的割集，方向vs→vt 其边分二类: 前向边：与割方向一致的边 反向边：与割方向相反的边 割量定义为前向边容量和 对可行流{fij}: f(X, )——表示前向边的流量（和）∑fij f( ,X)——表示反向边的流量 (和) ∑fji ;性质： 1)? F=f(X, )-f( ,X) 证： ; ; S: fs1+fs2+fs3 无 1: f14 fs1+f21 2: f21+f23 fs2 3: f3t fs3+f23+f53 ;2） 由1）及 非负;2.路与可增流路 ;例: ; 网处于最大流的情况下，每个割集的前向 流量均等于最大流量且总存在一个割集 , 其每条正向边都是饱和的，其割量在诸???中达 最小值，并等于最大流量。 ;3.最大流量最小割量定理 源宿端间的最大流量等于使源端与宿端分 离的割量最小值。 ;[证明]： ;于是必有:Fmax=f(X’, ’)-f( ’,X’) ;4.最大流的M算法 基本思想：在一个可行流的基础上，找vs→vt 的可增流路，找到则在此路上增流，直至无可 增流路，停止。 ;方法：可从任一可行流开始，通常以{ fij=0}开始。 ▲标志过程：从vs 始加标志符 加上标志符的端称已标端 ▲选查过程：从vs 始选查已标未查端 查某端——即标其可能增流的邻端（未足或倒流），所有邻端已标，则该端已查。 标志宿端，则找出一条可增流路，进入增流过程。 ▲增流过程：在已找到的可增流路上增流 步骤如下：;M0：初始令fij=0 M1：标源端vs ：（+,s,∞） M2：从vs 始，查已标未查端vi ，即标vi 的满足 下列条件的邻端vj 若（vi vj ）∈E，且cij fij ，则标vj (+,i,εj) 其中εj =min(cij-fij ,εi ) εi 为vi 已标值 若（vj vi ）∈E，且 fji 0, 则标vj (-,i,εj) 其中εj =min（εi ，fji ） 其它vj 不标。 所有能加标的邻端vj 已标，则vi已查。倘若所有端已查且宿端未标，则算法终止。 M3：若宿端vt已标，则沿该路增流。 M4: 返回M1。;例: ;初始令fij =0 标源端vs ：（+,s,∞）查该端，即标邻端