第七章 图的基本概念3

发布时间:2021-09-17 20:08:50

第七章 图的基本概念
3、图的矩阵表示

退出

7.3 图的矩阵表示
给定一个图G=<V 给定一个图 G=<V , E> , 使用图形表示法很容易 把图的结构展现出来,而且这种表示直观明了。 把图的结构展现出来,而且这种表示直观明了。但这只 在结点和边(或弧)的数目相当小的情况下才是可行的。 在结点和边(或弧)的数目相当小的情况下才是可行的。 显然这限制了图的利用。 显然这限制了图的利用。 本节提供另一种图的表示法—— 图的矩阵表示法 本节提供另一种图的表示法 ——图的矩阵表示法。 图的矩阵表示法。 它不仅克服了图形表示法的不足, 它不仅克服了图形表示法的不足,而且这种表示可以充 分利用现代工具电子计算机,以达到研究图的目的。 分利用现代工具电子计算机,以达到研究图的目的。

无向图的关联矩阵
E V 设无向图 G=<V,E>, = {v1, v2 ,L, vn} , = {e1, e2 ,L, em}, ,

令 mij 为顶点 vi 与 e j 边的关联次数,则称 (mij )n×m 为 G 的 边的关联次数, 关联矩阵, 关联矩阵,记作 M(G).

自环取2 注:自环取2。

?1 ?0 M(G) = ? ?1 ? ?0

1 1 0 0? ? 1 1 1 0? 0 0 1 2? ? 0 0 0 0?

性质 :

∑m
i =1

n

ij

= 2,

j = 1,2,L, m

∑m
j =1

m

ij

= d(vi ), i = 1,2,L, n
n m n

∑∑m = ∑∑m = ∑d(v ) = 2m
j =1 i =1
m

m

n

ij

i =1 j =1

ij

i =1

i

∑m
j =1

ij

v = 0,当且仅当 i为孤立点

若第j列与第k列相同,则ej与ek为*行边

有向图的关联矩阵
中无环, 设有向图 D=<V,E>中无环,V = {v1, v2 ,L, vn }, 中无环
E = {e1, e2 ,L, em},

令 mij

? 1 vi是e j的始点 ? = ?0 vi与e j 不关联 , ? vi是e j的终点 ??1

的关联矩阵, 则称 (mij )n×m 为 D 的关联矩阵,记作 M(D).

??1 ?1 M(D) = ? ?0 ? ?0

?1 1 0 0

1 0 ?1 0

0 1 ?1 0

0 0 1 ?1

0? 0? ? ?1? ? 1?

性质 :

∑m
i =1

n

ij

= 0,

j = 1,2,L, m

∑∑m
j =1 i =1
m j =1 m

m

n

ij

=0

(mij = 1) = d + (vi ), ∑ (mij = ?1) = ?d ? (vi ), i = 1,2,L, n ∑
j =1

(mij = 1) = ∑d + (vi ) = m = ?∑d ? (vi ) = ?∑∑(mij = ?1) ∑∑
i =1 j =1 i ?1 i =1 i =1 j =1

n

m

n

n

n

m

一个简单图G=<V 一个简单图G=<V,E>由V中每两个结点间 的邻接关系唯一地确定,这种关系可以用一个 的邻接关系唯一地确定, 矩阵给出, 矩阵给出,而矩阵形式与图中结点的编序有密 切关系,这是用矩阵表示图值得注意的一点。 切关系,这是用矩阵表示图值得注意的一点。

有向图的邻接矩阵
有 向 图 的 ( 点 点 ) 邻 接 矩 阵 : 设 有 向 图 D=<V,E> ,
V = {v1, v2 ,L, vn } , E = {e1, e2 ,L, em} ,令 aij 为顶点 vi 令
(1)

边的条数, 邻接到顶点 vj 边的条数, 则称 (aij )n×n 为 D 的邻接 矩阵, 矩阵,记作 A(D).或简记为 A. 或简记为

(1)

对于给定图D 对于给定图 D , 显然不会因结点编序不同 而使其结构发生任何变化, 而使其结构发生任何变化 , 即图的结点所有不 同的编序实际上仍表示同一个图。 换句话说, 同的编序实际上仍表示同一个图 。 换句话说 , 这些结点的不同编序的图都是同构的, 这些结点的不同编序的图都是同构的 , 并且它 们的邻接矩阵都是相似的。 们的邻接矩阵都是相似的。 今后将略去这种由于V 今后将略去这种由于 V 中结点编序而引起 邻接矩阵的任意性, 邻接矩阵的任意性 , 而取该图的任一个邻接矩 阵作为该图的矩阵表示。 阵作为该图的矩阵表示。

?0 ?0 A(D) = ? ?0 ? ?0

2 0 0 0

1 1 0 1

