通信网理论基础第二章 通信网拓扑结构分析1.ppt

第二章通信网拓扑结构分析 通信网的拓扑结构分析是很基本的问题 是通信网规划和设计的第一层次问题 通信网的拓扑结构可以用图论的模型来代表 主要的问题为最短路径和网络流量问题等 2 1图论基础2 1 1图的定义 例2 1Euler7桥问题 Kirchhoff应用树去研究电网络分析问题 Cayley将树应用到化学领域等 所谓一个图 是指给了一个集合V 以及V中元素的序对集合E V和E中的元素分别称为图的端点和边 记为 如果端点集合为V v1 v2 vn 边集合为E e1 e2 em 当eij vi vj 称边eij和端vi与vj关联 无向图 对任意vi vj 如果 vi vj E 就有 vj vi E 有向图 对任意vi vj 如果 vi vj E 不一定有 vj vi E 当V 为空图 当E 为孤立点图 自环 伪图 重边 简单图 不含自环和重边的图称为简单图 有限图 当集合V E均有限时 称为有限图 我们一般讨论的都是有限图 考虑到实数集的不可数性 任何有限图都可以表示为三维空间的几何图形 使每两条边互不相交 而且边均可用直线来实现 子图 若A的端集与边集分别为G的端集与边集的子集 则A为G的子图 若A G 且A G 则A为G的真子图 特别地 当A的端集和G的端集相等 称A为G的支撑子图 由端点子集诱导生成的子图 由边子集诱导生成的子图 图的运算 G1 G2 G1 G2 Gc等 图的几种表现形式 集合论定义 几何实现 矩阵表示 图的同构 权图 2 1 2图的连通性 对无向图的端vi来说 与该端关联的边数定义为该端的度数 记为 d vi 对有向图 d vi 表示离开vi的边数 d vi 表示进入vi的边数 对图G V E 若 V n E m 则有 1 若G是无向图2 若G是有向图 下面定义图的边序列 链 道路 环和圈 相邻二边有公共端的边的串序排列 有限 v1 v2 v2 v3 v3 v4 vi vj 称为边序列 边序列中 无重边的 成为链 link 若边序列中没有重复端 称为道路 path 若链的起点与终点重合 称之为环 ring 若道路的起点与终点重合 称之为圈 cycle 任何二端间至少存在一条路径的图 为连通图 否则 就是非连通图 对非连通图来说 它被分为几个最大连通子图 最大连通图 指的是在此图上再加任意一个属于原图而不属此图的元素 则此图成为非连通图 如下例 对于图的连通 可以通过下面的方法给予准确的描述 对于图G中的任意两个端点u和v 如果存在一条从u到v的链 称u和v有关系 容易知道这是一个等价关系 从而可以将图G做一个等价分类 每一个等价分类就是一个连通分支 连通分支只有一个的图为连通图 如果没有特别申明 一般考虑简单连通图 下面举一些图的例子 1 完全图Kn 任何二端间有且只有一条边 称为完全图 其边 端数之间存在关系 下面是一个n 5的完全图 2 正则图 所有端度数都相同的连通图为正则图d vi 常数 i 1 2 n 正则图是连通性最均匀的图 3 欧拉图 Euler 端度数均为偶数的连通图为欧拉图 欧拉图的性质 欧拉图存在一个含所有的边且每边仅含一次的环 4 两部图两部图的端点集合分为两个部分 所有边的端点分别在这两个集合中 完全两部图Km n 5 哈密尔顿图如果图有一个圈能够经过所有的顶点 2 1 3树 树是图论中一个很简单 但又很重要的概念 图的定义有多种 如下面的定义 1任何二端有径且只有一条径的图称为树 2无圈的连通图称为树 我们采用第2种关于图的定义方式 也就是 树 无圈的连通图称为树 树有以下性质 1 树是最小连通图 树中去一边则成为非连通图 2 树中一定无环 任何二端有径的图是连通图 而只有一条径就不能有环 3 树的边数m和端数n满足 m n 14 除单点树 至少有两个度数为1的端 悬挂点 定理2 1 给定一个图T 若p V q E 则下面论断等价 1 T是树 2 T无圈 且q p 1 3 T连通 且q p 1 证明 1 2 显然 2 3 反证 若T不连通 它有k个连通分支 k大于等于2 每个都为树 若第i个树有个点 则有下面的矛盾 3 1 反证 若T有圈 从圈中去掉任意一条边仍然保持连通 去掉若干条边后得到一个支撑树 但这与q p 1相矛盾 定理2 2 若T是树 则 1 T是连通图 去掉任何一条边 图便分成两个且仅仅两个连通分支 2 T是无圈图 但添加任何一条边 图便会包含一个且仅仅一个圈 同时 若无向图满足 1 和 2 则T是树 定理2 3 设T是树 则任何两点之间恰好有一条道路 反之 如图T中任何两点之间恰好有一条道路 则T为树 支撑树 SpanningTree 考虑树T是连通图G的子图 T G 且T包含G的所有端 称T是G的支撑树 只有连通图才有支撑树 反之有支撑树的图必为连通图 一般支撑树不止一个 连通图至少有一个支撑树 支撑树上任二端间添加一条树边以外的边 则形成环 支撑树外任一边称支撑树的连枝 连枝的边集称为连枝集 不同支撑树对应不同连枝集 2 1 4割 割指的是某些子集 端集或边集 对连通图 去掉此类子集 图变为不连通 割分为割端集 割边集和混合割集 1割端与割端集设V1是图G的一个端子集 去掉V1和其关联边后 G V1不连通 则称V1是图G的割端集 特别若V1为独点集 其中的端为割端 对于连通图 在众多的割端集中至少存在一个端数最少的割端集 称为最小割端集 最小割端集的端数目 称为图的联结度 2割边与割边集连通图G的边子集E1 去掉E1使G为不连通 称E1为割边集 特别若E1为独点集 其中的边为割边 在众多的割集中边数最少的割边集 称为最小割边集 最小割集的边数 称为结合度 特别 完全图Kn的联结度为n 1 完全图K1的结合度为0 3 基本割集与基本环1 基本割集设T为连通图G的一个支撑树 取支撑树的一条树枝与某些连枝 定可构成一个极小边割集 此割集称为基本割集 基本割集有n 1个 2 基本环T为连通图G的一个支撑树 G T的边集为连枝集 取一连枝可与某些树枝构成环 这种包含唯一连枝的环称基本环 每个基本环只包含一个连枝 其数目与连枝一一对应 共m n 1个 下面一个图来理解基本割集 支撑树 连枝 则基本割集 下面的图理解基本环 支撑树连枝集基本环为 例2 2通过基本环和基本割集理解基尔霍夫定律 环和运算 对于集合 这个运算的意义为对称差运算 通过环和运算 由基本割集和基本环可以生成新的环和边割集或它们的并集 事实上可以生成所有的环和边割集 2 1 5图的平面性 图G若可以在一个平面上实现 除端点以外 任何两条边均无其他交点 则称G是平面图 当平面图有一个平面实现后 它把全平面分成f个区域 含包含无穷远点的开区域 设连通平面图有m边 n端 f个区域 则 Euler f m n 2 定理2 4 简单连通图为平面图的必要条件是 例2 3讨论完全图K5和完全两部图K3 3的平面性 定理2 5 连通两部图为平面图的必要条件是 定理2 6 图G为平面图当且仅当G不含K5和K3 3或它们的细分图为子图 2 1 6图的矩阵表示 很多时候 需要使用图的矩阵表示 下面主要介绍关联阵和邻接阵 1关联阵 从全关联阵去掉任何一行就可以得到关联阵 如果将关联阵的每列中任何一个1改为 1 将这个矩阵记为A 对于连通图 这个矩阵的秩为n 1 每个满秩子阵对应图G的一个支撑树 下面是一个例子说明关联矩阵 例2 4 定理2 7 矩阵 树定理 用AT表示A的转置 无向图G的主树数目 G det AAT 注意上面的定理计算的主树数目为标号树的数目 同时n 1阶矩阵det AAT 可以直接写出 主对角线的元素为相应端点的度数 其余位置为 1或0 而这取决于相应的端点之间是否有边 例2 5 Kn nn 2 Kn m mn 1nm 1 继续例2 4 共有8种支撑树如下 2 邻接阵邻接阵是表征图的端与端关系的矩阵 其行和列都与端相对应 对于无向图 邻接阵为对称矩阵