通信网理论基础第3章解析.ppt

通信网设计要求： 满足各项性能指标要求 节省费用 要求设计人员应掌握相当的网络理论基础知识和网络分析的计算方 法，如通信网所涉及的数学理论、优化算法、网的分析方法与指标计算 方法等。 通信网的拓扑结构在通信网设计中的作用： 影响网的造价和维护费用 对网络的可靠性和网络的控制及质量起着重要的作用 对网络的拓扑结构的研究是通信网的规划和设计中第一层次的问题 通信网的结构 传统的网都是转接式的，是由交换节点和传输线路构成 从数学模型来说这是一个图论的问题。 一、图的概念 图论：是离散数学的一部分，是现代应用数学的一个分支。离散数学以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素。 图论：图论专门研究人们在自然界和社会生活中遇到的包 含某种二元关系的问题或系统。它把这种问题或系统抽象 为点和线的集合，用点和线相互连接的图来表示，通常称 为点线图。图论就是研究点和线连接关系的理论。 通信网中，点→交换节点 线→传输链路 图论在通信网的设计中的应用： （1）确定最佳网路结构 （2）进行路由选择 （3）分析网路的可靠性等 1.图的定义 设有端点集V={v1,v2,…,vn}和边集E={e1,e2,…,em}，当存在 关系R，使V×V→E成立时，则说由端点集V和边集E组成图 G，记为G=（V，E）。 关系R：指对任一边ek，有V中的一个点对(vi,vj)与之对应。 此时： a.称vi ,vj是ek的端点，记为ek=(vi,vj)； b.称点vi,vj与边ek关联，且称vi与vj为相邻点。 c.若有两条边与同一端点关联，则称这两条边为相邻边。 对vi∈V ,vj∈V, 当且仅当vi 对vj存在某种关系时（如邻接关 系）才有某一个ek∈E（或有两个或更多的ek∈E对应vi和vj）。 一个ek只能对应一点对(vi,vj)。 一个图可以用几何图形来表示，但所对应的几何图形不是唯一 的。 2. 图的相关概念 无向图：设图G=(V , E)，当vi对vj存在某种关系R等价于vj 对vi存在某种关系R, 则称G为无向图。即图G中的任意一条 边ek都对应一个无序点对（vi ,vj），记为 ek=（vi，vj）=（vj，vi）。（一条边） 有向图：设图G=(V , E)，当vi对vj存在某种关系R不等价于 vj对vi存在关系R, 则称G为有向图。即图G中的任意一条边 都对应一个有序点对（vi,vj ）， 即 ek=（vi，vj）≠（vj，vi）（两条边）。 其边的方向为vi → vj 空图：若图G中的端集V是空集，则不可能有边集E，这样的图称为空图。 孤立点图：若图G中的边集E为空集，点集V不空，但各端间无关系，则称图G为孤立点图。 有限图：若图G中的端集V和边集E为有限集时称图G为有限图。实际上我们通常所遇到的都是有限图。 无限图：若图G中的端集V和边集E中有一个为无限集时称图G为无限图。 有权图：设图G=(V , E)，如果对它的每一条边ek或每一个端点vi赋以一个实数pk，则称图G为有权图或加权图，pk称为权值。边和端的权值可以不止一个，可以是正值或负值，在实际问题中，代表不同的含义。 二、图的连通性 （一）相关概念 1.自环、重边和度数 自环：若与一个边er相关联的两个端是同一个端点,则称边er为自环。 重边：在无向图中与同一对端点关联的两条或两条以上的边称为重边。在有向图中与同一对端点关联且方向相同的两条或两条以上的边称为重边。没有自环和重边的图称为简单图。 在实际问题中： 重边→ 一条边 一条无向边←→两条方向相反的有向边 端的度数：与某端相关联的边数可定义为该端的度数。记为d(vi)。若为有向图，d+(vi)：表示离开或从端vi射出的边数,即端vi的出度；d-(vi)：表示进入或射入端vi的边数，即端vi的入度。d(vi)=d+(vi)+d-(vi) 度数的两个性质： （1）对于有n个端、m条边的图，必有 （2）任何图中，度数为奇数的端的数目必为偶数（或零）。即V1：奇度数端集 2.链、径和回路 边序列：有限条边的一种串序排列称为边序列。边序列中的各条边是首尾相连的，在边序列中，可以有重复的边和重复的端。 链(chain)：没有重复边的边序列叫做链。但在链中可以有重复的端。 链可分为开链和闭链。 开链：起点和终点不是同一端的链。通常所说的链指的是开链。 闭链：起点和终点重合的链。 链的长度：链中边的数目称为链的长度。 径(path)：既无重复边，又无重复端的边序列叫做径。在一条