第4章：网络规划

第四章：网络规划4.1图一、起源

1736年瑞士数学家欧拉（E.Euler）在求解七桥一笔画难题时，就用了点线图来分析论证：每个点均有奇数条边时，一笔画问题无解。ACBDCDAB(前苏)哥尼斯堡城中的普雷格尔河1二、图的概念

图由代表所研究对象的点和表示对象之间关联性质的线构成，一般称为点线图。上面表示的图就是点线图，其中（a）图的线不带表示关联方向的箭头，一般称为边，这样的图称为无向图；（b）图的带有表示关联方向的箭头，一般称为弧，这样的图称有向图。记为G={V,E}，其中点集和线集分别表示为

V={v1,v2,…,vn},vj

也称为顶点、端点或节点；E={e1,e2,…,em},ei可以是边，也可以是弧。

V1V2V3V4V5V6V7V8V1V2V4V3V5V6V7V8V9e1e2e3e4e5e6e7e8e9e10e11e13e122

1、点：以无向图为例点的次数（度数）：与点vi关联的边数称为的次数（度数），记为d(vi)。如：d(v1)=5，称顶点v1的次数为5，或称v1为5度关联。奇点：次数（度数）为奇数的点叫奇点。如：v1,v2等均是奇点。偶点：次数（度数）为偶数的点叫偶点。如v7,v8等均是偶点。悬挂点：次数（度数）为1的点叫悬挂点。如：v4,v5均是悬挂点。孤立点：次数（度数）为0的点叫孤立点。即与任何边都没有关联的顶点。如v9为孤立点。

2、边：以无向图为例可用{vi,vj}表示。多重边：关联于两个相邻顶点的边称为多重边。如：e11与e13称为多重边。环：两端点接于同一顶点的边称为环。如：e12称为环。悬挂边：与悬挂点关联的边叫悬挂边。如e3,e7均是悬挂边。V1V2V4V3V5V6V7V8V9e1e2e3e4e5e6e7e8e9e10e11e13e123三、链和路

1、链：从某点开始的点边交替序列称为链。如上图中的{v4,e3,v2,e1,v1,e4,v3,e2,v2,e1,v1,e6,v6,e8,v7}称为一条链。

圈：首尾相连的链叫圈。

2、路：无重复点和无重复边的链叫做路。如上图中的{v4,e3,v2,e1,v1,e4,v3,e5,v6,e9,v8}称为一条路。回路：首尾相连的路叫回路。如上图中的{v1,e4,v3,e5,v6,e6,v1}称为一回路。V1V2V4V3V5V6V7V8V9e1e2e3e4e5e6e7e8e9e10e11e13e12以上点边序列中的边表示为e={vi,vj},所以点边序列可由点列确定。如上面的回路可写为{v1,v3,v6,v1}。在有向图中，弧区分为正向弧和反向弧，其链和路的概念与无向图相似，点弧序列中弧也有正向弧和反向弧之分。四、连通图：

任意两点之间可由一条链连接起来相通的图叫连通图。否则，称为非连通图。如：上图就不是连通图，因为点V9与任何点之间均没有链连接起来相通。

4五、子图和部分图：设G1={V1，E1}，G2={V2，E2}，G={V，E}1、子图：若V2V1，E2

E1，则称G2是G1的一个子图。真子图：若V2V1，E2

E1，则称G2是G1的一个真子图。

2、部分图：若V2=V1，E2

E1，则称G2是G1的一个部分图，即包含原图全部顶点的子图。

3、零图：若E=ф，则称G为零图，即由许多孤立点构成的图。

4、空图：若V=ф和E=ф

，则称G为空图。六、同形图：两个图，从外表上看不一致，但它们保持了各自代表的对象间相同的关联性质，称为同形图，如下面两个图就是同形图。

结论：图的顶点可以任意挪动位置，而边是完全弹性的，只要在不拉断的条件下，可从一个形状的图变形为另一个形状的图，且关联性质不变。

V1V2V3V4V5e1e2e3e4e5e6e7V1V2V3V4V5e1e2e3e4e5e6e754.2树一、树的概念

一个无圈的连通图称为树。

如：在有线通讯网和交通网中，在保证节点连通的条件下，边数最少（可以节省材料和投资）的线路图必然是树，如下图所示

：v1v2v3v4v5v6v1v2v3v4v5v6边为树枝，次为1的顶点为树叶。一些行政管理机构和军队的建制也常用树来表示相互隶属关系；图书分类、会计科目、决策过程等等也都可以画成树图。

二、树的性质

①、任何树必有树叶(即次数为1的节点)。

②、树中任意两点之间有且仅有一条链连接相通。任意去掉一条树枝，该树就被分割成两互不连通的子图。

