当前位置：文档库 › 图论在通信网中的应用

图论在通信网中的应用

5.3.6 图论在通信网中的应用

网络可靠性是评价网络是否稳定工作的一个非常重要的指标。而网络可靠性的衡量取决于网络的两个重要的指标——结合度和连通度。下面主要就结合度和连通度的定义及其计算作简要描述，并以一个例子加以说明。

1. 网络的结合度和连通度的定义

1）结合度：网络G 的结合度又称为边连通度，记为()L G ，其大小等于使网络成为不连通图所需去掉链路（边）的最少条数。它反映网络节点间的内聚程度，是网络可靠性的一个基本度量指标。例如, 通过观察易知,图5.29所示的网络的结合度()3L G =。

图5.29

2）连通度：网络G 的连通度又称为点连通度，记为()K G ，其大小等于使网络成为不连通图所需去掉的节点的最少个数。例如，图5.29所示的网络的连通度()2K G =。从某种意义上讲，点连通度是比边连通度更重要的网络可靠性度量指标，这是因为在网络中去掉某个节点

就意味着与之关联的所有链路将失去意义。

2. 网络结合度和连通度的算法 1）算法基本思想

通常，要求给定网络(,)G V E =的结合度，需要首先确定任意不同两点的链路割集。设i v 和j v 是的两个不同节点，所谓G 的一个i j v v -链路割集是指这样的链路集合：若去掉其中所有链路，网络G 将被分割成两个分支，一个包含节点i v ，另一个包含节点j v 。假设

ij L 是G 中所有i j v v -链路割集中链路的最小数，则ij L 就是切断i v 和j v 之间所有路由所需

从G 中删去的最小链路数，故网络G 的结合度()L G 可按下式计算：

,,()m in

i j i j

ij v v V v v L G L ∈≠=

与确定结合度的方法类似，求给定网络(,)G V E =的连通度，则需要首先确定任两个不同节点间的节点割集。设i v 和j v 是的两个不同节点，G 的一个i j v v -节点割集是指这样

的一个节点集合：若去掉其中所有节点，网络G 将被分割成分别包含节点i v 和节点j v 的两个分支。假设ij K 是G 中所有i j v v -节点割集中节点的最小数，则网络G 的连通度()K G 可按下式计算：

,,()m in

i j i j

ij v v V v v K G K ∈≠=

2）算法基本步骤

由图论中的Menger 定理知，分离任意两点的最小链路数等于最小割的容量（每条弧的容量为1）。因此，通过改进网络最大流算法可以计算出分离任意两点的最小链路数。下面先给出计算分离网络任意两点的最小链路数的标号算法，然后给出计算网络结合度和连通度的一般步骤。

（1）计算任意两点的最小链路数的标号算法

在网络(,,)G V A C =中，设容量集C 中任一弧的容量ij c 均为1，s v 和t v 分别是G 的发点和收点，st L 是切断s v 与t v 的最小链路割集的链路数（最小割量）。对网络最大流标号算法稍做改进，可得如下求st L 的标号算法。

第1步：标号过程

A) 对所有(,)i j v v ，令0ij f =； B) 给发点s v 以标号(,)o ∞；

C) 选择一个已标号但未检查的顶点i v ，对于i v 的所有未给标号的邻接点j v 按下列规则处理：

(a) 对边(,)i j v v E ∈，若0ij f =，则给j v 标号； (b) 对边(,)j i v v E ∈，且1ji f =，则给j v 标号(,)i v -。

D) 重复C)直到收点t v 被标号或不再有顶点可标号时为止。

如若t v 得到标号，则说明存在一条可增广链，转（第2步）调整过程。若t v 未获得标号，标号过程已无法进行时，则算法结束，此时已得到分离s v 和t v 的最小链路割集的链路数st L ，其值为

(,)s j st sj v v E

L f ∈=

∑

第2步：调整过程先按各点标号从反向追踪找到增广链μ，再令

1,1,,ij i j ij ij i j ij