0? 0? ? 1? ? 1?

性质 :

∑aij
j =1
n

n

(1)

= d + (vi ), i = 1,2,L, n
= d ? (v j ),
n

∑aij
i =1

(1)

j = 1,2,L, n

( aij1) = ∑d + (vi ) = m ∑∑ i =1 j =1
n n

n

n

i =1
n

( aij1) = ∑d ? (vi ) = m ∑∑ j =1 i =1 j =1

?A(D)中所有元素之和为D中长度为1的通路总数,其中 A(D)中所有元素之和为D中长度为1的通路总数, A(D)中所有元素之和为 ?主对角线元素之和为D中长度为1的回路(环)的总数。 主对角线元素之和为D中长度为1的回路( 的总数。 主对角线元素之和为

邻接矩阵可展示相应图的一些性质: 邻接矩阵可展示相应图的一些性质:
若邻接矩阵的元素全为零, 若邻接矩阵的元素全为零,则其对应的图 是零图; 是零图; 若邻接矩阵的元素除主对角线元素外全为1 若邻接矩阵的元素除主对角线元素外全为1, 则其对应的图是连通的且为简单完全图。 则其对应的图是连通的且为简单完全图。

?1 ?1 ? ?1 A(G) = ? ?0 ?0 ? ?0

1 1 0 0 0? 1 1 0 0 0? ? 1 1 0 0 0? ? 0 0 1 1 0? 0 0 1 1 0? ? 0 0 0 0 1?

此外,当给定的简单图是无向图时,邻接 无向图时 此外,当给定的简单图是无向图 对称矩阵 矩阵是对称矩阵;反之,若给定任何对称矩阵A 矩阵是对称矩阵;反之,若给定任何对称矩阵A, 显然可以唯一地作出以A 显然可以唯一地作出以A为其邻接矩阵的简单图 G。于是,所有n个结点的不同编序的简单图的 于是,所有n 集合与所有n阶对称矩阵的集合可建立一一对应 集合与所有n阶对称矩阵的集合可建立一一对应。 一一对应。

当所给图是简单有向图 当所给图是简单有向图时,其邻接矩阵并 简单有向图时 其邻接矩阵并 一定是对称矩阵,但所有n 对称矩阵 非一定是对称矩阵,但所有n个结点的不同编序 的简单图的集合,与所有n阶邻接矩阵的集合亦 的简单图的集合,与所有n 可建立一一对应。 可建立一一对应。 不仅如此,通过对矩阵元素的一些计算还 不仅如此, 可以得到对应图的某些数量的特征。 可以得到对应图的某些数量的特征。

由给定有向图D的邻接矩阵A 由给定有向图D的邻接矩阵A可计算出矩阵 A的l次幂,即Al。 次幂,
定理: 设 的邻接矩阵, 定理: A 为有向图 D 的邻接矩阵,V = {v1, v2 ,L, vn } 为 D 的

Ar (r ≥ 1) 中元素 aij (r ) 为 D 顶点集, 顶点集,则 A 的 r 的次幂
的通路数, 中 vi 到 v j 长度为 r 的通路数,其中 aii 为 vi 到自身长 的回路数, 度为 r 的回路数,而 ∑∑a
i =1 j =1 n n (r ) ij
(r )

为 D 中长度为 r 的通路

( aiir ) 为 D 中长度为 l 的回路数。 总数, 的回路数。 总数,其中 ∑ i =1

n

在一些实际问题中,有时要判定图中结点v 在一些实际问题中,有时要判定图中结点vi到结点 vj是否可达,或者说vi到vj是否存在一要链(或通路)。 是否可达,或者说v 是否存在一要链(或通路) 如果要利用图D 的邻接矩阵A 则应计算A 如果要利用图 D 的邻接矩阵 A , 则应计算 A2 , A3 , ··· , ···, An,···。当发现其中某个Ar中 ···。当发现其中某个A ≥1,就表明vi可达vj或 就表明v 可达v

vi 到 vj 存在一条链 ( 或通路 ) 。 但这种计算繁琐量大 , 存在一条链( 或通路) 但这种计算繁琐量大, 又不知计算A 到何时为止。 又不知计算Ar到何时为止。

根据定理10.2.2可知 对于有n个结点的图, 根据定理10.2.2可知,对于有n个结点的图, 可知, 任何基本链(或通路)的长度不大于n 任何基本链(或通路)的长度不大于n-1和任何 基本圈(或回路)的长度不大于n。因此,只需 基本圈(或回路)的长度不大于n 因此, 考虑 就可以了,其中1≤r≤n。即只要计算 就可以了,其中1≤r Bn=A+A2+A3+···+An。 +···+A

( 推论: 推论:设 Br = A+ A +L+ A (r ≥ 1) ,则 Br 中元素 ∑∑bijr ) 为 D

n

n

2

r

i =1 j =1

的通路数, 中长度小于等于 r 的通路数, 其中 ∑bii 为 D 中长度小
(r ) i =1

n

的回路数。 于等于 r 的回路数。

如果关心的是结点间可达性或结点间是否 有链(或路), ),至于结点间的链存在多少条及 有链(或路),至于结点间的链存在多少条及 长度是多少无关紧要, 长度是多少无关紧要,那么便可用下面的定义 图的可达矩阵来表示结点间可达性。 图的可达矩阵来表示结点间可达性。