③、一连通图可能具有很多树，这些树都是原连通图的部分图，即包括了原连通图的所有顶点。6三、图的部分树若图G={V,E}的部分图T={V,E’}是树，则T称为图G的一个部分树。即：连接图全部顶点的最小边数的部分图。定理1：图G是连通的充分必要条件为

图G有部分树。v1v2v3v4v5v6v1v2v3v4v5v6v1v2v3v4v5v67四、赋权无向图的最小部分树1、最小部分树定义：权数之和(数量指标之和)为最小的部分树叫最小部分树。

v1v2v3v4v5v6132873566v1v2v3v4v5v613736∑ei

=1+3+3+7+6=20v1v2v3v4v5v612536∑ei

=1+2+3+5+6=172、最小部分树定理：若T*是图G的一棵树，则

T*是最小树充分必要条件为对T*外的每条边(vi,vj)，其权wij≥max{wii1，wi1i2，，wikj}

其中：{vi,vi1,,vj}是T*内连接点vi和vj的唯一的链。883、最小部分树求法①避圈法：将连通图所有边按权从小到大排序，每步从未选的边中选一条权最小的边逐条衔接，但不能成圈。②破圈法：在连通图中任取一圈，去掉一条权数最大的边，在余下的图中重复以上步骤，直至无圈为止。例：某工厂内联结六个车间的道路网如下图示，巳知每条道路的长度，要求沿道路架设联结六个车间的电话网，使电话线总长度最短?v1v2v3v4v5v6132873566v1v2v3v4v5v612356∑ei

=1+2+3+5+6=17v1v2v3v4v5v6132873566∑ei

=1+2+3+5+6=1794.3网络最短路线问题一、最短路线问题的概念

v1v2v3v5v6v7v4718234312274二、原理：Be1lman优化原理。在网络图中的表述如下：若{V1，V2，，Vn}是从V1到

Vn的最短路径，Vk

是其中任一点，则

{V1，V2，，Vk}也是从V1到

Vk的最短路径。

v1vkvn10三、最短路线求法

T,P标号算法：1959年狄克斯特拉E.W.Dijkstra提出，仅适用于所有弧权dij≥0的网络图。用指标函数迭代逐步正向搜索，直至指标函数衰减稳定为止。

T(Vj)k=min{T(Vj)k-1，P(Vi)+dij}

其中：T---为临时或试探性标号，表示V1到Vj的估计最短距离，后要改为P标号。

(所有求出的T标号中，选最优者改为P标号)P---为永久性标号，表示V1到Vj的最短距离

T(Vj)k

表示第k步从V1到Vj的估计最短距离；

P(Vi)表示从V1到Vi的最短距离；

dij

表示从Vi到Vj的实际距离。例1：求下列网络中，从V1到V7的最短路径及最短路径距离。v1v2v3v5v6v7v471823431227411解：⑴先用T,P标号法求从V1到各点Vj的最短距离：T(Vj)k=min{T(Vj)k-1，P(Vi)+dij}

第一步：T(Vj)=，(j=1,…,7)，v7v1v2v3v5v6v47182343122740144579第二步：从V1可达V2、V3，修改其T标号，将已求出的所有T标号中的最优者改为P标号。

T(V2)①=min{T(V2)，P(V1)+d12}=min{，0+7}=7

T(V3)①=min{T(V3)，P(V1)+d13}=min{，0+1}=1第三步：从V3可达V2、V4、V6，修改其T标号，将已求出的所有T标号中的最优者改为P标号。

T(V2)②=min{T(V2)①，P(V3)+d32}=min{7，1+3}=4

T(V4)①=min{T(V4)，P(V3)+d34}=min{，1+4}=5

T(V6)①=min{T(V6)，P(V3)+d36}=min{，1+3}=4第四步：A.从V2可达V4、V5，修改其T标号。

T(V4)②=min{T(V4)①，P(V2)+d24}=min{5，4+2}=5

T(V5)①=min{T(V5)，P(V2)+d25}=min{，4+8}=12

B.从V6可达V4、V7，修改其T标号，将已求出的所有T标号中的最优者改为P标号。

T(V4)③=min{T(V4)②，P(V6)+d64}=min{5，4+4}=5

T(V7)①=min{T(V7)，P(V6)+d67}=min{，4+7}=11第五步：从V4可达V7，修改其T标号，将已求出的所有T标号中的最优者改为P标号。

T(V7)②=min{T(V7)①，P(V4)+d47}=min{11，5+2}=7第六步：从V7可达V5，修改其T标号，将已求出的所有T标号中的最优者改为P标号。

