➢ 有向图：设图G =(V,E )，当vi对vj存在关系R不等 价于vj对vi存在关系R, 则称G 为有向图。即图G 中 的任意一条边都对应一个有序节点对（vi, vj ）， （vi，vj）≠（vj，vi）。其边的方向为vi → vj 。
如图2.4所示。
v1
v5
v2
v4
v3
图2.4 有向图
9
2.1.1 图的概念
v3
(a)
(b)
11
2.1.1 图的概念
➢ 节点的度数：与某节点相关联的边数可定义为该节点的度数，记为
d(vi)。如图2.6(a)中d(v2)=4,d(v3)=2,d(v1)=4。
✓ 若为有向图，
d+(vi)：表示离开或从节点vi射出的边数,即节点vi的出度， d-(vi)：表示进入或射入节点vi的边数即节点vi的入度， 节点vi的度数d(vi)=d+( vi)+d-( vi)。 如图2.6(b)中，d+(v1)=3, d-(v1)=1, d(v1)=4。
3
图论是专门研究人们在自然界 和社会生活中遇到的包含某种 二元关系的问题或系统。它把 这种问题或系统抽象为点和线 的集合，用点和线相互连接的 图来表示，通常称为点线图。
图论就是研究点和线连接关系 的理论。
传统的网都是转接式的，包括 电路转接和信息转接，是由交 换节点和传输线路构成。从数 学模型来说这是一个图论的问 题。
✓ 没有自环和重边的图称为简单图。
✓ 在实际问题中，重边常可合并成一条边。对于一条无向边可画 成两条方向相反的有向边，使有向图中没有无向边，也可将与 同一对节点相关联的两条有向边合并成一条无向边。
e1
v1
e2
e6
e5
e1
v1
e2
e6
e5
v2
v4
v2
v4
e7
e3
e4
e7
e3
e4
v3
图2.6 自环、重边示意图
➢ 对网络拓扑结构的研究是通信网规划和设计中第一层次的 问题。
在通信网的规划、设计和维护中，可靠性是一项重要的性
能指标。
1
第2章 网络规划设计理论基础
2.1 图论基础 2.2 树 2.3 路径选择算法 2.4 网络流量分配及其算法 2.5 通信网的可靠性
2
2.1 图论基础
2.1.1 图的概念 2.1.2 图的矩阵表示
图中v1与e1,e2,e6关联, v1与v2,v3,v4是相邻节点, e1与e2,e3,e4,e6是相邻边。
2.1.1 图的概念
v1
e1
e6
e2
v2
e3
v4
e4
e5
v3
图2.2 图G
6
2.1.1 图的概念
➢ 一个图可以用几何图形来表示，但一个图所对应的几何图 形不是唯一的。
➢ 不难看出，图2.2表示的图与图2.1表示的图是相同的图G， 说明一个图只由它的节点集V、边集E 和点与边的关系所
➢ 关与系之对R 可应以。说图成G对中任的一V边集e可k，任有意V给中定的，一而个E 节集点只对是(代vi,表vjV) 中关的系二时元（关如系邻。接对关系vi∈）V才,有vj∈某V一, 个当e且k仅∈当E。vi对一v个j存ek在只某能种对
应一点对(vi,vj)。
➢ 如果有一条边ek与节点对(vi,vj)相对应，则称vi, vj是ek的 端vj为点相，邻记节为点ek。=(vi , vj)，称点vi , vj与边ek关联，而称vi与
确定，而与节点的位置和边的长度及形状无关。
➢ 图2.1和图2.2只是一个图G 的两种不同的几何表示方法。
v1
v1
e1
e6
v2
e3
v4 e2
e1
e6
e2
v2
e3
v4
e4
e5
e4
e5
v3
图2.1 图的概念
v3
图2.2 图G
7
2.1.1 图的概念
2．图的相关概念
➢ 节点：表示物理实体，用vi表示。
➢ 边：节点间的连线，表示两节点间存在连接关系，用eij表
示。
➢ 无向图：设图G =(V, E )，当
v1
v5
vi对vj存在某种关系R等价于
vj对vi存在某种关系R，则称 G 为无向图。即图G 中的任
v2
v4
意一条边 ek 都对应一个无序 节点对（vi, vj）,（vi,vj）= （vj, vi）。如图2.3所示。
v3
图2.3 无向图
8

2.1.1 图的概念
第2章 网络规划设计理论基础
通信网设计要求：
➢ 满足各项性能指标要求；
➢ 节省费用；
➢ 要求设计人员应掌握相当的网络理论基础知识和网络分析 的计算方法，如通信网所涉及的数学理论、优化算法、网 的分析方法与指标计算方法等。
通信网的拓扑结构在通信网设计中的作用：
➢ 影响网络的造价和维护费用；
➢ 对网络的可靠性和网络的控制及规划起着重要的作用；
图2.5所示。
v1
2.5 v5
3.1
2.7
v2
4.2
v4
1.8
5.3
v3
图2.5 有权图
10
2.1.1 图的概念
➢ 自环：若与一个边er 相关联的两个节点是同一个节点,则称边er
为自环。
➢ 重边：
✓ 在无向图中与同一对节点关联的两条或两条以上的边称为重边。
✓ 在有向图中与同一对节点关联且方向相同的两条或两条以上的 边称为重边。
➢ 若有两条边与同一节点关联，则称这两条边为相邻边。
5
例2.1 图2.2中
V={v1, v2, v3, v4 } E={e1, e2,e3,e4, e5, e6} 其中e1=(v1, v2), e2=(v1, v3), e3=(v2, v4), e4=(v2, v3), e5=(v3, v4), e6=(v1, v4)。 故可将图2.2记为G =(V, E )。
2.1.1 图的概念
v1
e1
e6
v2
e3
v4 e2
e4
e5
v3
图2.1 图的概念
通信网中： 点→交换节点 线→传输链路 图论在通信网的设计中的应用： ➢ 确定最佳网络结构； ➢ 进行路由选择； ➢ 分析网络的可靠性等。
4
2.1.1 图的概念
1．图的定义
➢ 设有节点集V={v1,v2,…,vn}和边集E={e1,e2,…,em}，当存 在关系R，使V×V→E成立时，则说由节点集V 和边集E 组成图G，记为G =（V,E）。
➢ 有权图：设图G =(V, E )，如果对它的每一条边ek 或对它 的每个节点vi 赋以一个实数pk，则称图G 为有权图或加权 图，pk 称为权值。对于电路图，若节点为电路中的点，边
为元件，则节点的权值可以为电压和电阻，边的权值为电
流。对于通信网而言，节点可代表交换局，权值可以为造
价或容量等，边代表链路，权值可以为长度，造价等，如