《第4章通信网结构.pdf》由会员分享，可在线阅读，更多相关《第4章通信网结构.pdf（85页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2010-11-251通信网理论基础通信网理论基础通信网理论基础通信网理论基础通信网理论基础通信网理论基础1 1 引论（通信网概述）引论（通信网概述）引论（通信网概述）引论（通信网概述）2 2 网内业务分析网内业务分析网内业务分析网内业务分析3 3 多址接入系统分析多址接入系统分析多址接入系统分析多址接入系统分析4 4 通信网结构（图论基础）通信网结构（图论基础）通信网结构（图论基础）通信网结构（图论基础）5 5 通信网中的流量优化通信网中的流量优化通信网中的流量优化通信网中的流量优化6 6 通信网的可靠性通信网的可靠性通信网的可靠性通信网的可靠性Reference:1.Reference:1
2、.通信网理论基础通信网理论基础通信网理论基础通信网理论基础2.2.图图图图论及应用论及应用论及应用论及应用3.3.运筹学运筹学运筹学运筹学2010-11-252第四章通信网结构第四章通信网结构4.1 4.1 图论基础图论基础图论基础图论基础4.1.1 4.1.1 4.1.1 4.1.1 抽象图基本定义抽象图基本定义抽象图基本定义抽象图基本定义4.1.2 4.1.2 4.1.2 4.1.2 图的联结性图的联结性图的联结性图的联结性4.1.3 4.1.3 4.1.3 4.1.3 树树树树4.1.4 4.1.4 4.1.4 4.1.4 割和环割和环割和环割和环4.1.5 4.1.5 4.1.5 4.
3、1.5 平面图性和对偶性平面图性和对偶性平面图性和对偶性平面图性和对偶性4.1.6 4.1.6 4.1.6 4.1.6 图的矩阵表示图的矩阵表示图的矩阵表示图的矩阵表示4.2 4.2 最短路径问题最短路径问题最短路径问题最短路径问题4.2.1 4.2.1 4.2.1 4.2.1 最短主树最短主树最短主树最短主树4.2.2 4.2.2 4.2.2 4.2.2 端间的最短径端间的最短径端间的最短径端间的最短径4.3 4.3 站址问题站址问题站址问题站址问题4.3.1 4.3.1 4.3.1 4.3.1 单中点问题单中点问题单中点问题单中点问题4.3.2 k4.3.2 k4.3.2 k4.3.2 k
4、中点问题中点问题中点问题中点问题4.3.3 4.3.3 4.3.3 4.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 基本定义基本定义一、抽象图的定义一、抽象图的定义抽象图用点和边来反
5、映实际网络中的具体事物和事物间相互关系。抽象图用点和边来反映实际网络中的具体事物和事物间相互关系。无向图记为：无向图记为：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);无向图表示：无向图表示：or 2010-11-2564.1.1 抽象图的基本定义抽象图的基本定义二、抽象图常用术语二、抽
6、象图常用术语1.自环自环（或自回路）：两端点相同的边。（或自回路）：两端点相同的边。2.重边（或并联边，平行边）：两点间有多条边存在。如重边（或并联边，平行边）：两点间有多条边存在。如(i,j)1,(i,j)2,(i,j)k,k2,表示表示i，j节点间有节点间有k 条边存在。条边存在。3.关联关联：边边与连接它的与连接它的点点互称为关联。互称为关联。4.邻接邻接：连接一条边的：连接一条边的两节点两节点，互称为邻接点。，互称为邻接点。5.孤立节点图：只有点无边的图。孤立节点图：只有点无边的图。6.简单图：无环且无重边的图。简单图：无环且无重边的图。7.空图：无点无边的图。空图：无点无边的图。V=
7、，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所有节点的子图。所有节点的子图。例例：判断图G：判断图G1 1和G和G2 2是否是G 的子图？是否生成子图？是否是G 的子图？是否生成子
8、图？V1V2V3V4V5V2V4V5图图G 图图G1图图G2V2V4V5V1V32010-11-2584.1.1 抽象图的基本定义抽象图的基本定义三、集合相关的图描述：三、集合相关的图描述：2.两个图的运算两个图的运算：2个图的并，交，相差，环和运算。例个图的并，交，相差，环和运算。例:已知已知G1和和G2，求，求G1G2，G1G2，G1 G2，G1 G2及及G2 G1。fdce43ba21G1jicg45he3G2d2fdce43ba21G1G2jig5hdce432G1G2f3ba21G1 G2G2 G143jig5hf43ba21G1 G2jig5h2010-11-2594.1.2 图的
9、联结性（连通）图的联结性（连通）1.节点的度数节点的度数定义：图定义：图G中节点中节点i 的度数记为的度数记为d(i)，等于与该节点相关联的，等于与该节点相关联的边数边数。孤立节点的度数是。孤立节点的度数是0；若节点；若节点i为自环，则为自环，则d(i)=2;则：图中所有节点度数之和是边数则：图中所有节点度数之和是边数b的两倍，的两倍，=Nibid12)(211()()()Nij VkVd id kdj=+推论：设推论：设V1，V2分别表示图分别表示图G中顶点度数为奇数、偶数的两个点集，则且奇度节点的节点数为偶数。中顶点度数为奇数、偶数的两个点集，则且奇度节点的节点数为偶数。V1V2V4V5V
10、3e3e1e7e6e2e4e5e8e92010-11-25104.1.2 图的联结性（连通）图的联结性（连通）2.链、径和环链、径和环边序列边序列定义：由点、边交叉的有限序列定义：由点、边交叉的有限序列(i1,i2)，(i2,i3)，(ik-1,ik)称为长度为称为长度为K-1的边序（或通路）。的边序（或通路）。i1=ik，称闭合边序，否则称开放边序，在开放边序中，称闭合边序，否则称开放边序，在开放边序中，i1称为始点，称为始点，ik为终点，为终点，i1和和ik都称为边序的端点，其它节点称为内节点。都称为边序的端点，其它节点称为内节点。“手不离纸，一笔画成手不离纸，一笔画成”在一个边序中，同一
11、节点可重复出现，同一边也可以重复出现。在一个边序中，同一节点可重复出现，同一边也可以重复出现。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.链、径和环链、径和环链链定义：边序中无重复的边，则称这样的边序列为链。定
12、义：边序中无重复的边，则称这样的边序列为链。在一个链中，同一节点可重复出现，同一边不可以重复出现。在一个链中，同一节点可重复出现，同一边不可以重复出现。下图中下图中(V1,V2)(V2,V7)(V7,V1)(V1,V6)就是边不重、点重复的链。就是边不重、点重复的链。V2V3V4V5V6V7V1径径：点不重复的边序列。（边当然不重复）：点不重复的边序列。（边当然不重复）环环：起点和终点相同的链。闭链：起点和终点相同的链。闭链(V1,V7)(V7,V5)(V5,V6)(V6,V1)就是长度为就是长度为4 的回路，这也是一条闭径。的回路，这也是一条闭径。V2V3V4V5V6V7V12010-11-
13、25124.1.2 图的联结性（连通）图的联结性（连通）3.图的联结性图的联结性 点联结 点联结：若图：若图G中存在一中存在一路径路径P，u、v都是都是P上的节点，则称上的节点，则称u、v在在G 中点连通。中点连通。联结图 联结图：若图：若图G中任两节点都连通，则该图为连通图中任两节点都连通，则该图为连通图 连通片 连通片：图中含有最大边数的连通子图称为该图的连通片。记为：图中含有最大边数的连通子图称为该图的连通片。记为C(G)，简记为，简记为C。连通图。连通图C(G)=1；非连通图可分多个连通子图，；非连通图可分多个连通子图，C(G)1。例例：已知图：已知图G，求其连通片数。，求其连通片数。
14、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；当且仅当
15、图中只含一条回路时，图；当且仅当图中只含一条回路时，图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。正则图正则图：所端节点的度数相同的图，称为正则图。：所端节点的度数相同的图，称为正则图。两部图两部图：图的节点分为V：图的节点分为V1 1,V,V2 2集合，所有边两端分别桥接在此两节点集合中，完
16、备集合，所有边两端分别桥接在此两节点集合中，完备Km,n图。图。欧拉图欧拉图：各节点度数均为偶数的图。：各节点度数均为偶数的图。M图M图：图中只有2个节点的度数为奇数的图。：图中只有2个节点的度数为奇数的图。汉密尔顿H图汉密尔顿H图：图在至少存在1个环，经过所有节点。：图在至少存在1个环，经过所有节点。K3,2 图图2010-11-25154.1.3 树树1.树树不含回路的联结图称为树（不含回路的联结图称为树（tree）图）图。多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图。多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图。树图中的每一
17、个连通子图都称为森林（forest），树和森林中的边称为树枝。（a）树）树G（b）三个森林）三个森林2010-11-25164.1.3 树树树的特征：1).若图G是树图，则任意两顶点间必有一条且仅有一条通路必有一条且仅有一条通路。由于树图的连通的，所以树图中任意两顶点间必有通路，如果两顶点间有两条不同的通路存在，则必将出现回路，此与树的定义矛盾。2).树无环，但在树图中不相邻的两个顶点间添上一条边，则恰好得到一条回路（环）。3).设树G是有n个顶点的一棵树，那么树的边数为n1。4).除单点树外，树至少有2节点的度数为1。5).树图是连通且无回路的图，同时，树是二分图。2010-11-25174
18、.1.3 树树主树定义主树定义:如果如果T是图是图G的一个生成子图而且又是一棵树，则称的一个生成子图而且又是一棵树，则称T是图是图G的一棵主树，也称生成树（的一棵主树，也称生成树（spanning tree）。）。图图G4213e5e4e3e2e1234T31234T41234T21234T11主树的性质：主树的性质：1)T是连通图是连通图G的一棵主树的充要条件是：的一棵主树的充要条件是：T是是G的有的有n 1条边的连通生成子图。主树条边的连通生成子图。主树T的树枝数就是图的树枝数就是图G的阶的阶(G)。2)图图G有主树的充要条件是：图有主树的充要条件是：图G连通。连通。3)计算图的主树的各边
19、的加权值和，得到的一个和最小的主树称为最小重量生成树。计算图的主树的各边的加权值和，得到的一个和最小的主树称为最小重量生成树。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 中中最小数量最小数量的边集合构成
20、的子图，若移去这些边的边集合构成的子图，若移去这些边(全部全部)，将使图，将使图 G 的秩减的秩减 1（即连通片增加（即连通片增加1）。）。2)割边：割集中的每一条边，都称为这一割集的割边。割边：割集中的每一条边，都称为这一割集的割边。3)割边集（割）：图的割集或边不相接割集的并集称为割。割边集（割）：图的割集或边不相接割集的并集称为割。解：割集解：割集e1e2;e2e3e5;e1e3e5;e2e4e5;e1e4e5;e3e4;e6e8;e6e7;e7e8。e2例例：已知图：已知图G 如下，分析其割集、关联割。如下，分析其割集、关联割。e113e3e4e5e6e7e82456割：图的割集加e3
21、e4e6e8;e1e5e3e6e7等等。2010-11-25204.1.4 割和环割和环3 基本割集基本割集 基本割集基本割集(f-割集割集)：指的是在阶为：指的是在阶为r的连通图中，对应一个树的连通图中，对应一个树t，有，有r 个个 f-割集。每一基本割集只包含割集。每一基本割集只包含t 的一条树支。的一条树支。1243e1e3e5e6e 2e4例例：已知完备图：已知完备图K4如下，确定一主树如下，确定一主树T及基本割集。及基本割集。解：解：1.求图的秩求图的秩r：r=n c=4 1=3，则图的任意树树支数为，则图的任意树树支数为3。2.在图中，任取一树在图中，任取一树t=e1e4e3,对应
22、于树支对应于树支e1,e4,e3的三个基本割集是：的三个基本割集是：C1=e1e2e6;C2=e2e4e5e6;C3=e2e3e5;2010-11-25214.1.5 平面性和对偶性平面性和对偶性1.平面图定义：若一个图的几何图可以画在平面上，使其任意两条边不存在节点以外的交叉，则称该图为平面图。平面图定义：若一个图的几何图可以画在平面上，使其任意两条边不存在节点以外的交叉，则称该图为平面图。V1V2V3V4V1V2V3V4例例：判断下两面两图是否为平面图？：判断下两面两图是否为平面图？2 区域（窗口）平面图无交叉地展开到平面上，将平面分成若干个区域，这些区域也可以称为平面图的窗口。区域（窗口
23、）平面图无交叉地展开到平面上，将平面分成若干个区域，这些区域也可以称为平面图的窗口。区域由边界的边表示，无边界的区域称为外区域。区域由边界的边表示，无边界的区域称为外区域。2010-11-25224.1.5 平面性和对偶性平面性和对偶性推论：平面图满足：推论：平面图满足：bqbGqii2)(=其中，其中，b-图边数；图边数；qi 区域i。区域i。定理定理1：任何一个平面图都包括一个或多个内区域和一个外区域。：任何一个平面图都包括一个或多个内区域和一个外区域。定理定理2：对于有：对于有 n 个顶点，个顶点，b 条边和条边和 q 个区域（包括外区域）的连通平面图，都满足欧拉公式：即个区域（包括外区
24、域）的连通平面图，都满足欧拉公式：即 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 的各区域（包括外区域）内各设置的各区域（包括外区域）内各设置一个节点一个
25、节点，当其中两个区域有公共边，当其中两个区域有公共边e 时，就将两个区域内的节点用一条边时，就将两个区域内的节点用一条边e连接，则连接，则 e 和节点集所组成的图就称为图和节点集所组成的图就称为图 G 的几何对偶图。的几何对偶图。1 2 3 4例例：已知平面图：已知平面图 G 如下，求其对偶图。如下，求其对偶图。确定对偶图的 确定对偶图的边边。寻找图。寻找图G 每两个区域间的每两个区域间的公共边公共边baCdefg图图Gf 234eabcdg1图图G 的几何对偶图的几何对偶图解：根据定义，归纳几何对偶图作法过程，包括以下解：根据定义，归纳几何对偶图作法过程，包括以下3 步：确定对偶图节步：确定
26、对偶图节点点。由于本图有。由于本图有4 个区域，则其对偶图有个区域，则其对偶图有4顶点；重画图顶点；重画图G 的几何对偶图。的几何对偶图。2010-11-25244.1.6 图的矩阵表示图的矩阵表示一、一、一、一、关联矩阵关联矩阵关联矩阵关联矩阵1.节点节点边关联矩阵边关联矩阵(Aa),又称关联矩阵或完备关联矩阵又称关联矩阵或完备关联矩阵定义：用矩阵来表示图的节点与边关联关系。定义：用矩阵来表示图的节点与边关联关系。A0=aijn b对有向图，对有向图，=;ve 0,;vve,1;vve 1,ijiijiij不关联与若节点流入且方向指向关联与若节点流出且方向离开关联与若）（，）（，aij=;v
27、e0,;ve 1,ijij不关联与若关联与若ija对无向图来说，对无向图来说，2010-11-25254.1.6 图的矩阵表示图的矩阵表示例例：写出下图的关联矩阵：写出下图的关联矩阵A0,求图的阶和求图的阶和A0的秩。的秩。解解：确定图的节点数和边数图：确定图的节点数和边数图GA的节点数。的节点数。n(GA)=5，边数，边数b(GA)=8，阶为，阶为4。写出图的关联矩阵。写出图的关联矩阵A0如上。如上。01 1 0 0 1 0 0 00 1 1 0 0 1 0 0 1 0 0 1 0 0 0 1;0 0 1 1 0 0 1 00 0 0 0 1 1 1 1AGA=的e1e2e3e4e5e6e7
28、e81234543215e1e2e3e4e5e6e7e8图图GA完备关联矩阵具有下列性质：完备关联矩阵具有下列性质：1)图的关联矩阵的秩就是该图的阶。图的关联矩阵的秩就是该图的阶。2）阶为）阶为r的图的图G是连通的，当且仅当图是连通的，当且仅当图G的完备关联矩阵秩为的完备关联矩阵秩为r。2010-11-25264.1.6 图的矩阵表示图的矩阵表示2.基础关联矩阵基础关联矩阵(A)定义定义：若图：若图G含有含有b条边，阶为条边，阶为r，则图，则图G的基础关联矩阵的基础关联矩阵A是一个是一个r b矩阵，矩阵矩阵，矩阵A 的秩与图的秩与图G 的关联矩阵的关联矩阵Aa的阶都为的阶都为r。性质：图性质：
29、图G的主树（生成树）数目的主树（生成树）数目 S=|AAT|。例例：写出图：写出图GA的基础关联矩阵的基础关联矩阵A,并求并求A 的秩。的秩。43215e1e2e3e4e5e6e7e81 1 0 0 1 0 0 00 1 1 0 0 1 0 0 ;1 0 0 1 0 0 0 10 0 1 1 0 0 1 0AGA=的e1e2e3 e4e5e6e7e81234解：取节点解：取节点5为参考点，则为参考点，则2010-11-25274.1.6 图的矩阵表示图的矩阵表示二、二、二、二、割阵与环阵割阵与环阵割阵与环阵割阵与环阵1.割阵：若图割阵：若图G 有有b条边，条边，q 个非空割集，则割矩阵为个非空
30、割集，则割矩阵为Q=qijqxb，其中，其中，对无向图对无向图，=;ie0,;ie 1,jj中不在割若割边中在割若割边ijq=;e 0,;e,1;e 1,jjj中不在割路若割边且边方向与割方向相反中在割若割边且边方向与割方向一致中在割若割边i，i，iqij对有向图对有向图，基本割集矩阵基本割集矩阵Qf（又称（又称f-割集矩阵）：割集矩阵）：阶为阶为r的连通图的连通图G的割集矩阵中，对应于一组的割集矩阵中，对应于一组r个个f-割集的子矩阵割集的子矩阵Qf。其中，其中，基本割集基本割集(f-割集割集)：指的是在阶为：指的是在阶为r的连通图中，对应一个树的连通图中，对应一个树t，有，有r 个个 f-
31、割集。每一基本割集只包含割集。每一基本割集只包含t 的一条树支。的一条树支。2010-11-25284.1.6 图的矩阵表示图的矩阵表示2环阵环阵B(又称又称回路回路-边关联矩阵边关联矩阵)定义定义：若图：若图G 含有含有P 个回路，个回路，b 条边，则其回路矩阵条边，则其回路矩阵B=bijpxb对有向图，对有向图，=;ie0,;ie 1,jj中不在回路若边中在回路若边ijb=;e 0,;e,1;e 1,jjj中不在回路若边反且边方向与回路方向相中在回路若边致且边方向与回路方向一中在回路若边i，i，ibij对无向图来说对无向图来说，基本回路（又称为基本回路（又称为f回路）回路）：零度为：零度为
32、m的连通图的连通图G，它的每一个树对应着，它的每一个树对应着m个个f-回路，这回路，这m个回路称为基本回路或个回路称为基本回路或f-回路。每个回路。每个f-回路是该回路是该树和一条连支树和一条连支构成的回路。若连通图构成的回路。若连通图G零度零度 m，对应，对应G 中中m个基本回路，称个基本回路，称 Bf=bijmxb矩阵为矩阵为G 的基本回路矩阵的基本回路矩阵Bf，简称，简称 f-回路矩阵。回路矩阵。2010-11-25294.1.6 图的矩阵表示图的矩阵表示例例：已知图：已知图G及选定树及选定树T如下，写出如下，写出G的的A，Bf和和 Qf。图图Gdeb24c31aa12树树Tb3c4C1
33、C2C3解：解：1）对图）对图G中取树中取树T=abc，则补树为，则补树为de。取节点。取节点4为参考点。为参考点。2）对应树枝）对应树枝a，b，c，有向基本割集分别是：，有向基本割集分别是：3）对应连枝）对应连枝d，e，有向基本回路分别是：，有向基本回路分别是：edL1=abcd，L2=abe，方向与连枝方向一致。，方向与连枝方向一致。C1=aed，C2=bed，C3=cd，割集方向与树枝方向一致；，割集方向与树枝方向一致；2010-11-2530图图Gdeb24c31aa12树树Tb3c4C1C2C3ed以节点以节点4为参考点，行按节点为参考点，行按节点1,2,3排序，列按排序，列按d,e
34、,a,b,c排列，则排列，则1 1 1 1 0 1 1 1 0 0;0 1 0 1 1A=d e a b c1231 0 1 1 1 ;0 1 1 1 0fB=d e a b c1231 1 1 0 0 1 1 0 1 01 0 0 0 1fQ=d e a b c123基本回路基本回路L1=abcd，L2=abe，方向与各连枝方向一致。，方向与各连枝方向一致。基本割集基本割集C1=aed，C2=bed，C3=cd，方向与各树枝方向一致；，方向与各树枝方向一致；2010-11-25314.1.6 图的矩阵表示图的矩阵表示三、邻接矩阵三、邻接矩阵三、邻接矩阵三、邻接矩阵定义定义：在：在n个节点的网
35、个节点的网G(V,E)中，邻接矩阵中，邻接矩阵C=Cijnxn是一个是一个n行，行，n列的矩阵。对无向图，列的矩阵。对无向图，Cij=Cji。图图Gdeb24c31a0 1 1 00 0 1 0 ;0 0 0 10 1 0 0AGC=的1 2 3 41234解：图解：图G有有4节点，则节点，则C为为=无边到若有边到若jijivv,0vv,1ijC2010-11-25324.2 最短径问题最短径问题最短路径问题涉及网络拓扑结构优化和通信路由选择问题，研究：在给定局站和信道代价条件下确定最小费用联结网结构；根据网络结构如何选择局间最佳路由和备用路由。最短路径问题涉及网络拓扑结构优化和通信路由选择问
36、题，研究：在给定局站和信道代价条件下确定最小费用联结网结构；根据网络结构如何选择局间最佳路由和备用路由。1 弧的长度 弧的长度l(i，j)：在一个网G（V，E）中，V是节点集，E是弧集，设每条弧(i，j)都有一个相应的加权实数l(i，j),称它的弧长度。2 长度函数 长度函数：将弧集：将弧集E和加权实数联系起来的函数和加权实数联系起来的函数l称为长度函数。称为长度函数。3 有向路径长度 有向路径长度l（Pst）:若若Pst是是G中从节点中从节点s到节点到节点t的有向路径，的有向路径，l(Pst)就称为有向路径就称为有向路径Pst的长度。的长度。4 距离 距离：网中从节点：网中从节点s到节点到节
37、点t的最短有向路径的长度，称为该网节点的最短有向路径的长度，称为该网节点s到到t的距离的距离2010-11-25334.2 最短径问题最短径问题例例：已知网：已知网G（V，E，L）如下，求节点）如下，求节点1到节点到节点5的最长和最短路径长度。的最长和最短路径长度。解：节点解：节点1 5 有向路径：有向路径：P15(1),P15(2),P15(3),P15(4),P15(5),P15(6),P15(7)。1 1123451 12222344网网G（V，E，l）2010-11-25344.2.1 最短主树最短主树最短主树是一个网最短主树是一个网G中主树节点之间中主树节点之间路径总和路径总和最小问
38、题；分为无限制条件的最小问题；分为无限制条件的Prim和和Kruskal算法；有限制条件的穷举法、调整法（厄斯威廉算法；有限制条件的穷举法、调整法（厄斯威廉E-W）算法等。一、）算法等。一、Prim（普林姆）算法（普林姆）算法普林姆算法是从任一节点开始，构造一个非平凡蓝子树，过程：第普林姆算法是从任一节点开始，构造一个非平凡蓝子树，过程：第1步：取步：取G中任一节点作初始蓝子树中任一节点作初始蓝子树t0，置，置x=0；把与；把与t0关联的最小长度边关联的最小长度边(t0，y)着以着以浅蓝色，浅蓝色浅蓝色，浅蓝色边中最短着边中最短着蓝色蓝色；第；第2步：寻找蓝子树步：寻找蓝子树 tx的关联最小长
39、度边，着的关联最小长度边，着浅蓝色浅蓝色。第。第3步：在所有步：在所有浅蓝色浅蓝色边中，选择一条最小长度边边中，选择一条最小长度边(x，y)，着成，着成蓝色蓝色，若，若x是子树是子树tx中节点，中节点，(x tx)，置，置tx+1=txU(x，y)；2010-11-25354.2.1 最短主树最短主树P普林姆算法第普林姆算法第4步：步：若节点若节点 z tx+1，且不与浅蓝色边关联，把，且不与浅蓝色边关联，把(y，z)着为浅蓝色；着为浅蓝色；若蓝边不是生成树，返回 算法第若蓝边不是生成树，返回 算法第2 步，步，x=x+1；若是，算法结束。；若是，算法结束。v1101081177169.517
40、12919.5v2v4v3v6v51.取中取中v1节点为初始蓝子树节点为初始蓝子树t0，置，置x=0；与；与t0关联的最小长度边关联的最小长度边(t0，v2)和和(t0，v5)着以着以浅蓝色浅蓝色；2.在所有在所有浅蓝色浅蓝色边中，选择子树关联最小长度边边中，选择子树关联最小长度边(x，y)，着成，着成蓝色蓝色，若，若x是子树是子树tx中节点，中节点，(x tx)，置，置tx+1=txU(x，y)；依次为边（；依次为边（v1,v2),(v2,v3),(v3,v4),(v4,v6),(v4,v5）着）着蓝色蓝色。2010-11-25364.2.1 最短主树最短主树边权矩阵上的边权矩阵上的 Pri
41、m 算法算法(无向图无向图)：1、根据网路写出边权、根据网路写出边权邻接矩阵邻接矩阵C，两点间若无边，则用表示；，两点间若无边，则用表示；2、从、从 V1 开始标记，在第一行打开始标记，在第一行打 ，划去第一列；，划去第一列；3、从所有打、从所有打 的的行行（最后的列）（最后的列）中找出尚未划掉的最小元素，对该元素画圈，划掉该元素所在列，与中找出尚未划掉的最小元素，对该元素画圈，划掉该元素所在列，与该列数对应的行打 该列数对应的行打 ；4、若所有列都划掉，则已找到最小生成树、若所有列都划掉，则已找到最小生成树(所有画圈元素所对应的边所有画圈元素所对应的边)；否则，返回第；否则，返回第 3 步。
42、步。P算法复杂度（比较次数）：算法复杂度（比较次数）：1131()1(1)(2)(3)6(),nrr nrnnnO nn=+很大.2010-11-2537Prim矩阵法矩阵法V1V2V3V4V5V6 Prim算法是多项式算法，比较次数算法是多项式算法，比较次数O(n3)Prim算法可以求最大生成树算法可以求最大生成树 网路的边权可以有多种解释，如效率网路的边权可以有多种解释，如效率 次数受限的最小生成树次数受限的最小生成树尚无有效算法尚无有效算法 最小最小 Steiner 树树尚无有效算法尚无有效算法v1v4v6v3v5v2101081177169.51712919.597125.191798
43、10787111275.9165.195.9101710111610 V1V2V3V4V5V6v1v4v6v3v5v108779.522010-11-2538二、二、Kruskal（克鲁斯科）算法（克鲁斯科）算法Kruskal 算法：将图中所有算法：将图中所有边按权值从小到大排列边按权值从小到大排列，依次选所剩最小的边加入边集，依次选所剩最小的边加入边集 T，只要不和前面加入的边构成回路，直到，只要不和前面加入的边构成回路，直到T 中有中有 n 1 条边，则条边，则 T 是最小生成树。是最小生成树。复杂度复杂度n2log2(n)。例例：用：用Kruskal算法求图算法求图G(V，E，L)的一个
44、最小树。的一个最小树。解：按解：按G中相同长度边排序：中相同长度边排序：(3，6)(5，6)(1，2)(1，3)(2，4)(2，3)，长度均为，长度均为2。长度为长度为5(2，5)(5，7)2010-11-2539三、穷举法三、穷举法穷举穷举 算法：将图中所有支撑树找出，逐个筛选，找出最小支撑树，算法直观，但运算烦琐算法：将图中所有支撑树找出，逐个筛选，找出最小支撑树，算法直观，但运算烦琐。完备图的支撑树（主树）总数。完备图的支撑树（主树）总数 n n-2。置换法置换法：以图：以图G的的连枝置换连枝置换支撑树的支撑树的树枝树枝穷举穷举。例：例：求下图求下图G的所有支撑树（主树），并找出最小树。
45、的所有支撑树（主树），并找出最小树。图图G4213e4e3e2e1e513123T04213e4e2e1132解：解：1.图图G中找一棵支撑树中找一棵支撑树T0=e1,e2,e4。2.找找T0的基本割集。的基本割集。2010-11-2540穷举法之穷举法之 置换法置换法图图G4213e4e3e2e1e5131233.T0基本割集中任基本割集中任1条连枝置换树枝，得其它主树簇条连枝置换树枝，得其它主树簇T1，共，共4个主树，个主树，T1=t1；t2；t3和和t4。t1=e5,e2,e44213e4e2e5323t2=e1,e3,e44213e4e3e1112t3=e1,e2,e34213e3e2
46、e111t4=e1,e2,e54213e4e3e2e1e5133T0=e1,e2,e4基本割集：基本割集：Se1(t0)=e1,e5;Se2(t0)=e2,e3;Se4(t0)=e3,e4,e5;2010-11-2541穷举法之穷举法之置换法置换法t1=e5,e2,e44213e4e3e2e1e5131234.求求t1=e5,e2,e4基本割集：基本割集：Se5(t1)=e5,e1;Se2(t1)=e2,e3;Se4(t1)=e1,e4,e3;求求t1与与t0割集的非空交集。割集的非空交集。T0=e1,e2,e4基本割集：基本割集：Se1(t0)=e1,e5;Se2(t0)=e2,e3;Se4
47、(t0)=e3,e4,e5;交集如下，其中交集如下，其中e3是连支。是连支。102133202444()(),;()(),eeeeststetestsee=IIe1t5=e5,e3,e44213e4e3e2e513123t6=e5,e2,e34213e4e3e2e513123e1e3分别置换分别置换t1中树支中树支e2、e4得到树得到树T2簇部分，簇部分，T21=t5，t6。2010-11-2542穷举法之穷举法之 置换法置换法t2=e1,e3,e44.求求t2=e1,e3,e4基本割集：基本割集：Se1(t2)=e1,e5;Se3(t2)=e2,e3;Se4(t2)=e2,e4,e5;求求t
48、2与与t0割集的非空交集。割集的非空交集。T0=e1,e2,e4基本割集：基本割集：Se1(t0)=e1,e5;Se2(t0)=e2,e3;Se4(t0)=e3,e4,e5;交集如下，其中交集如下，其中e5是连支。是连支。101155101444()(),;()(),eeeeststetestsee=II4213e4e3e2e1e513123e5分别置换分别置换t2树支树支e1，e4得主树得主树T2簇部分，簇部分，T22=t7，t8。e1t7=e5,e3,e4=t54213e4e3e2e513123t8=e1,e3,e54213e4e3e2e513123e12010-11-2543穷举法之穷举
49、法之置换法置换法继续求继续求t3、t4基本割集，然后求它们分别与基本割集，然后求它们分别与t0割集的非空交集，即求距离为割集的非空交集，即求距离为2的主树簇，结果与前面已找到树重合。本题主树最大距离为的主树簇，结果与前面已找到树重合。本题主树最大距离为2，算法结束。然后根，算法结束。然后根据限制条件从主树中选取据限制条件从主树中选取。t04213e4e2e1132t14213e4e2e5323t24213e4e3e1112t34213e3e2e111t44213e4e3e2e1e5133t54213e4e3e5123t64213e3e2e5313t84213e3e5113e12010-11-2
50、544四、调整法四、调整法调整调整算法：准最佳解算法：准最佳解，以以Esau-William算法为例算法为例(解决解决1种特定问题种特定问题)13254kn问题：问题：图图G有有n个站，其中已知个站，其中已知v1是主机，已知各边间距离是主机，已知各边间距离dij，各个端站业务量，各个端站业务量Fi（i，j=1，2，n），要求任意端至），要求任意端至v1的径边数的径边数K（限转接次数限转接次数K-1)，且径上总业务量，且径上总业务量M，(其中其中K为给定的整数，为给定的整数，M为给定的实数为给定的实数)，求最短支撑树。，求最短支撑树。算法思想算法思想：用贪心法原则，逐步用边替换：用贪心法原则，逐