T(V5)②=min{T(V5)①，P(V7)+d75}=min{12，7+2}=9P(V1)=0①=P(V3)②=P(V6)③=P(V2)③=P(V4)④=P(V7)⑤=P(V5)⑥12

⑵用反向跟踪法求最短路径：设Vj的紧前点为Vk，则P(Vk)=

P(Vj)-dkj

第一步：求V7的紧前点为Vk：P(Vk)=

P(V7)-dk7=7-{d47,d67}

=7-{2,7}={5,0}={P(V4),P(V6)}=P(V4)v7v1v2v3v5v6v47182343122740144579第二步：求V4的紧前点为Vk：P(Vk)=

P(V4)-dk4=5-{d54,d24,d34,d64}

=5-{1,2,4,4}={4,3,1,1}={P(V5),P(V2),P(V3),P(V6)}=P(V3)第三步：求V3的紧前点为Vk：P(Vk)=

P(V3)-dk3=1-d13=1-1=0=P(V1)

故所求的最短路为：V1V3V4V7142

所求的最短路距离为：1+4+2=7134.4网络最大流问题一、问题的提出

交通网络中要研究车辆的最大通过能力；生产流水线网络上产品的最大加工能力；供水网络中通过的最大水流量；信息网中信息最大传送能力等等。弧容量cij：网络的组成弧都具有确定的通过能力(有时称为硬件能力)；弧流量fij：实际通过弧的流量(有时称为软件能力)；

研究的问题：因各弧容量的配置关系不调，有些流量常常达不到容量值。因此，研究实际能通过网络的最大流量问题，可以评估网络的最大运载能力，明确为使最大流量增大应如何改造网络。v1v2v3v5v6v470100904070904080100,50,50,60,50,40,90,50,80,30源点汇点14二、基本概念

1、容量网络：标有弧容量cij的网络叫容量网络。

2、网络流：容量网络中，实际通过各弧的流量集F={fij}称为网络流。由于各弧容量的配置可能不协调，实际通过各弧的流量fij不可能处处都达到容量值cij。

3、可行流：对给定的容量网络，在满足下列两个条件①、②的网络流称为可行流：

①容量约束条件：0≤fij≤cij。即0≤f12≤70，0≤f13≤100，0≤f14≤90，0≤f26≤80，0≤f34≤40，

0≤f35≤70，0≤f45≤40，0≤f46≤100，0≤f56≤90。

②节点流量平衡条件：每个节点的流入总量等于流出总量。V1:Q=f12+f13+f14；V2:f12=f26

；V3:f13=f34+f35V4:f14+f34=f45+f46；V5:f35+f45=f56；V6:f26+f46+f56=Q。可行流总存在，如零流{fij=0}就是一个可行流,即容量网络没有给出流量fij时,就认为fij=0。

4、最大流：使得从网络源点（或称发点）到汇点（或称收点）的总流量Q达到最大的可行流F={fij}

称为最大流。v1v2v3v5v6v470100904070904080100,50,50,60,50,40,90,50,80,30源点汇点C12C26C13C14C34C46C45C56C35,f12,f26,f14,f13,f34,f46,f45,f35,f5615三、增广链

给出网络{cij,fij}，其中{fij}为可行流，fij

v1v2v3v4v5v6354112352,3,3,3,1,1,1,1,2,0v1v2v3v4v65415,3,3,1,1

1、增广链定义：一条从起点到终点的链，且正向弧必是非饱和弧，反向弧必是非零弧。即：正向饱和弧和反向零弧均不入链。正向非饱和弧充许增大流量，反向非零弧，充许减小流量（维持节点量平衡）。如链：L={v1,v3,v2,v4,v6}为一条增广链。其中：正向弧集L+={(v1,v3),(v2,v4),(v4,v6)}均为非饱和弧。反向弧集L-={(v3,v2)}为非零弧。在增广链上存在增大输送能力的潜力。

2、增广链作用：网络可行流为网络最大流的判别方法。检查该可行流中是否存在增广链，若不存在，则当前可行流为最大流；否则，当前可行流为非最大流，总流量还可增大。注：网络流非最大时，往往存在多条增广链。16四、最小割v1v2v3v4v5v6354112352

1、割集概念的引入：一个容量网络，由于各弧容量Cij配置得不合适，结果有的地方能通过较大流量，而有的地方能通过的流量较量却较小。小的地方就限制了最大流的上限值，称为网络流的“瓶颈”（或俗称“卡脖子”地区）。因此,研究从起点到终点的流径中，哪些弧容量起了限制最大流作用，而割集就是研究网络流“瓶颈”的一种工具。

2、割集的定义：使连通图分成两个互不连通子图的弧的最小集合，记为S={(vI,,vj)}。

