没有合适的资源?快使用搜索试试~ 我知道了~
图论.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 77 浏览量
2023-03-13
20:58:04
上传
评论
收藏 532KB DOCX 举报
温馨提示
试读
20页
。
资源推荐
资源详情
资源评论
5.3 图论
5.3.1 基本概念
作为一门应用数学,图论已经被广泛地应用到复杂网络的研究中。 图论研究的是人们
在自然界和社会生活中遇到的包含某种二元关系的问题或系统,并把这种问题或系统抽象
为点和线的集合。通信网是由终端节点、业务节点和传输链路组成的,从数学模型来说,
这就是一个图论的问题,其中点表示通信网中的节点,线表示传输链路。在通信网规划中,
图论可以用于确定最佳网络结构、选择路由、分析网络可靠性等。
1. 图的概念
1) 定义
定 义 1 图 是 一个 有 序 二 元 组
, 其 中
称 为 点 集 ,
G (V , E )
V
v , v , , v
1
2
n
称为边集。一个图所对应的几何图形不是唯一的。故一般要求明确边集
E e , e , , e
1
2
m
中任一边 是连接哪两个点,且点集 非空。
E
e
V
j
2)分类
给定图
,设两个点 ,
,若边
,则称 , 两点相邻。
(v , v ) E
v v
G (V , E )
V
v
v
i
j
i
j
i
j
, 称为边
的端点。两条边
,若它们有一个公共端点 ,则称
相
e , e
v
v
(v , v )
i
e , e E
v
i
j
j
i
j
i
j
邻。称边
为点 v 的关联边。对于 中任一边
,若边
端点无序,则它是
(v , v )
e , e
i
E
(v , v )
j
j
i
i
j
无向边,此时图 G 称为无向图;反之,若边
(v , v )
端点有序,则它是有向边(或称为弧),
i
j
此时图 G 称为有向图。某条边的两个端点重合,则称该边为环(自回路);若两点间多于一
条边,则称具有多重边。无环无多重边的图称为简单图,含有多重边的图称为多重图。本
节研究的主要是简单图。对于无向图
G (V , E )
,定义顶点v 的次(或度)为:以点v 为端
点的边数称为点 v 的次(或度),记作
deg( v)
,或简记为
d( v)
;对于有向图,点的次有入次
和出次,其定义与无向图相似。出次与入次之和为边数总和的 2 倍。从通信的角度看,如
果以点代表局站,以边表示出/入局路由,则点的次越大,意味着局站出/入口路由越多。
次为 1 的点称为悬挂点,连结悬挂点的边称为悬挂边。次为零的点称为孤立点。次为
偶数的点称为偶点,次为奇数的点称为奇点。
3)链路、路径、回路
图
,其中
条边与同其相连的点依次排成点和边的交替序列,则称
m (m 2)
G (V , E )
该序列为链路;若链路中不出现重复的边,则称其为路径,若路径的起点和终点重合,则
称为回路。
4)赋权图
每边赋以某一实数,则称该图为赋权图(或加权图)。所赋实数为边的权值,权值可以
代表不同的含义,如距离、流量、时间、费用等。对不同的实际问题赋权图具有不同的实
际意义。此外,还有点赋权、边(弧)赋权等。赋权图也称为网络,故网络有无向网络与
有向网络之分。
5)连通图
对于图
,若任意两点之间都至少存在一条路径,则 为连通图,否则为非
G
G (V , E )
连通图。
6)几种特殊的图
完全图:指任意两点间都有一条边的无向图。比如通信网中的网状网结构就构成了完
全图。
正则图;指所有点的次均相等的连通图。目前在传输网中应用较为广泛的 SDH 环形结
构所构成的图就是正则图。
7)子图
给定图
和图
,若 ,则称 为 的子图,而称
V V ,E E
G G
G (V , E )
G (V , E )
为 的母图,特殊地,若
,则称 为 的支撑子图(生成子图)。
V , E E
G G
G
G
V
8)树
定义:无回路的连通图称为树。树中次为1 的点称为树叶,次大于 1 的点称为分枝点。
①树的性质:
a)有 个点的树共有
条树枝;
(n
1)
n
b)树中任意两点之间只存在一条路径;
c)树是连通的,但去掉任一边即不连通;
d)树无回路,但增加一条边便可得到一个回路;
e)除单点树外,树至少有两个端点度数为 1。
由树的性质可以看出,树是可靠性最差的网络结构图,但由于投资小,通信网在建网
初期,多采用树形结构。发展到一定时期后,树形结构显现出了在安全性方面的不足,这
时网络会根据具体情况,引入完善机制,如形成环路保护等。
② 图的支撑树
如果图 G 的生成子图是一棵树,则称该树为 G 的支撑树(或生成树)。只有连通图才
有支撑树,有支撑树的图必为连通图。
满足一定条件的权值之和为最小的支撑树称为最小支撑树。对于一个连通图而言,如
果它本身不是一棵树,那么它的支撑树将不止一个,而最小支撑树至少存在一个。
寻找最小支撑树是一个常见的优化问题,目的是寻找保证一定连通性条件的最简化的
网络结构。
2. 图的矩阵表示
图的几何表示具有直观性,但在数值计算和分析时,需借助于矩阵表示。用矩阵表示
图对研究图的性质及应用常常比较方便,其最大优点是可以利用计算机进行运算。图的矩
阵表示方法主要有关联矩阵、邻接矩阵和权值矩阵等三类。
1)完全关联矩阵与关联矩阵
关联矩阵:表达点与边关联性的矩阵。
完全关联矩阵:具有 个点、 条边的图 ,其完全关联矩阵
是以每点为一行、
n
m
G
M (G )
每边为一列的 矩阵,即:
n m
。对于无向图,有:
m
顶点与边的关联
M (G )
[m ]
ij n m
ij
1,
e
是 的 起 点
v
0
i
j
次数=0,1,2。对于有向图,有:
m
。
,
v 与 e 不 关 联
ij
i
j
- 1 , v 是 e 的 终 点
i
j
例如与图 5.13 中的图
G (V , E )
相对应的关联矩阵为
e e e e e e e
5
1
2
3
4
6
7
1 1 0 0 1 0 1 v
1
2
3
4
1 1 1 0 0 0 0 v
M (G )
0 0 1 1 0 0 1 v
0 0 0 1 1 2 0 v
v
6
e
1
1.5
v
4
v
1
6
3
2
v
1
3
5
3
e
5
e
1.5
6
v
v
5
v
v
4
e
4
4
4
3
图 5.13
图 5.14
从无向图的关联矩阵可以很容易地看出点与边的关系,关联矩阵每一行元素的和等于
对应节点的次,每一列元素的和一定等于 2。
类似地,可以得出有向图的关联矩阵。从有向图的关联矩阵也很容易看出点与边的关
系,该关联矩阵每行元素为 1 的个数等于对应节点的出次,元素为一 1 的个数等于对应节
点入次之和,每列元素的和一定为 0。
2)邻接矩阵
邻接矩阵用于表示点与点之间的关系,用
表示。对于有n 个节点的图G ,
A(G )
A(G )
是一个 n n 的方阵,记作
A(G ) [a ]
,其中,
a
连接 与 的边数。无向简单图的
v
v
i
ij n n
ij
j
邻接矩阵是对称的,即 a a ,并且对角元素为 0,每行或每列之和为该行或列对应节点
ij
ji
的次。有向简单图的邻接矩阵对角元素也为 0,但不一定对称,其每行上 1 的个数是该行对
应节点的出次,每列上 1 的个数为该列对应节点的入次。
图 5.13 的邻接矩阵为:
v v
1
v
v
2
3
4
0 2 1 1 v
1
2
3
4
2 0 1 0 v
A(G )
1 1 0 1 v
1 0 1 1 v
3)权值矩阵
权值矩阵表明了点与点之间的相邻关系及相隔距离的关系,用
表示,它与邻接
W (G )
矩阵有类似性。
对于有 个节点的简单图 ,其权值矩阵
W (G ) [w ]
,其中
n
G
ij n n
d , (v , v ) E
ij
i
j
w , (v , v ) E
ij
i
j
0,
i j
无向简单图的权值矩阵是对称的,对角线元素为零。有向简单图的权值矩阵对角线元
素也为零,但不一定是对称的。
图 5.14 权值矩阵为:
v
v
v
v
v
v
1
2
3
4
5
6
0
2
0
4
5
3
4
1.5
v
1
2
3
4
5
6
v
2
5
3
3
4
0
1.5 v
W (G )
3
0
v
1.5
4
0
6 v
1.5
6
0
v
5.3.2 最小生成树问题
许多网络问题都可以归结为最小树问题。例如,设计长度最短的公路网把若干城市联
系起来;设计用料最省的通信网把有关站点联系起来等等。
下面介绍最小树的两种算法。
算法 1 (Kruskal 算法)
Kruskal 算法也称避圈法,基本步骤如下:
将树的各边的权值按大小顺序排列;每步从未选的边中选取边 e ,使它与已选边不构
成环,且 e 是未选边中的最小权边,直到选够 n 1 条边为止。
可以证明,用 Kruskal 算法得到的子图是一棵最小树。
算法 2(破圈法)
破圈法的依据是:若图 的生成树 为最小树,当且仅当对任一弦 e 来说,e 是 + e
G
T
T
中与之对应的圈中的最大权边。(证明略)
其基本步骤:
剩余19页未读,继续阅读
资源评论
คิดถึง643
- 粉丝: 3917
- 资源: 1万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- Screenshot_2024-05-28-11-40-58-177_com.tencent.mm.jpg
- 基于Dart的Flutter小提琴调音器APP设计源码 - violinhelper
- 基于JavaScript和CSS的随寻订购网页设计源码 - web-order
- 基于MATLAB的声纹识别系统设计源码 - VoiceprintRecognition
- 基于Java的微服务插件集合设计源码 - wsy-plugins
- 基于Vue和微信小程序的监理日志系统设计源码 - supervisionLog
- 基于Java和LCN分布式事务框架的设计源码 - tx-lcn
- 基于Java和JavaScript的茶叶评级管理系统设计源码 - tea
- IMG_5680.JPG
- IMG_0437.jpg
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功