有向图的可达矩阵
定义7.3.2 给定有向图D=<V 定义7.3.2 给定有向图D=<V,E>,将其结点按下 标编序得V={v 标编序得V={v1,v2,…,vn}。定义一个n阶方阵P=(pij), 定义一个n阶方阵P=(p 其中 1 vi到vj可达 否则

Pij=

{

0

(Pii=1,i=1,2,…,n,若需要则添加) =1,i=1,2,…,n,若需要则添加 若需要则添加)
则称矩阵P是图D的可达矩阵。 则称矩阵P是图D的可达矩阵。

可见,可达矩阵表明了图中任意两结点间是否至 可见, 少存在一条链(或通路)以及在结点处是否有圈(或回路) 少存在一条链(或通路)以及在结点处是否有圈(或回路)。 从图D的邻接矩阵A可以得到可达矩阵P 从图D的邻接矩阵A可以得到可达矩阵P,即令 Bn=A+A2+A3+…+An,再从Bn中非零元素改为1而零元素 +…+A 再从B 中非零元素改为1 不变(若需要,主对角线元素均改为1), 不变(若需要,主对角线元素均改为1),这种变换后的矩 阵即是可达矩阵P 阵即是可达矩阵P。 显然可达矩阵是布尔矩阵。 显然可达矩阵是布尔矩阵。

应用:求有向图的强连通分支。 应用:求有向图的强连通分支。
设P是D的可达矩阵,其元素pij,PT是P的转 的可达矩阵,其元素p 其元素p 则图D的强连通分支可从矩阵P 置,其元素pijT,则图D的强连通分支可从矩阵P 求得。因从v 可达, =1, ∧PT求得。因从vi到vj可达,则pij=1,从vj到vi 可达, =1, =1,于是当且仅当v 可达,则pji=1,即pijT=1,于是当且仅当vi和vj 相互可达时, 的第(i,j)个元素的值为1 (i,j)个元素的值为 相互可达时, P∧PT的第(i,j)个元素的值为1 定理7.3.2 定理7.3.2 给定简单有向图D中的任意结 的可达矩阵, 点vi,若P=(pij)是D的可达矩阵,PT=(pji)是P的 行元素为1 转置矩阵, 转置矩阵,则P∧PT的第i行元素为1的列号为下 标的结点构成了包含vi的强分图

例如:求下列有向图的通路总数,回路总数, 例如:求下列有向图的通路总数,回路总数, 可达矩阵,及强连通分支的顶点集. 可达矩阵,及强连通分支的顶点集.

?0 ?0 ? A = ?0 ? ?0 ? ?0

0 1 0 0? 0 0 1 0? ? 0 0 1 0? ? 0 1 0 1? 0 0 1 0? ?

?0 ?0 ? A2 = ?0 ? ?0 ?0 ?

0 0 1 0? 0 1 0 1? ? 0 1 0 1? ? 0 0 2 0? 0 1 0 1? ?

?0 ?0 ? A3 = ?0 ? ?0 ?0 ?

0 1 0 1? 0 0 2 0? ? 0 0 2 0? ? 0 2 0 2? 0 0 2 0? ?

?0 ?0 ? 4 A = ?0 ? ?0 ?0 ?

0 0 2 0? 0 2 0 2? ? 0 2 0 2? ? 0 0 4 0? 0 2 0 2? ?

?0 ?0 ? 5 A = ?0 ? ?0 ?0 ?

0 2 0 2? 0 0 4 0? ? 0 0 4 0? ? 0 4 0 4? 0 0 4 0? ?

B5 = A+ A(2) + A(3) + A(4)

?0 (5) ?0 +A ? = ?0 ? ?0 ?0 ?

0 5 3 3? 0 3 7 3? ? 0 3 7 3? ? 0 7 6 7? 0 3 7 3? ?

长度小于等于5的通路总数70 长度小于等于5的通路总数70 长度小于等于5的回路总数12 长度小于等于5的回路总数12

P = E + B5 = E ∨ A∨ A(2) ∨ A(3) ∨ A(4) ∨ A(5) ?1 ?0 ? = ?0 ? ?0 ?0 ? 0 1 0 0 1? 1? ? 1? ? 1? 0 1 1 1? ? 1 1 1 1 1 1 1 1

?1 ?0 ? T P = ?1 ? ?1 ?1 ?

0 1 1 1

0? 0? ? 1? ? 1? 1 1 1 1? ? 0 0 1 1 0 0 1 1

?1 ?0 ? T P ∧ P = ?0 ? ?0 ?0 ?

0 0 0 0? 1 0 0 0? ? 0 1 1 1? ? 0 1 1 1? 0 1 1 1? ?

该图的强连通分支的顶点集为{v 该图的强连通分支的顶点集为{v1},{v2},{v3,v4,v5}.

利用简单有向图的可达矩阵, 利用简单有向图的可达矩阵 , 能够确定某 过程是否为递归的。 过程是否为递归的。 假设V 假设 VP={p1,p2,···,pn}是程序 P中的过程集合 , ,···,p 是程序P中的过程集合, 做有向图D=<V 做有向图 D=<VP,E> , 其中 pi∈VP , i=1,2,···,n ; 其中p ,···,n <pi,pj>∈E?pi 调用 pj 。 如果图 D 中有包含 pi 的回 调用p 如果图D 中有包含p 路,则可断言pi是递归的。为此,由图G的邻接 则可断言p 是递归的。为此,由图G 矩阵A=(a 计算出可达矩阵A 矩阵A=(aij)计算出可达矩阵A+=( 的主对角线上的某元素 )。如果A+中 如果A 是递归的。 =1,则pi是递归的。

权矩阵
已知加权的简单图G=<V 已知加权的简单图G=<V,E>,定义一个矩阵 W=(wij),其中: =(w 其中:

wij=

{

w,

w是边[vi,vj](或弧<vi,vj>)∈E的权 是边[ 或弧<

0, vi与vj不相邻

则称W为图G 则称W为图G的权矩阵

作业:P174 作业:P174 7.18


相关文档

  • 第七章 图的基本概念3汇总
  • 第7章 图的基本概念
  • 第七章—图的基本概念
  • 第七章图的基本概念1
  • 第七章图的基本概念
  • 第七章-图的基本概念答案
  • 第七章图的基本概念(1)
  • 第七章 图的基本概念1
  • 第7章-1 (图的基本概念)
  • 第7章 图论-1图的基本概念
  • 猜你喜欢

  • 2019年六年级数学下册 3.比例小结*题 新人教版
  • 常用低压电器及应用
  • C语言之选择流程语句:if--else
  • 中国地理填图集空白图.练*.
  • 皇家墨尔本理工大学毕业生起薪怎么样
  • 2017-2022年福建省公路行业发展预测及投资咨询报告
  • 谢谢你的宽容作文【初中初二700字】
  • 参考计划-公司出纳每日工作计划表三篇
  • 框架完整大气医疗机构工作总结汇报PPT模板
  • 7A Unit 2 ReadingII-olive
  • 永恒的中华民族精神 教学课件26 人教课标版.ppt
  • 2018专四作文常用短语88个
  • 电子舌在食品药品中的应用
  • 2019-2020年北京市资格从业考试《内分泌学》练*题资料[八十一]
  • OFA系列收费机使用说明书
  • C++多线程安全类的问题
  • 江苏省普通高校专转本选拔考试英语测试题(二)及答案
  • 现代传播背景下纳西族传统民间音乐传播现状及其保护的思考
  • 2019-2020年新标准英语一起第二册期中试卷
  • 碳油板特性用途及发展方向-PPT精品文档
  • 2019高中化学第一章物质结构元素周期律课时作业三含解析新人教版必修2
  • 华为荣耀pro路由器的怎么设置
  • 【合同协议范本】中国人民建设银行外汇借款合同(二)范本
  • 吕梁学院2018年各省艺术类专业录取分数线
  • 2017-2023年中国离心筛分机行业市场发展态势及投资前景可行性报告(目录)
  • DB3502Z042018标准化农贸场溯源体系建设规范
  • 怀孕吃什么饭菜
  • 米邵飞和孙亚亚第几集在一起
  • 成功离你并不遥远
  • 【精编范文】个人委托书银行转款怎么写-推荐word版 (2页)
  • 北京市基准地价容积率修正系数表(精)
  • 初一年级班主任班务工作计划
  • 每一件童年趣事
  • 责任高二作文800字
  • 大连宇杰机械铸造有限公司(企业信用报告)- 天眼查
  • 消防总*招标文件范本参考以及合同
  • 中国国家机关名称中英文对照
  • 2019年部编版一年级语文上册 识字 5 对韵歌18p 课件.ppt
  • 找寻一份静 高三
  • 游西安古都的作文精选
  • 全钢高性能子午线轮胎项目投资建设规划立项报告
  • 浅析新时期大学生志愿服务存在的主要问题及应对措施
  • 电脑版