第4章通信网结构

2010-11-251通信网理论基础通信网理论基础通信网理论基础11引论（通信网概述）引论（通信网概述）22网内业务分析网内业务分析33多址接入系统分析多址接入系统分析44通信网结构（图论基础）通信网结构（图论基础）55通信网中的流量优化通信网中的流量优化66通信网的可靠性通信网的可靠性Reference:1.Reference:1.通信网理论基础通信网理论基础2.2.图图论及应用论及应用3.3.运筹学运筹学2010-11-252第四章通信网结构4.14.1图论基础图论基础4.1.14.1.1抽象图基本定义抽象图基本定义4.1.24.1.2图的联结性图的联结性4.1.34.1.3树树4.1.44.1.4割和环割和环4.1.54.1.5平面图性和对偶性平面图性和对偶性4.1.64.1.6图的矩阵表示图的矩阵表示4.24.2昀短路径问题昀短路径问题4.2.14.2.1最短主树最短主树4.2.24.2.2端间的最短径端间的最短径4.34.3站址问题站址问题4.3.14.3.1单中点问题单中点问题4.3.2k4.3.2k中点问题中点问题4.3.34.3.3设站问题设站问题2010-11-253第四章通信网结构路由？优化设站？2010-11-2544.1图论基础A岛B岛C岸D岸*七桥问题CBDA拓扑图设有节点集合V和边集E，V={v1，v2，……，vn}，E={e1，e2，……em}，且EVVR⎯→⎯×则V和E组成图G，称V为端集，E为边集。2010-11-2554.1图论基础4.1.1基本定义一、抽象图的定义抽象图用点和边来反映实际网络中的具体事物和事物间相互关系。无向图记为：G（V，E）或G（V(G),E(G)）,简记为G。其中：①V或V（G）是点的集合，集合表示：V（G）或V={V1，V2，……Vn},图表示：•ο;②E或E（G）是边（两点间连线）的集合，集合表示：E（G）或E={e1,e2,……em}={(i1,j1),(i2,j2),…(im,jm)};无向图表示：or2010-11-2564.1.1抽象图的基本定义二、抽象图常用术语1.自环（或自回路）：两端点相同的边。2.重边（或并联边，平行边）：两点间有多条边存在。如(i,j)1,(i,j)2,……,(i,j)k,k≥2,表示i，j节点间有k条边存在。3.关联：边与连接它的点互称为关联。4.邻接：连接一条边的两节点，互称为邻接点。5.孤立节点图：只有点无边的图。6.简单图：无环且无重边的图。7.空图：无点无边的图。V=ф，E=ф。8.有限图：点集V和边集E有限的图。V1V2V3V4V5V6e1e2e3e4e5e6e7e8e9e02010-11-2574.1.1抽象图的基本定义1122334456有向图G1无向图G2三、集合相关的图描述1.子图：Gs和G均为图，且V(Gs)⊆V(G),E(Gs)⊆E(G),则称Gs是G的子图，记为Gs⊆G;生成子图：含图G所有节点的子图。[例]：判断图G1和G2是否是G的子图？是否生成子图？V1V2V3V4V5V2V4V5图G图G1图G2V2V4V5V1V32010-11-2584.1.1抽象图的基本定义三、集合相关的图描述：2.两个图的运算：2个图的并，交，相差，环和运算。例:已知G1和G2，求G1∪G2，G1∩G2，G1⊕G2，G1−G2及G2−G1。fdce43ba21G1jicg45he3G2d2fdce43ba21G1∪G2jig5hdce432G1∩G2f3ba21G1−G2G2−G143jig5hf43ba21G1⊕G2jig5h2010-11-2594.1.2图的联结性（连通）1.节点的度数定义：图G中节点i的度数记为d(i)，等于与该节点相关联的边数。孤立节点的度数是0；若节点i为自环，则d(i)=2;则：图中所有节点度数之和是边数b的两倍，∑==Nibid12)(211()()()NijVkVdidkdj=∈∈=+∑∑∑推论：设V1，V2分别表示图G中顶点度数为奇数、偶数的两个点集，则且奇度节点的节点数为偶数。V1V2V4V5V3e3e1e7e6e2e4e5e8e92010-11-25104.1.2图的联结性（连通）2.链、径和环边序列定义：由点、边交叉的有限序列(i1,i2)，(i2,i3)，……，(ik-1,ik)称为长度为K-1的边序（或通路）。i1=ik，称闭合边序，否则称开放边序，在开放边序中，i1称为始点，ik为终点，i1和ik都称为边序的端点，其它节点称为内节点。“手不离纸，一笔画成”在一个边序中，同一节点可重复出现，同一边也可以重复出现。V2V3V4V5V6V7V1[例]:已知一个图的几何图形如下：边序列(V1,V2)(V2,V7)(V7,V1)(V1,V2)(V2,V3)是长度为5的开放边序。边序列（V1,V7）（V7,V5）（V5,V7）（V7,V6）（V6,V1）是长度为5的闭合边序。2010-11-25114.1.2图的联结性（连通）2.链、径和环链定义：边序中无重复的边，则称这样的边序列为链。在一个链中，同一节点可重复出现，同一边不可以重复出现。下图中(V1,V2)(V2,V7)(V7,V1)(V1,V6)就是边不重、点重复的链。V2V3V4V5V6V7V1径：点不重复的边序列。（边当然不重复）环：起点和终点相同的链。闭链(V1,V7)(V7,V5)(V5,V6)(V6,V1)就是长度为4的回路，这也是一条闭径。V2V3V4V5V6V7V12010-11-25124.1.2图的联结性（连通）3.图的联结性①点联结：若图G中存在一路径P，u、v都是P上的节点，则称u、v在G中点连通。②联结图：若图G中任两节点都连通，则该图为连通图③连通片：图中含有昀大边数的连通子图称为该图的连通片。记为C(G)，简记为C。连通图C(G)=1；非连通图可分多个连通子图，C(G)1。[例]：已知图G，求其连通片数。V4V6V3V1V2解：该图有3个连通片，C(G)=3。2010-11-25134.1.2图的联结性（连通）阶r：若图G中含有n个节点，C个连通片，则r=n−c称为图G的阶。非连通图的阶是各连通片的阶之和。零度m：若图G含有b条边，n个节点和C个连通片，则称m=b−n+c=b−r为该图的零度。图的秩和零度都是非负数，当且仅当图中不含回路时，该图的零度为0；当且仅当图中只含一条回路时，图m=1。[例]：已知图G，求其阶和零度。V4V6V3V1V2解：n=5，c=3，r=2；由于b=3，则m=3−5+2=1。2010-11-25144.1.2图的联结性（连通）4.典型的联结图全联结图：任何节点间都有n-1条边的联结图，记Kn。正则图：所端节点的度数相同的图，称为正则图。两部图：图的节点分为V1,V2集合，所有边两端分别桥接在此两节点集合中，完备Km,n图。欧拉图：各节点度数均为偶数的图。M图：图中只有2个节点的度数为奇数的图。汉密尔顿H图：图在至少存在1个环，经过所有节点。K3,2图2010-11-25154.1.3树1.树不含回路的联结图称为树（tree）图。多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图。树图中的每一个连通子图都称为森林（forest），树和森林中的边称为树枝。（a）树G（b）三个森林2010-11-25164.1.3树树的特征：1).若图G是树图，则任意两顶点间必有一条且仅有一条通路。由于树图的连通的，所以树图中任意两顶点间必有通路，如果两顶点间有两条不同的通路存在，则必将出现回路，此与树的定义矛盾。2).树无环，但在树图中不相邻的两个顶点间添上一条边，则恰好得到一条回路（环）。3).设树G是有n个顶点的一棵树，那么树的边数为n−1。4).除单点树外，树至少有2节点的度数为1。5).树图是连通且无回路的图，同时，树是二分图。2010-11-25174.1.3树主树定义:如果T是图G的一个生成子图而且又是一棵树，则称T是图G的一棵主树，也称生成树（spanningtree）。图G4213e5e4e3e2e1234T31234T41234T21234T11主树的性质：1)T是连通图G的一棵主树的充要条件是：T是G的有n−1条边的连通生成子图。主树T的树枝数就是图G的阶ρ(G)。2)图G有主树的充要条件是：图G连通。3)计算图的主树的各边的加权值和，得到的一个和最小的主树称为最小重量生成树。2.主树2010-11-25184.1.4割和环1.割点1).割端（割点）设Vi是图G的一端点，去掉Vi及与之关联的所有边后，若图G的连通片数C增加，则称Vi是图G的割端。12346785910[例]：求右图G的割点。2010-11-25194.1.4割和环2．割集、割1)割集：指图G中昀小数量的边集合构成的子图，若移去这些边(全部)，将使图G的秩减1（即连通片增加1）。2)割边：割集中的每一条边，都称为这一割集的割边。3)割边集（割）：图的割集或边不相接割集的并集称为割。解：割集e1e2;e2e3e5;e1e3e5;e2e4e5;e1e4e5;e3e4;e6e8;e6e7;e7e8。e2[例]：已知图G如下，分析其割集、关联割。e113e3e4e5e6e7e82456割：图的割集加e3e4e6e8;e1e5e3e6e7等。2010-11-25204.1.4割和环3．基本割集基本割集(f-割集)：指的是在阶为r的连通图中，对应一个树t，有r个f-割集。每一基本割集只包含t的一条树支。1243e1e3e5e6e2e4[例]：已知完备图K4如下，确定一主树T及基本割集。解：1.求图的秩r：r=n−c=4−1=3，则图的任意树树支数为3。2.在图中，任取一树t=e1e4e3,对应于树支e1,e4,e3的三个基本割集是：C1=e1e2e6;C2=e2e4e5e6;C3=e2e3e5;2010-11-25214.1.5平面性和对偶性1.平面图定义：若一个图的几何图可以画在平面上，使其任意两条边不存在节点以外的交叉，则称该图为平面图。V1V2V3V4V1V2V3V4[例]：判断下两面两图是否为平面图？2．区域（窗口）平面图无交叉地展开到平面上，将平面分成若干个区域，这些区域也可以称为平面图的窗口。区域由边界的边表示，无边界的区域称为外区域。2010-11-25224.1.5平面性和对偶性推论：平面图满足：bqbGqii2)(=∑∈其中，b-图边数；qi—区域i。定理1：任何一个平面图都包括一个或多个内区域和一个外区域。定理2：对于有n个顶点，b条边和q个区域（包括外区域）的连通平面图，都满足欧拉公式：即n−b+q=2。推论2：一个节点数为n(n≥3),且不含并联边和自回路的平面图，其边数b的上限是3n-6。即：b≤3n-6；推论3：若平面图G节点数为n(n≥3)，且G不含并联边和自回路及长度为3的回路，则其边数上限是2n-4。2010-11-25234.1.5平面性和对偶性对偶图：在一个给定的平面图G的各区域（包括外区域）内各设置一个节点，当其中两个区域有公共边e时，就将两个区域内的节点用一条边e’连接，则{e’}和节点集所组成的图就称为图G的几何对偶图。1••2•3•4[例]：已知平面图G如下，求其对偶图。②确定对偶图的边。寻找图G每两个区域间的公共边baCdefg图Gf’234e’a’b’c’d’g’1图G的几何对偶图解：根据定义，归纳几何对偶图作法过程，包括以下3步：①确定对偶图节点。由于本图有4个区域，则其对偶图有4顶点；③重画图G的几何对偶图。2010-11-25244.1.6图的矩阵表示一、一、关联矩阵关联矩阵1.节点–边关联矩阵(Aa),又称关联矩阵或完备关联矩阵定义：用矩阵来表示图的节点与边关联关系。A0=[aij]n×b对有向图，⎪⎪⎩⎪⎪⎨⎧−=;ve0,;vve,1;vve1,ijiijiij不关联与若节点流入且方向指向关联与若节点流出且方向离开关联与若）（，）（，aij⎪⎩⎪⎨⎧=;ve0,;ve1,ijij不关联与若关联与若ija对无向图来说，2