《图的矩阵表示》PPT课件.ppt

《《图的矩阵表示》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1计算机科学领域有许多算法涉及图。计算机存储图的一种最简单有效的方法就是矩阵。矩阵是由数字组成的矩阵表格，一般用大写字母表示。（元素、行、列）。图论有效地利用了矩阵，将其作为表达图及其性质的有效工具和手段。图在计算机中怎么表示?图跟矩阵是否一一对应?2007-11-1018:27提问者：Nimitz

2、浏览次数：1408次课本上有讲关于图的矩阵表示,但并没有提到这个问题.图(有向图或者无向图)跟矩阵是否一一对应呢?即一个矩阵是否能够唯一确定一个图,一个图是否能唯一确定一个矩阵?如果是这样的话,图在计算机中就好表示了.我一直在思考这个问题.谢谢了!图一般可以用邻结

3、矩阵来表示，是双射得。比如跳马问题等就是这么处理得！2用邻接矩阵表示一个图时1、输出一个图的边数，以及两端顶点2、增加、删除一条边（输出新图对应的邻接矩阵）3414.4图的矩阵表示无向图的关联矩阵有向无环图的关联矩阵有向图的邻接矩阵有向图中的通路数与回路数有向图的可达矩阵5无向图的关联矩阵设无向图G=,V={v1,v2,…,vn},E={e1,e2,…,em}.令mij为vi与ej的关联次数,称(mij)nm为G的关联矩阵,记为M(G).mij的可能取值为:0,1,2例如e1e2e3e4e5e6v5v1v2v3v4M(G)=211000010111

4、0000110000000011006关联矩阵的性质7无环有向图的关联矩阵则称(mij)nm为D的关联矩阵,记为M(D).设无环有向图D=,V={v1,v2,…,vn},E={e1,e2,…,em}.令(3)ej与ek是平行边第j列与第k列相同(2)第i行1的个数等于d+(v),第i行1的个数等于d(v)性质:8实例v1v2v3v4e2e1e3e4e5e6e7M(D)=–11000–110–11000000–1–1–11–110011009有向图的邻接矩阵设有向图D=,V={v1,v2,…,vn},E={e1,e2,…,em},令为

5、顶点vi邻接到顶点vj边的条数，称()mn为D的邻接矩阵,记作A(D),简记作A.10实例A=1100001010001020v1v2v3v411有向图中的通路数与回路数定理14.11设A为n阶有向图D的邻接矩阵,则Al(l1)中元素等于D中vi到vj长度为l的通路(含回路)数,等于vi到自身长度为l的回路数,等于D中长度为l的通路(含回路)总数,等于D中长度为l的回路总数.12实例(续)A=1100001010001020A2=1110100011003100A3=2110110011103310A4=3210111021104330v1到v2长为3的通

6、路有1条v1到v3长为3的通路有1条v1到自身长为3的回路有2条D中长为3的通路共有16条,其中回路4条v1v2v3v413有向图的可达矩阵性质:P(D)主对角线上的元素全为1.D强连通当且仅当P(D)的元素全为1.设有向图D=,V={v1,v2,…,vn},令称(pij)nn为D的可达矩阵,记作P(D),简记为P.14实例例1(1)v1到v4,v4到v1长为3的通路各有多少条?(2)v1到自身长为1,2,3,4的回路各有多少条?(3)长为4的通路共有多少条?其中有多少条回路?(4)长度小于等于4的回路共有多少条?(5)写出D的可达矩阵,并问D是强

7、连通的吗?解v1v2v3v4A=121000100001001015实例(续)v1到v4长为3的通路有条,A2=1231000100100001A3=1243001000010010A4=12640001001000013v4到v1长为3的通路有条0v1到自身长为1,2,3,4的回路各有条1长为4的通路共有条，其中有条回路163长度小于等于4的回路共有条8可达矩阵非强连通,单连通P=1111011100110011