工程硕士班《通信网理论基础》.pptVIP

Chapter 14 Overview of Graph Theory and Least-Cost Paths TCP Traffic and Congestion Control in ATM Networks Chapter 13 通信网理论基础 第三部分 图论基础 与 应用 基本概念 图 G(V,E) 由两个集合加以定义: 顶点 (或节点) 集合 V={ v1,v2,v3….vn }; 边集合 E={e1,e2,e3……em }; G={V, E } 边由一对直接关连的顶点的组合定义 如果: (i,j) ? E,则顶点i和 j称为相邻的 顶点的数目称为图的“阶”;边的数目称为图的“尺寸”; 许多图的算法的运行时间与图的“阶”和“尺寸”相关 图的一个例子 图的邻接矩阵 邻接矩阵是用数学方式来表示图 顶点编号: 1,2,3,…,|V| |V| x |V| 邻接矩阵 A=(ai,j) 定义为: ai,j = 1 if (i,j) ? E (ij是图的一条边) 0 otherwise 对于边没有方向性的图(即边的两顶点的顺序不影响边的性质),邻接矩阵A是对称矩阵. 邻接矩阵一例 Terminology 关联同一对顶点的边称为: 平行边 关联同一顶点的边称为: 环 既无平行边,又无环的图称为: 简单图 顶点 i 到顶点 j的路径是: 顶点和边的交替序列 起于i,止于j; 每条边只与序列中直接在它前面和直接在它后面的顶点相连 简单路径 : 顶点和边在序列中只出现一次的路径 在简单图中,简单路径可以由顶点序列来定义 每个顶点与序列中在其前面和后面的顶点相邻 序列中没有重复的顶点 简单路径 (1) 由V1 到 V6 (不完全) V1,V2,V3,V4,V5,V6 V1,V2,V3,V5,V6 V1,V2,V3,V6 V1,V2,V4,V3,V5,V6 V1,V2,V4,V5,V6 V1,V3,V2,V4,V5,V6 V1,V3,V6 V1,V4,V3,V6 总共14条(其余的请自行列出) 简单图 (2) 两顶点间的所有路径中有一条最短路径,如:V1,V3,V6 顶点间的距离是所有路径中边数最少的路径的边的数目 回路是起于和止于同一顶点的路径 例如:. V1,V3,V4,V1 有向图 边有方向性的图 有向图 G(V,E) 的边由一对顶点的有序组合来定义 代表边的线段用箭头表示其方向 允许存在平行边,只要它们的方向相反 便于用图表示通信网络 每条有向边表达一个方向上的数据流 仍然可用邻接矩阵表示 除非每对相邻的顶点用平行边连接,否则邻接矩阵是不对称的 加权图 或加权有向图 每条边有一与之关联的数(权值w) -------便于说明路由算法 邻接矩阵定义为: ai,j = wi,j if (i,j) ? E 0 otherwise wi,j 是与边( i, j )关联的权值 路径长度是权值之和 最短距离路径不一定是长度最短路径(见下面两张PPT) 加权图与邻接矩阵 V1 至 V6 的路径距离 和 路径长度 路径 距离 长度 V1,V2,V3,V4,V5,V6 5 11 V1,V2,V3,V5,V6 4 8 V1,V2,V3,V6 3 10 V1,V2,V4,V3,V5,V6 5 10 V1,V2,V4,V5,V6 4 7 V1,V3,V2,V4,V5,V6 5 16 V1,V3,V6 2 10 V1,V4,V5,V6 3 4 树 树是图的子集 以下几项定义是等效的: * 树是一种简单图,顶点i 和 j 之间只有一条简单路径 * N个顶点的简单图如果只有N-1 条边,没有回路 * N个顶点的简单图如果只有N-1条边,而且是连通的 可以指定一个顶点为“根” 根通常画在上部 与根邻接的顶点画在下一层 这些顶点可以到达树根,路径距离为1 树中顶点的等级关系 每个顶点(除根外)有一个父顶点 靠根一边的邻接顶点 每个顶点有0个或几个子顶点 离根远的邻接顶点 没有子顶点的顶点称为叶 层次等级 直接在根下面的顶点是第一层 第一层顶点的子顶点是第二层 树的例 子图 从图G中选择一些边和顶点构成G的子图 每条被选上的边的两个关联顶点必须同时选上 图 G’(E’,V’) 是图G(E,V) 的子图,如果: V’ ? V , E’ ? E 并且 对每一条E’中的边e’.如果 e’ 关联 v’ and w’,