i j f v v f f v v f v v μμμ?+∈??'=∈?????+-()－()() 去掉所有标号，回到第1步，对新的可行流f '重新标号。

2）网络结合度计算步骤

由前所述，计算网络结合度的算法思路是：先按标号算法求分离任两点的最小链路数，然后，再求所有这些数的最小数即可。但是，上述求st L 的算法是针对有向图给出的，而网络结合度是针对无向图的，因此，算法需首先将原无向网络转换成等效的有向网络。具体计算步骤如下：

第1步：对给定网络(,)G V E =，任选一对节点s v 和t v ，按下面的步骤求分离s v 和t

v 的最小链路数st L ：

① 首先将(,)G V E =转换成有向图(,)G V A '=。方法是：将链路集E 中以s v 为端点的链路转换成A 中以s v 为起点的到相应节点的有向链路，将E 中以t v 为端点的链路转换成

A 中从相应节点到节点s v 的有向链路，又将E 中其他链路(,)i j v v 转换成A 中2条有向链

路(,)i j v v 和(,)j i v v 。这种转换如图5.30所示。

s v ?

v j

v s v

(a) (b)

图5.30 无向网络转换成有向网络

(a) 原无向网络(,)G V E =； (b) 相应的有向网络(,)G V A '=

② 用标号算法，求(,)G V A '=中分离s v 与t v 的最小链路数st L 。

第2步：对所有节点对(,)i j v v ，i j <，重复上述步骤计算ij L ，最后计算：

,,()m in

i j i j

ij v v V v v i j

L G L ∈≠<=

，()L G 即网络的结合度。

需要注意的是，由于ij ji L L =，对于含有n 个节点的图，第2步中需要计算的ij L 共有(1)2n n -个。

3）网络连通度计算步骤

算法的思路是：将割点问题转换成割边问题，从而使求网络连通度的问题转换成求网络的结合度问题。转换的方法是：在网络(,)G V E =中任选一对节点s v 和t v ，首先，类似于结合度算法一样，将(,)G V E =转换成有向网络(,)G V A '=，然后，再将(,)G V A '=构

造另一个有向图???(,)G V A =，构图规则是：将V 中除s

v 和t v 外的每个节点i v 拆成2个新的?G 中的节点1i v 和2i v ，并用?A 中的有向链路12

(,)i i v v 将它们连接起来。将A 中每一链路(,)j i v v 换成?A 中的链路21(,)j i v v ，并把s

v 标为2s v ，t v 标为1t v ，这种转换如图5.31所示。它由图5.30继续转换得来。

t v 2

j 1

图5.31 割点集转换成割链集

由构图规则可知，在新的网络?G 中，从发点到收点的包含节点i

v 的一条路由，必定包含一个顶点拆成的两部分之间的那条弧。并且原图G 的一对相邻点及其间的边(,)i j v v 被转换成等效的由4个节点组成的“8”字形有向回路1

{,,,,}i i j j i v v v v v 。因此，一个链路割集在

切断?G 中2

s v 到1

t v 的所有有向路由方面，与在原始无向图G 中去掉s t

v v -节点割集有相同作用，即G 中st K 等于?G 中21

s t

L 。综上述，可得网络连通度算法计算步骤如下。第1步：对原网络(,)G V E =的任一节点对s v 和t v ，按上述规则构造新的有向网络???(,)G V A =，并用标号法求?G 中分离2s v 和1t v 的最小链路数21s t L ，即G 中分离s

v 和t v 的最小割点集点数st K 。

第2步：对所有节点i j <，计算()m in ij i j

K G K <=，即得G 的结合度。

例5.21 计算如图5.32所示5点网络的结合度和连通度。

???1

234

图5.32

解：1）结合度计算：

设发点为1、收点为4，下面求分离发点1收点4的最小链路数14L ：首先将无向网络转换成有向网络，见图5.33。

图5.33

按前述的计算任意两点的最小链路数的标号算法，容易计算得到143L =。类似地，计算12L ，13L 等等，有：

1213152324253435453L L L L L L L L L =========

所以，该5节点网络的结合度m in{,15}3ij L L i j =≤<≤=。

