<4D F736F F F696E74202D FCDF8C2E7CDD8C6CBBDE1B9B9B7D6CEF6>

Size: px

Start display at page:

Download "<4D F736F F F696E74202D FCDF8C2E7CDD8C6CBBDE1B9B9B7D6CEF6>"

君百霞强
5 years ago
Views:

1 第五章网络拓扑结构分析

2 网络拓扑结构分析是很基本也是很重要的问题拓扑结构是通信网规划和设计的第一层次问题通信网的拓扑结构可以用图论的模型来代表本章分析的主要问题为最小支撑树最短路径和网络流量安排等问题

3 5.1 图论基础图的定义和基本概念图论是应用数学的一个分支有着丰富的内容本节介绍它的一些概念和结论例 5.1 欧拉 Euler 7 桥问题电网络分析问题

4 图的定义定义 5.1 所谓一个图 G 是指给了一个端点集合 V 以及边的集合或 V 中元素的序对集合 E 图一般用 G = V E 来表示如果图 G 有 n 端 m 条边可将 V 和 E 表示为 V = v v... v } E = { e1 e2... em} { 1 2 n v 某边的端为 v 称这边和端 v v 关联这个边也可记为 : v v 或 e

5 一些概念无向图有向图空图孤立点图自环重边一个不含自环和重边的图称为简单图以后如果没有特别声明主要讨论简单图

6 对无向图的端 v 与该端关联边的数目为该端的度数记为 : d v 性质 5.1 对无向图 G = V E 如果 V = n E = m n 有 d v = 2m = 1

7 子图给定图 G = V E 若 V1 V E1 = { u v E u v V1} 称图 G1 = V1 E1 是 G 中由 V1 生成的子图记为 G [ V 1 ] 若 E2 E1 称 G 为 G 的子 2 = V1 E2 图特别若子图的端点集合为 V 这个图被称为图 G 的支撑子图若 E 1 E V1 = { v V v 是 E1中某边的端点 } 称图 G1 = V1 E1 是 G 中由 E1 生成的子图记为 G[ E 1 ]

8 图的连通性考虑边的一个序列相邻二边有公共端如 v 1 v 2 v 2 v 3 v 3 v 4 v v +1 这个边序列称为链链简单说就是一个连续轨迹没有重复边的链称为简单链 ; 没有重复端的链称为初等链或道路 ; 若链的起点与终点重合称之为圈 ; 若道路的起点与终点重合称之为初等圈一般重点讨论道路和初等圈

9 连通图任何二端间至少存在一条链的图为连通图否则就是非连通图非连通图 G 有三个连通分支 G

10 图的例子完全图两部图 K n 欧拉图正则图

11 5.1.2 树定义 5.2 无圈的连通图称为树性质 5.2 除单点树至少有两个度数为 1 的端悬挂点性质 5.3 任意树的边数 m 和端数 n 满足 m = n 1

12 定理 5.1 给定一个图 T 若 V = n E = m 则下面论断等价 : 1T 是树 ; 2T 无圈且 m = n 1 ; 3T 连通且 m = n 1

13 性质 5.3: 若 T 是树则 : 1T 是连通图去掉任何一条边图便分成两个且仅仅两个连通分支 ; 2T 是无圈图但添加任何一条边图便会包含一个且仅仅一个圈性质 5.4: 设 T 是树则任何两点之间恰好有一条道路 ; 反之如图 T 中任何两点之间恰好有一条道路则 T 为树

14 如果树 T 是连通图 G 的子图 T G 且 T 包含 G 的所有端称 T 是 G 的支撑树或主树连通图一定有支撑树树边连枝

15 5.1.3 割集割集指的是某些端集或边子集对连通图去掉此类子集图变为不连通定义 5.3 割端与割端集设 v 是图 G 的一个端去掉 v 和其关联边后 G 的部分数增加则称 v 是图 G 的割端去掉一个端集合后 G 的部分数增加这个端的集合称为割端集

16 点连通度对于连通图在众多的割端集中至少存在一个端数最少的割端集称为最小割端集最小割端集的端数目称为图的点连通度或连通度连通度用 α 表示

17 线连通度定义 5.4 割边与割边集设 e 是图 G 的一条边去掉 e 后 G 的部分数增加则称 e 是图 G 的割边去掉一个边集合后 G 的部分数增加这个边的集合称为割边集割边集中边数最少的割边集称为最小割边集最小割边集的边数目称为线连通度线连通度用 β 表示

18 性质 5.5 对于任意一个连通图 G= V E 若 V = n E = m δ 为最小度则 α β δ 2m n

19 基本割集和基本圈对于任何一个连通图 G 设 T 为 G 的一个支撑树每一条连枝决定的圈是基本圈确定了连通图的一个支撑树后每条树边可以决定一个基本割集对于支撑树去掉树上任何一条边树便分为两个连通分支从而将原图的端分为两个集合这两个集合之间的所有边形成一个极小边割集这个边割集称为基本割集

20 基本圈和基本割集 e 1 e 6e 2 e 3 e 5 e 4 图 5.3 基本圈和基本割集

21 基本圈和基本割集有许多应用首先通过集合的对称差运算由基本割集可以生成新的割集或它们的并集事实上可以证明生成所有的割集 ; 基本圈也有类似的性质例 5.2 通过基本圈和基本割集分析求解电网络

22 反圈下面给出一个重要的概念反圈确定的反圈为由称的非空真子集若是设或记为时将特别当 : 记若反圈 : 给定图定义 X X X V X S S T S S V T T v S u E v u T S V T S E V G G G G G G Φ Φ Φ Φ = = = φ ] [ \ }; { ] [ 5.5

23 5.1.4 图的矩阵表示下面将给出图的矩阵表示主要介绍关联阵和邻接阵 1 关联阵设图有 n个端 m条边则全关联阵 A = [ ] 其中 G a n m a 在无向图中 a a 在有向图中 a a = 1 若 e = 若 e = e = + 1 e = 1 e 与 v 关联与 v 不关联与 v 与 v 与 v 关联离开 v 关联指向 v 不关联

24 关联阵中每行对应一个端每列对应一个边由于完全表示了图中端集和边集的信息所以关联阵是图的一个等价表示例 5.3 考虑下面图 5.4 所表示的图 v1 e1 v2 e4 e5 e2 v4 e3 图 5.4 例 5.3 图 v3

25 则依照定义全关联阵为 A =

26 可以看出 : 1 每行非零元个数等于相应端的度数每列有两个 1; 2 任意两行或两列互换得到的关联阵本质上是一个图 3 将 A 中每列的任一个 1 改为 -1 因为 n 行之和零所以最多只有 n-1 行线性无关再去掉任一行得到关联阵 A 这是一个 n-1 m 矩阵

27 可以证明 A 的每一个 n-1 阶非奇异方阵一一对应一个支撑树并且定理 5.2 矩阵 - 树定理 T 用 A 表示 A 的转置无向图 G 的主树数目 t G = det T AA

28 T 同时 n-1 阶矩阵 AA 可以直接写出主对角线的元素为相应端点的度数其余位置根据相应的端点之间是否有边取值为 -1 或继续例 5.3 如果去掉第一行则 2 1 t G = det = 1 2 共有 8 种支撑树如下 : 8

29 邻接阵令 2 邻接阵邻接阵是表示图的端与端关系的矩阵其行和列都与端相对应 G = V E 为 n端 m边的有向图其邻接阵 : C = [ c ] n n 其中 c = 1 若 v到 v 有边若 v到 v 无边

30 对于例 5.3 中的图邻接阵为 : C = 对于无向图阵 c = c 因此是邻接阵为对称

31 于邻接阵包含了图的所有信息和关联阵一样是图的等价表示邻接阵和关联阵以后被经常用来表示图可以通过对邻接阵 C 做一些计算得到图 G 的一些性质例如可以计算 C 的幂来考虑图是否连通

32 Warshall 算法 1 置新矩阵 P:= C; 2 置 = 1; 3 对所有的如果 p = 1 则对 k=12 n 4 = +1 ; 5 如 p k : = p k p k n 转向步骤 3 否则停止 ;

33 5.2 最短路径问题上节中介绍的图只考虑了图顶点之间的关联性本节将要对图的边和端赋予权值讨论有权图权值在各种各样实际问题中有不同的物理意义如费用几何距离容量等在本节中将讨论最小支撑树和最短路径问题等算法

34 5.2.1 最小支撑树给定连通图 G= VE we 是定义在 E 上的非负函数 T = V E 为 G T 的一个支撑 w T = 树定义树 T 的权为 w e e E T 最小支撑树问题就是求支撑树 T 使 w T 最小下面介绍求最小支撑树的方法首先不加证明地引用定理 5.3

35 最小支撑树的特征定理 T 2 对 T 3 对 T 设 T 是最小支撑树 ; 是 G的支撑树则如下论断等价 : 的任一树边 e e是由 e所决定的基本割集或反圈中的最小权边 ; 的任一连枝 e e是由 e所决定的基本圈中的最大权边这个定理描述了最小支撑树的特征依照不同地逻辑可以有下面不同地具体做法

36 Prm 算法 Pr m 任取一点作为初始的 X 2 在反圈 Φ X 从 Φ X k k 将选出边的邻端并入 X 3 若在某一步 Φ X 若在某一步 X ; 中选边的原则是 : 中选一条权最小的边如果有多条权最小的边则任选一条 ; k k k 形成 X k + 1 = φ 则 G不含支撑树 ; ; = V 则由所有被选边生成的树是最小支撑树

37 例 5.4 求下图中的最小支撑树 v 1 v v 3 v 7 v v 4 5 v 5 图 5.5 例 5.4

38 Kruskal 算法 k 设是的无圈支撑子图开始 G k 若 G 是连通的则它是最小支撑树 ; 若 k 不连通取 e 为这样的一边它的两个端 k 点分属 G 的两个不同连通分支并且权 k+1 最小令 G = G k + e k 重复上述过程 G G = V Φ k G

39 破圈法 k 设 G 是 G 的连通支撑子图开始 G = G 若 G k 中不含圈则它 k 是最小支撑树 ; 若 G 中包含圈设 µ 是中的一个圈取 µ 上的一条权最大的 k 边令 k +1 k k e G = G - e 重复上述过程

40 例 5.5 对于一个无向图如何寻找其中的圈?

41 5.2.2 端间最短路径和路由已知图 G= VE 每条边有权 w 需要求网络中任意端点之间的最端距离和路由这类问题分两种情况 : 1 寻找指定端至其它端的最短路径和路由这个问题可以使用 Dkstra 算法解决 ; 2 寻找任意二端最短路径和路由这个问题可以使用 Floyd 算法解决

42 Dkstra 算法 } { mn = Φ Φ + = + = + Φ + Φ = = = = Φ 但情况情况当出现下面情况之一时停止的标号为并且并令使中选一边设为在的值计算反圈对任一边的标号为并且记初始算法可以简述如下 : 的权为 : 中的一条链定义链是设的每一边上有一个权图 k k k l l l l l X l l k l k k l k l k k e X X v X v v w w w X v X v l X w X v X v X l v v X Dkstra e w w G e w E V G k λ λ λ λ λ λ λ λ µ µ µ µ

43 对于 Dkstra 算法提出若干问题如下 : 1 如果端点有权如何处理? 2 如果边的权可正可负算法是否仍然有效? 3 算法是否对有向图也适用?

44 例 5.6 在下图中求距离和路由 v 1 到其余端点的最短 v 3 v v v 2 3 v 4 图 5.6 例 5.5

45 例 5.7 深度优先和广度优先搜索如果要搜索的环境为图 G=VE 每条边赋权 1 搜索的起点为 v 1 应用 Dkstra 算法求 v 1 到任意端 v 的距离距离 λ 表示了端 v 的代数

46 Floyd 算法定理 5.4 对于图 G 如果 w 表示端和端之间的可实现的距离那么 w 表示端和之间的最短距离当且仅当对于任意 k 有 : w w k + w k

47 Floyd 算法给定图及其边的权 F : 初始化距离矩阵 W 和路由矩阵其中 : G w 1 n1 n w w = 若 e E 若 e E 若 = R r 若 w = 其它

48 k-1 k-1 F1: 已求得 W 和 R 依据下面的迭 k k 代求 W 和 R k k 1 k 1 w = mnw wk + w k-1 k r r r k 1 k k 1 k k 若 w < w = k 1 k k 1 若 w = w F2: 若 k<n 重复 ;k=n 终止

49 对于 Floyd 算法同样提出若干问题如下 : 1 如果端点有权如何处理? 2 如果边的权可正可负算法是否仍然有效? 3 算法是否对有向图也适用? 问题 1 和 3 在 Dkstra 算法中有过讨论这里重点讨论问题 2

50 图的中心与中点已知图 G = V E 为权图根据 Floyd 算法的结果可以定义网络的中心和中点中心 n 对每个端点 max w 先求此值最小的端称为网的中心即满足下式的端 : n max * = n w mn[max w ]

51 中点 n s 对每个端点计算 = [ w ] 然后求出 s 的最小值相应的端点为中点

52 例 5.8 图 G 的距离矩阵如下用 Floyd 算法求任意端间最短距离和路由并求中心和中点 w =

53 解 : 距离矩阵包含了邻接矩阵和权的所有信息依照 Floyd 算法计算结果如下 : w 1 =

54 = R 1

55 = w 7 = R 7

56 t s 对于中心和中点根据的计算结果可以得到 : 从而图的中心为 v4 中点为 v7 = =

57 5.3 网络流量问题网络的目的是把一定的业务流从源端送到宿端流量分配的优劣将直接关系到网络的使用效率和相应的经济效益网络的流量分配受限于网络的拓扑结构边和端的容量流量分配和路由规划关系密切本节中关于流量问题的内容均在有向图上考虑并且均是单商品流问题即网络中需要安排的只有一种商品或业务 ;

58 5.3.1 基本概念 G = ce 给定一个有向图 VE 是定义在边集合 E 上一个非负函数称为容量 ; 边 e 的容量 c 表示这条边能通过的最大流量设 f = { f } 是上述网络的一个流该流有一个源 vs 和一个宿 v t 若能满足下述二个限制条件称为可行流

59 可行流的条件 1 非负有界性 : 对任意边 e 有 f c 2 连续性 : 对任意端 v 有 E f E f = F F v 为源端 v v 为宿端 v 其他 s t

60 v f = F 为源宿间流的总流量需要解决的基本问题分为两类 : 1 最大流问题在确定流的源和宿的情况下求一个可行流 f 使 v f = F 为最大

61 2 最小费用流问题如果边 e 的单位流费用为流的 d f 费用为 : C = E d 最小费用流问题在确定流的源和宿的情况下求一个可行流 f 使 C 为最小 f

62 下面介绍割量和可增流路的概念设 X 是 V 的真子集且 v s X v t X c XX c 表示起点和终点分别在 X 和 X c 的边集合这是一个带方向的反圈或割集割集的正方向为从 v s 到 v t 割量定义为这个割集中边容量的和 : c C X X = C v X 对可行流 {f }: fxx c 表示前向边的流量和 f 其中 v Xv X c fx c X 表示反向边的流量和 f 其中 v Xv X c v c X

63 则源为 v s 宿为 v t 的任意流 f 有 : 1. vf=fxx c -fx c X v s Xv t X c 对任 v X : 对所有 v X 将上述等式求和 : s s V v V v v v v v F f f = = f v F X X f X X f f f f f c c X v X v X v X v X v V v X v V v c c = = = =

64 2. vf CXX c 由 fx X c 非负可得 : c c c c C X X X X f X X f X X f f v =

65 下面讨论可增流路的概念从端 s 到端 t 的一个路有一个自然的正方向然后将路上的边分为两类 : 前向边集合和反向边集合对于某条流若在某条路中前向边均不饱和 f <c 反向边均有非流量 f 称这条路为可增流路在可增流路上增流不影响连续性条件也不改变其它边上的流量同时可以使从源端到宿端的流量增大

66 5.3.2 最大流问题所谓最大流问题在确定流的源端和宿端的情况下求一个可行流 f 使 vf 为最大对于一个网络求最大流的方法采用可增流路的方法下面的定理 5.5 为这种方法提供了保证

67 定理 5.5 最大流 - 最小割定理可行流 f = { f } 为最大流当且仅当 G 中不存在从 v s 到 v t 的可增流路证明 : 必要性 : 设 f * 为最大流如果 G 中存在关于 f * 的从 v s 到 v t 的可增流路 μ 令 θ = mn [ mn * mn c f f ] > µ + µ 构造一个新流 f 如下 : 如果 + * µ f = f +θ

68 如果如果 * µ f = f θ * µ f = f * f 不难验证新流 f 为一个可行流而且 vf=vf*+θ 矛盾充分性 : 设 f * 为可行流 G 中不存在关于这个流的可增流路

69 令 X * = {v G 中存在从 v s 到 v 的可增流路 } 从而这样那么流 f * 为最大流为最小割证毕性质 5.8: 如果所有边的容量为整数则必定存在整数最大流 X v X v t s c c f X X * * = 有对于任意边 * * = c f X X 对于任意边有 * * * c X X c f v = * * c X X

70 求最大流的基本思想是 : 在一个可行流的基础上找 v s v t 的可增流路然后在此路上增流直至无可增流路时停止 M 算法 : 从任一可行流开始通常以零流开始 1 标志过程 : 从 v s 开始给邻端加标志加上标志的端称已标端 ;

71 2 选查过程 : 从 v s 开始选查已标未查端 ; 查某端即标其可能增流的邻端 ; 所有邻端已标则该端已查标志宿端则找出一条可增流路到宿端进入增流过程 3 增流过程 : 在已找到的可增流路上增流

72 步骤 : M : 初始令 f = M1: 标源端 v s :+s M2: 从 v s 始查已标未查端 v 即标 v 的满足下列条件的邻端 v 若 v v Ec > f 标 v 为 : +ε 其中 ε =mnc -f ε ε 为 v 已标值若 v v E f > 标 v 为 : - ε 其中 ε =mnε f 其余 v 端不标

73 所有能加标的邻端 v 已标则称 v 已查倘若所有端已查且宿端未标则算法终止 M3: 若宿端 v 已标则沿该可增流路增流 M4: 返回 M1

74 上面的算法是针对有向图且端无限制的情况若是有无向边端容量及多源多宿的情况可以进行一些变换化为上述标准情形这个算法的复杂度不是多项式的但是经过简单改进后算法为多项式复杂度需要解决下面的情况 : 1. 端有容量限制 ; 2. 无向边 ; 3. 多源多宿 ;

75 5.3.3 最小费用流问题如果网络为图 G = V E 源端为 v s 宿端为 v t 边的单位流费用为 d 流 f 的费用为 : C = d f 所谓最小费用流问题 : 在确定流的源和宿的情况下求一个可行流 f 使 C 为最小 E

76 最小费用流问题是线性规划问题但也可用图论方法求解效率更高对于它的存在性可以这样理解流量为 F 的可行流一般不是唯一的这些不同的流的费用一般也不一样有一个流的费用最小寻找最小费用流可以用负价环法算法 Klen 1967 所谓负价环的意义如下: 负价环为有向环同时环上费用的和为负负价环算法的具体步骤如下 :

77 K: 在图 G 上找任意流量为 F 的可行流 f; K1: 做流 f 的补图 ; 做补图的方法如下 : K2: 在补图上找负价环 C - 若无负价环算法终止 K3: 在负价环上沿环方向使各边增流增流数 : mn * C c = δ d f c e f c e 1 单位流费用为 : 容量为 : 构造边如果对于所有边 > d f e f e 2 > 单位流费用为 : 容量为 : 构造边如果对于所有边

78 K4: 修改原图每边的流量得新可行流 K5: 返回 K1 上面的算法中需要寻找负价环这个可以通过 FLOYD 算法来解决例 5.1: 已知 c d 要求 F=9 求最小费用流

79 上面可行流安排总费用为 :C=12 下面做补图寻找负价环调整可行流 v s v s δ = mn 334 = C 5-3 3

80 这个新可行流的补图如下 : 这个补图没有负价环 v s

81 习题

一握手定理的应用二平面图欧拉公式的应用三图的基本概念与应用四欧拉图和哈密顿图五图的着色

一握手定理的应用二平面图欧拉公式的应用三图的基本概念与应用四欧拉图和哈密顿图五图的着色图论习题考研习题与经典习题 2004-5 一握手定理的应用二平面图欧拉公式的应用三图的基本概念与应用四欧拉图和哈密顿图五图的着色一握手定理的应用 1. 已知具有 n 个度数都为 3 的结点的简单图 G 有 e 条边, (1) 若 e=3n-6, 证明 G 在同构意义下唯一, 并求 e,n (2) 若 n=6, 证明 G 在同构意义下不唯一提示 : 握手定理 ( 北师大 2000