集合论与图论第16讲图的矩阵表示

1、第16讲图的矩阵表示内容提要第十章图的矩阵表示10.110.2关联矩阵邻接矩阵表示与相邻矩阵1集合论与图论第16讲2008-12-02有向图关联矩阵设D=是无环有向图, V=v1,v2,vn, E=e1,e2,em关联矩阵(incidence matrix): M(D)=mijnm,1,0,-1,vi是ej的起点vi与ej不关联 vi是ej的终点mij=2集合论与图论第16讲2008-12-02有向图关联矩阵举例v1v4e1e2e3e5e6e4e 3v2e1100v3e401e1v120 v30 v5e6e121010000011D)1 vM (1011 43集合论与图论第16讲2008-12

2、-02有向图关联矩阵性质ni=1mij=0每列和为零:每行绝对值和为d(v): d(vi)=mm ,j=1ij其中 1的个数为d+(v),-1的个数为d-(v)ni=1mijj=1m =0握手定理:平行边:相同两列4集合论与图论第16讲2008-12-02无向图关联矩阵设G=是无环无向图, V=v1,v2,vn, E=e1,e2,em关联矩阵(incidence matrix): M(G)=mijnm,1,vi与ej关联mij=0,vi不与ej关联5集合论与图论第16讲2008-12-02无向图关联矩阵举例v1v4e3e1e6v2ee5e 31001v3 e4 1010e5e06e001112

3、1v1111G) v 1M(012v30v 00046集合论与图论第16讲2008-12-02e2e4无向图关联矩阵性质每列和为2: ni=1mij=2 ( ni=1mm =2m )j=1ij每行和为d(v): d(vi)=mmj=1ij每行所有1对应的边平行边: 相同两列断集: vi, vi伪对角阵: 对角块是连通分支M(1G)M(G)M (G) 2OM (kG)7集合论与图论第16讲2008-12-02无向图关联矩阵的秩定理10.1:G连通 r(M(G)=n-1(F=0,1)#8集合论与图论第16讲2008-12-02无向图基本关联矩阵设G=是无环无向图, V=v1,v2,vn, E=e1

4、,e2,em参考点: 任意1个顶点基本关联矩阵(fundamental incidence matrix): 从M(G)删除参考点对应的行, 记作 Mf(G)9集合论与图论第16讲2008-12-02无向图基本关联矩阵的秩定理10.2: G连通r(Mf(G)=n-1.推论1:G有p个连通分支 r(Mf(G)=n-p,其中Mf(G)是从M(G)的每个对角块中#删除任意1行而得到的.#推论2: G连通r(M(G)=r(Mf(G)=n-1. #10集合论与图论第16讲2008-12-02基本关联矩阵与生成树定理10.3: G连通,Mf是Mf(G)中任意n-1列组成的方阵, Mf中各列对应的边集是ei

5、1,ei2, ei(n-1),T是导出子图Gei1,ei2,ei(n-1),则T是G的生成树 Mf的行列式|Mf|0. #11集合论与图论第16讲2008-12-02用关联矩阵求所有生成树忽略环, 求关联矩阵任选参考点, 求基本关联矩阵求所有n-1阶子方阵,计算行列式,行列式非0的是生成树12集合论与图论第16讲2008-12-02求所有生成树(例)v1v4e3e1e6v2ee5e 31001v3 e4 1010e5e06e0011121v1111G) v 1M(012v30v 000413集合论与图论第16讲2008-12-02e2e4求所有生成树(例,续)v1v4e3e1e6v2e5e 3

6、v3e4ee5e6e1211G) v 1001010011M(01f2v30v 000414集合论与图论第16讲2008-12-02e2e4求所有生成树(例,续)v1v4e3ee16vev253eee3e45e6 e1211G)v1001010011M(01f2v03v040015集合论与图论2008-12-02e2e41,2,302,3,411,2,402,3,511,2,502,3,611,2,602,4,501,3,412,4,611,3,512,5,611,3,613,4,511,4,503,4,601,4,613,5,611,5,6第16讲14,5,61有向图邻接矩阵设D=是有向图,

7、V=v1,v2,vn邻接矩阵(adjacence matrix):A(D)=aijnn,aij= 从vi到vj的边数vv 22000v31101v40011v1v41v01A (D) v02v03v04v2v3集合论与图论第16讲162008-12-02有向图邻接矩阵(性质)每行和为出度: nj=1aij=d+(vi)每列和为入度: ni=1aij=d-(vj)握手定理: ni=1nj=1aij=ni=1d-(vj)=m环个数: ni=1aiivv 22000v31101v40011v1v41v01A (D) v02v03v04v2v3集合论与图论第16讲172008-12-02邻接矩阵与通路

8、数设A(D)=A=aijnn, Ar=Ar-1A,(r2), Ar=a(r)ijnn, Br=A+A2+Ar= b(r)ijnn定理4: a(r)ij=从vi到vj长度为r的通路总数且ni=1nj=1a(r)ij=长度为r的通路总数且 ni=1a(r)ii=长度为r的回路总数推论: b(r)ij=从vi到vj长度r的通路总数且 ni=1nj=1b(r)ij=长度r的通路总数且 ni=1b(r)ii=长度r的回路总数.#18集合论与图论第16讲2008-12-02定理10.4证明证明: (归纳法) (1)r=1: a(1)ij=aij, 结论显然.(2) 设rk时结论成立, 当r=k+1时,a(

9、k)ita(1)tj=从vi到vj最后经过vt的长度为 k+1的通路总数,a(k+1)ij=nt=1a(k)ita(1)tj=从vi到vj的长度为k+1的通路总数. #k1集合论与图论第16讲192008-12-02用邻接矩阵求通路数举例vv 22000v31101v40011v1v41v01A (D) v02v03v04v2v3000011230000312373473 420000020201131121010011211A 2A 3A 40 1000000020242340002050402 8 40200 7 2B 3B 4B00 2000 03 1100460020集合论与图论第16

10、讲2008-12-02用邻接矩阵求通路数举例v2到v4长度为3和4的通路数: 1,v2到v4长度4的通路数: 4v4到v4长度为4的回路数: 52v4到v4长度4的回路数: 11000002011124230000020312373047423500000202011311210123420011211A 2A 3A 40000000000402 8 4000 7 B2B 3B 400 200 03 1100460021集合论与图论第16讲2008-12-02用邻接矩阵求通路数举例长度=4的通路(不含回路)数: 16长度4的通路和回路数: 53, 1500001123000031233 420

11、000020201131121010011211A 2A 3A 40 10000000202423400050402 8 40200 7B2B 3B 40 200110046000322集合论与图论第16讲2008-12-0227030407可达矩阵设D=是有向图,V=v1,v2,vn,可达矩阵:P(D)=pijnn,1,从vi可达vjpij=0,从vi不可达vj23集合论与图论第16讲2008-12-02可达矩阵性质主对角线元素都是1: viV, 从vi可达vi强连通图: 所有元素都是1伪对角阵: 对角块是连通分支的可达矩阵ij,pij=1 b(n-1)ij 0P (1D)P (D)P (D

12、) 2OP (D)k24集合论与图论第16讲2008-12-02可达矩阵举例v4v1vv 22000v31101v4001111111v01D) v02A(v03v04v2v3000002011124230000020312373047423500000202011311210123420011211A 2A 3A 40000000000402 8 4000 7 2B 3B 4B00 200 03 1100460025集合论与图论第16讲2008-12-021 110 11P 0 010 01无向图相邻矩阵设G=是无向简单图,V=v1,v2,vn相邻矩阵(adjacence matrix):1

13、, vi与vj相邻,ijA(G)=aijnn, aii=0,aijv4=0,vi与vj不相邻v1vvv30100v4110012v011G) v1011A (2v03v1v2v3426集合论与图论第16讲2008-12-02无向图相邻矩阵性质A(G)对称: aij=aji每行(列)和为顶点度: ni=1aij=d(vj)握手定理: ni=1nj=1aij=ni=1d(vj)=2mvvv30100v4110012v011A (G) v10112v03v1v2v3集合论与图论第16讲4272008-12-02相邻矩阵与通路数设Ar=Ar-1A,(r2), Ar=a(r)ijnn, Br=A+A2+

14、Ar= b(r)ijnn定理10.5: a(r)ij=从vi到vj长度为r的通路总数且 ni=1a(r)ii=长度为r的回路总数. #推论1: a(2)ii=d(vi).#推论2: G连通距离d(vi,vj)=minr|a(r)ij0. #28集合论与图论第16讲2008-12-02用相邻矩阵求通路数举例v1v4vvv30100v4110012v011G) v1011A(2v03v14v2v33746114621301101116261112A 2A 3A 434 2112412664729集合论与图论第16讲2008-12-02用相邻矩阵求通路数举例v1到v2长度为4的通路数: 614142

15、,14242,14232,12412,14212,12142v1v4v1到v3长度为4的通路数: 412423,12323,14123,12123v1到v1长度为4的回路数: 714141,14241,14121,12121,12421,12321,12141,v2v3376112646213011011162647301112A 2A 3A 446341124116讲2集合论与图论第2008-12-02连通矩阵设G=是无向简单图,V=v1,v2,vn,连通矩阵:P(G)=pijnn,1,若vi与vj连通pij=0,若vi与vj不连通31集合论与图论第16讲2008-12-02连通矩阵性质主对角线元素都是1: viV, vi与vi连通连通图: 所有元素都是1伪对角阵: 对角块是连通分支的连通矩阵设Br=A+A2+Ar= b(r)ijnn, 则ij, b(n-1)ij 0pij=1P (1G)P (G)P (G) 2OP (集合论与图论第16讲G)k322008-12-02连通矩阵举例v1v3v4v6