2）连通度计算：

设发点为1、收点为4，先将原无向图按所述规则转换成有向图，如图5.34。

112

图5.34

按前述的计算任意两点的最小链路数的标号算法，容易计算得到143K =。类似地，可以求出：

1213152324253435453K K K K K K K K K =========

所以，该5节点网络的连通度m in{,15}3ij K K i j =≤<≤=。

3. 通信网的组建原则

一个通信网中，从网络拓扑来考虑，当L 和K 的值越大时，该网络越可靠，当然其造价越贵，这里的造价可能是通信线路的建设费，也可能是通信线路的租用费。如果仅从可靠性角度来看，怎样组网才能取得较大的结合度和连通度呢？具体来说，给定n 个通信节点，要用m 条通信链路将其连接，那么，怎样组网才能使其可靠性最好？由于网络是连通的，它至少应含有树。因n 个顶点的树，其链路为1n -，故1m n ≥-。并且由图论的有关定理，有如下结论：

设()L G 和()K G 分别是网络(,)G V E =的结合度和连通度，n 是G 的节点总数，m 是

G 的链路总数，d 是G 的所有节点的最小次数，则()()[2]K G L G d m n ≤≤≤，其中

[2]m n 表示不超过2m n 的最大整数。当图为正则图时，()()L G K G =。

由该结果，可得以下关于网络组建的几个原则性结论：

① 在给定节点数n 链路数m 的前提下，应尽可能使网络结合度和连通度最大。但其值最大不会超过2m n ，后者称为网的冗度。

② 给定n 和m ，组网方式不同，其连通度一般也不一样。通常应尽量使链路均匀分布于各节点。

③ 对给定的网络G ，其最小链路割集的所有链路和最小节点割集的所有节点，是网络组建的“瓶颈”，它们被破坏时将会严重破坏网的连通性。因此，在组网时要引起高度重视。

电子科技大学研究生试题《图论及其应用》(参考答案)

电子科技大学研究生试题《图论及其应用》(参考答案) 考试时间：120分钟一．填空题(每题3分，共18分) 1．4个顶点的不同构的简单图共有__11___个； 2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。则G 中顶点数至少有__9___个； 3．设n 阶无向图是由k(k ?2)棵树构成的森林，则图G 的边数m= _n-k____; 4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_. 5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。图G 二．单项选择(每题3分，共21分) 1．下面给出的序列中，是某简单图的度序列的是( A ) (A) (11123); (B) (233445); (C) (23445); (D) (1333). 2．已知图G 如图所示，则它的同构图是（ D ） 3．下列图中，是欧拉图的是（ D ） 4．下列图中，不是哈密尔顿图的是（B ） 5．下列图中，是可平面图的图的是（B ） A C D A B C D