S1={(V1,V2),(V1,V3)}容量C1=3+5=8

S2={(V2,V4),(V3,V5)}

容量C2=4+2=6

S3={(V4,V6),(V3,V5)}

容量C3=5+2=7

S4={(V1,V2),(V3,V5)}容量C4=3+2=5

3、最小割集(最小割)的定义：所有割集中容量最小的割集，记为S(v*,v*)。实际流F的流量Q（F）≤C(v*,v*)。

4、最小割集与最大流定理：容量网络中，实际流F所能达到的最大流量Q(F*)等于该容量网络最小割的容量C(v*,v*)。

即：Q(F*)=C(v*,v*)17五、最大流与最小割求法---标号法

1、原理：从网络图的一可行流出发，用给顶点标号的方法找增广链。若找得到增广链,说明当前流非最大,则沿增广链方向增大可行流得新可行流，然后在新可行流中继续找增广链，直到在某个新可行流中找不到增广链时，这个新可行流就是最大流，同时也得到最小割。2、标号形式：(±vi,Δfij），其中Δfij=例1求下图容量网络中，从v1到v6的最大流和最小割。v1v2v3v4v5v6354112352第一步：给出一个初始可行流，应尽量接近最大流。（容量网络给出时，fij=0）一般原则：①、找出回路，给回路上各弧同一流量值，使回路上某些容量较小的弧优先达到饱和。

②、找出从起点到终点的路，给路上各弧同一流量值，使路上某些容量较小的弧优先达到饱和。v1v2v3v4v5v6354112352,1,1,1,3,3,3,1+1,118第二步：给顶点标号找增广链。①对起点v1标号(0，∞)。v1v2v3v4v5v6354112352,3,3,3,1,1,1,1,2,0(0，∞)②从v1可达v2，v3：(v1,v2)为正向饱和弧，不入链，v2不标号；

(v1,v3)为正向非饱和弧，入链，v3标(＋v1,4)。(+v1，4)③从v3可达v2，v5：(v3,v2)为反向非零弧，入链，v2标（－v3，1）

(v3,v5)为正向饱和弧，不入链，v5不标号。（-v3，1）④从v2可达v4，v5

：(v2,v4)为正向非饱和弧，入链，v4标(+v2,1)(v2,v5)为反向非零弧，入链，v5标(-v2,1)(+v2,1)(-v2,1)⑤从v4可达v6：(v4，v6)为正向非饱和弧，入链，v6标（+v4,2）。（+v4，2）从v5可达v6：(v5，v6)为正向非饱和弧,入链，v6标（+v5,1）。（+v5，1）故：当前可行流非最大流，沿增广链L1方向调整流量l(正向弧增加流量l，反向弧减少流量1)，其余弧流量不变，得一新可行流。+1-1+1+1v1v2v3v4v5v6354112352,3,4,4,2,1,0,1,2,0得一条增广链：L1={v1,v3,v2,v4,v6}得另一条增广链：L2=｛v1,v3,v2,v5,v6｝19第三步：给新可行流各顶点标号找增广链。①对起点v1标号(0，∞)。v1v2v3v4v5v6354112352,3,4,4,2,1,0,1,2,0(0，∞)(+v1，3)②从v1可达v2，v3：(v1,v2)为正向饱和弧，不入链，v2不标号；

(v1,v3)为正向非饱和弧，入链，v3标(＋v1,3)。③从v3可达v2，v5：(v3,v2)为反向零弧，不入链，v2不标号

(v3,v5)为正向饱和弧，不入链，v5不标号。标号过程中断，找不到增广链，当前可行流为最大流。第四步：确定最小割和最大流量。①最小割：将已标号的顶点v1、v3构成非空集v*={v1,v3}，未标号的其它顶点v2,v4,v5,v6构成补集

v*={v2,v4,v5,v6},形成最小割(将v*,v*分开)：Smin={(v1,v2),(v3,v5)},其容量为C(v*,v*)=3+2=5Smin={(v1,v2),(v3,v5)},其容量为C(v*,v*)=3+2=5②最大流量Ｑ(F*):根据最大流――最小割定理有Ｑ(F*)=C(v*,v*)=5注：最小割Smin所包含弧（v1,v2）,(v3,v5)为网络关键弧。若要增大网络最大流，必须首先设法改善这些关键弧的状况，提高它们容量；如果最小割中的弧通过能力一旦降低，则会使总流量减小。另外，在各弧容量一定的网络中，最大流的总流量是唯一的，最小割却不一定是唯一的。20ABCEDSFGHT30,2015,1520,520,2010,1020,2010,1010,510,1010,1020,