6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ）三．作图(6分) 1．画出一个有欧拉闭迹和哈密尔顿圈的图； 2．画出一个有欧拉闭迹但没有哈密尔顿圈的图； 3．画出一个没有欧拉闭迹但有哈密尔顿圈的图；解：四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。解：由克鲁斯克尔算法的其一最小生成树如下图：权和为：20. 五．(8分)求下图G 的色多项式P k (G). 解：用公式 (G P k -G 的色多项式： )3)(3)()(45-++=k k k G P k 。六．(10分) 22，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。解：设该树有n 1个1度顶点，树的边数为m. 一方面：2m=n 1+2n 2+…+kn k 另一方面：m= n 1+n 2+…+n k -1 v v 1 3 图G

图论在通信网中的应用

5.3.6 图论在通信网中的应用网络可靠性是评价网络是否稳定工作的一个非常重要的指标。而网络可靠性的衡量取决于网络的两个重要的指标——结合度和连通度。下面主要就结合度和连通度的定义及其计算作简要描述，并以一个例子加以说明。 1. 网络的结合度和连通度的定义 1）结合度：网络G 的结合度又称为边连通度，记为()L G ，其大小等于使网络成为不连通图所需去掉链路（边）的最少条数。它反映网络节点间的内聚程度，是网络可靠性的一个基本度量指标。例如, 通过观察易知,图5.29所示的网络的结合度()3L G =。 ? ? ?? ?? ?? 图5.29 2）连通度：网络G 的连通度又称为点连通度，记为()K G ，其大小等于使网络成为不连通图所需去掉的节点的最少个数。例如，图5.29所示的网络的连通度()2K G =。从某种意义上讲，点连通度是比边连通度更重要的网络可靠性度量指标，这是因为在网络中去掉某个节点就意味着与之关联的所有链路将失去意义。 2. 网络结合度和连通度的算法 1）算法基本思想通常，要求给定网络(,)G V E =的结合度，需要首先确定任意不同两点的链路割集。设i v 和j v 是的两个不同节点，所谓G 的一个i j v v -链路割集是指这样的链路集合：若去掉其中所有链路，网络G 将被分割成两个分支，一个包含节点i v ，另一个包含节点j v 。假设 ij L 是G 中所有i j v v -链路割集中链路的最小数，则ij L 就是切断i v 和j v 之间所有路由所需从G 中删去的最小链路数，故网络G 的结合度()L G 可按下式计算： ,,()m in i j i j ij v v V v v L G L ∈≠= 与确定结合度的方法类似，求给定网络(,)G V E =的连通度，则需要首先确定任两个不同节点间的节点割集。设i v 和j v 是的两个不同节点，G 的一个i j v v -节点割集是指这样

答案(电子科大版)图论及其应用第一章

习题一： ● 。证明:作映射f : v i ? u i (i=1,2….10) 容易证明，对?v i v j ∈E ((a)),有f (v i v j,),=,u i,u j,∈,E,((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图(a)与(b)是同构的。 ● 5.证明：四个顶点的非同构简单图有11个。证明：设四个顶点中边的个数为m ，则有： m=0: m=1 ： m=2： m=3： m=4： (a) v 23 4 (b)

m=5： m=6：因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。 ● 11.证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1）不是图序列。证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,2）不是图序列；（6,6,5,4,3,3,1）是图序列 1 1 12312(1,1,,1,,,)d d n d d d d d π++=---是图序列（5,4,3,2,2,0）是图序列，然而（5,4,3,2,2,0）不是图序列，所以（6,6,5,4,3,3,1）不是图序列。 ● 12.证明：若，则包含圈。证明：下面仅对连通图的下的条件下进行证明，不连通的情形可以通过分成若干个连通的情形来证明。设 , 对于中的路若与邻接，则构成一个闭路。若是一条路，由于，因此，对于，存在与之邻接，则构成一个圈。 ● 17.证明：若G 不连通，则连通。证明：对于任意的 ,若与属于G 的连通分支，显然与在中连通；

图论及其应用答案电子科大

图论及其应用答案电子科大 This model paper was revised by the Standardization Office on December 10, 2020

习题三：证明：e是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u，v）必含e . 证明：充分性: e是G的割边，故G ?e至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G中的u ,v不连通，而在G中u与v连通，所以e在每一条(u ,v )路上，G中的(u ,v )必含e。必要性：取12,u V v V ∈∈，由假设G中所有(u ,v )路均含有边e，从而在G ?e中不存在从 u与到v的路，这表明G不连通，所以e 是割边。 3.设G 是阶大于2的连通图，证明下列命题等价：（1） G 是块（2） G 无环且任意一个点和任意一条边都位于同一个圈上；（3） G 无环且任意三个不同点都位于同一条路上。（1）→（2）： G是块，任取G的一点u，一边e，在e边插入一点v，使得e成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G中的u,v 位于同一个圈上，于是G 1中u 与边e都位于同一个圈上。（2）→（3）： G无环，且任意一点和任意一条边都位于同一个圈上，任取G的点u ，边e ，若u在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u不在e上，由定理，e的两点在同一个闭路上，在e边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。（3）→（1）： G连通，若G不是块，则G中存在着割点u，划分为不同的子集块V 1, V 2, V 1, V 2无环，12,x v y v ∈∈，点u在每一条(x ,y )的路上，则与已知矛盾，G是块。 7.证明：若v 是简单图G 的一个割点，则v 不是补图G ?的割点。证明：v是单图G的割点，则G ?v有两个连通分支。现任取x ,y ∈V (G ?v ), 如果x ,y 不在G ?v的同一分支中，令u是与x ,y处于不同分支的点，那么，x ,与y在G ?v的补图中连通。若x ,y在G ?v的同一分支中，则它们在G ?v的补图中邻接。所以，若v是G 的割点，则v不是补图的割点。 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给出相应的最小点割和最小边割。解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）}

图论应用案例

题目：最小生成树在城市交通建设中的应用姓名：学号：指导老师：专业：机械工程 2014年3月16

目录摘要..................................................................................... 错误！未定义书签。 1 绪论 (1) 2 有关最小生成树的概念 (2) 3 prim算法介绍 (3) 4 系统设计及其应用 (5) 一、系统设计 (5) 二、最小生成树应用 (8) 5 总结 (11) 参考文献 (12) 附件： (13)

最小生成树在城市交通建设中的应用摘要：连通图广泛应用于交通建设，求连通图的最小生成树是最主要的应用。比如要在n个城市间建立通信联络网，要考虑的是如何保证n点连通的前提下最节省经费，就应用到了最小生成树。求图的最小生成树有两种算法，一种是Prim（普里姆）算法，另一种是Kruskal（克鲁斯卡尔）算法。本文通过将城市各地点转换成连通图，再将连通图转换成邻接矩阵。在Microsoft Visual C++上，通过输入结点和权值，用普里姆算法获得权值最小边来得到最小生成树，从而在保证各个地点之间能连通的情况下节省所需费用。本文从分析课题的题目背景、题目意义、题目要求等出发，分别从需求分析、总体设计、详细设计、测试等各个方面详细介绍了系统的设计与实现过程，最后对系统的完成情况进行了总结。关键字：PRIM算法、最小生成树、邻接矩阵、交通建设

Abstract Connected graph is widely applied in traffic construction, connected graph of minimum spanning tree is the main application.Such as to establish a communication network between the n city, want to consider is how to ensure n points connected under the premise of the most save money, apply to the minimum spanning tree. O figure there are two kinds of minimum spanning tree algorithm, one kind is Prim (she) algorithm, the other is a Kruskal algorithm (Kruskal). In this article, through the city around point into a connected graph, then connected graph is transformed into adjacency matrix.On Microsoft Visual c + +, through the input nodes and the weights, gain weight minimum edge using she algorithm to get minimum spanning tree, which in the case of guarantee every location between connected to save costs. Based on the analysis topic subject background, significance, subject requirements, etc, from requirements analysis, general design, detailed design, testing, and other aspects detailed introduces the system design and implementation process, finally the completion of the system are summarized. Key words: PRIM algorithm, minimum spanning tree, adjacency matrix, traffic construction

离散数学试卷及答案(2)

一、填空 20% （每小题2分） 1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为；“虽然你努力了，但还是失败了”的翻译为。 2、论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为。 2、设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是。 3、设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R= （列举法）。 R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ； A 上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c}, 则幺元是；是否有幂等性；是否有对称性。 7、4阶群必是群或群。 8、下面偏序格是分配格的是。

9、n 个结点的无向完全图K n 的边数为，欧拉图的充要条件是。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为。二、选择 20% （每小题2分） 1、在下述公式中是重言式为（） A ．)()(Q P Q P ∨→∧； B ．))()(()(P Q Q P Q P →∧→??； C ．Q Q P ∧→?)(； D ．)(Q P P ∨→ 。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（），成真赋值的个数为（）。 A ．0； B ．1； C ．2； D ．3 。 3、设}}2,1{},1{,{Φ=S ，则 S 2 有（）个元素。 A ．3； B ．6； C ．7； D ．8 。 4、设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产生的S S ?上一个划分共有（）个分块。 A ．4； B ．5； C ．6； D ．9 。 5、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为