《集合论与图论16》由会员分享，可在线阅读，更多相关《集合论与图论16（35页珍藏版）》请在金锄头文库上搜索。
1、集合论与图论第16讲1 2009-10-15 第第16讲讲 图的矩阵表示图的矩阵表示 内容提要内容提要 第十章第十章图的矩阵表示图的矩阵表示 10.1 关联矩阵关联矩阵 10.2 邻接矩阵表示与相邻矩阵邻接矩阵表示与相邻矩阵 集合论与图论第16讲2 2009-10-15 有向图关联矩阵有向图关联矩阵 设设D=是是无环无环有向图有向图, V=v1,v2,vn, E=e1,e2,em 关联矩阵关联矩阵(incidence matrix): M(D)=mijn m, 1, vi是是ej的起点的起点 mij= 0, vi与与ej不关联不关联 -1, vi是是ej的终点的终点 集合论与图论第16讲3 2
2、009-10-15 有向图关联矩阵举例有向图关联矩阵举例 110000 111100 001011 000111 )( 654321 4 3 2 1 eeeeee v v v v DM v1 v2 v4 v3 e1e2e3e5 e4 e6 集合论与图论第16讲4 2009-10-15 有向图关联矩阵性质有向图关联矩阵性质 每列和为零每列和为零: ni=1mij=0 每行绝对值和为每行绝对值和为d(v): d(vi)= mj=1mij, 其中其中 1的个数为的个数为d+(v), -1的个数为的个数为d-(v) 握手定理握手定理: ni=1 mj=1mij=0 平行边平行边: 相同两列相同两列 集
3、合论与图论第16讲5 2009-10-15 无向图关联矩阵无向图关联矩阵 设设G=是是无环无环无向图无向图, V=v1,v2,vn, E=e1,e2,em 关联矩阵关联矩阵(incidence matrix): M(G)=mijn m, 1, vi与与ej关联关联 mij= 0, vi不与不与ej关联关联 集合论与图论第16讲6 2009-10-15 无向图关联矩阵举例无向图关联矩阵举例 100100 111000 010011 001111 )( 654321 4 3 2 1 eeeeee v v v v GM v1 v2 v4 v3 e1e2 e3 e4 e6 e5 集合论与图论第16讲7
4、 2009-10-15 无向图关联矩阵性质无向图关联矩阵性质 每列和为每列和为2: ni=1mij=2 ( ni=1 mj=1mij=2m ) 每行和为每行和为d(v): d(vi)= mj=1mij 每行所有每行所有1对应的边构成对应的边构成断集断集: vi, vi 平行边平行边: 相同两列相同两列 伪对角阵伪对角阵: 对角块是连通分支对角块是连通分支 )( )( )( )( 2 1 k GM GM GM GM 集合论与图论第16讲8 2009-10-15 无向图关联矩阵的秩无向图关联矩阵的秩 定理定理10.1: G连通连通 r(M(G)=n-1 (F=0,1) # 集合论与图论第16讲9
5、2009-10-15 无向图基本关联矩阵无向图基本关联矩阵 设设G=是是无环无环无向图无向图, V=v1,v2,vn, E=e1,e2,em 参考点参考点: 任意任意1个顶点个顶点 基本关联矩阵基本关联矩阵(fundamental incidence matrix): 从从M(G)删除参考点对应的行删除参考点对应的行, 记作记作 Mf(G) 集合论与图论第16讲10 2009-10-15 无向图基本关联矩阵的秩无向图基本关联矩阵的秩 定理定理10.2: G连通连通r(Mf(G)=n-1. # 推论推论1: G有有p个连通分支个连通分支 r(Mf(G)=n-p, 其中其中Mf(G)是从是从M(G
6、)的每个对角块中的每个对角块中 删除任意删除任意1行而得到的行而得到的. # 推论推论2: G连通连通r(M(G)=r(Mf(G)=n-1. # 集合论与图论第16讲11 2009-10-15 基本关联矩阵与生成树基本关联矩阵与生成树 定理定理10.3: G连通连通, Mf是是Mf(G)中任意中任意n-1列组成的方阵列组成的方阵, Mf中各列对应的边集是中各列对应的边集是ei1,ei2, ei(n-1), T是导出子图是导出子图Gei1,ei2,ei(n-1), 则则 T是是G的生成树的生成树 Mf的行列式的行列式|Mf| 0. # 集合论与图论第16讲12 2009-10-15 用关联矩阵求
7、所有生成树用关联矩阵求所有生成树 忽略环忽略环, 求关联矩阵求关联矩阵 任选参考点任选参考点, 求基本关联矩阵求基本关联矩阵 求所有求所有n-1阶子方阵阶子方阵,计算行列式计算行列式,行列行列 式非式非0的是生成树的是生成树 集合论与图论第16讲13 2009-10-15 求所有生成树求所有生成树(例例) 100100 111000 010011 001111 )( 654321 4 3 2 1 eeeeee v v v v GM v1 v2 v4 v3 e1e2 e3 e4 e6 e5 集合论与图论第16讲14 2009-10-15 求所有生成树求所有生成树(例例,续续) 100100 11
8、1000 010011 )( 654321 4 3 2 eeeeee v v vGM f v1 v2 v4 v3 e1e2 e3 e4 e6 e5 集合论与图论第16讲15 2009-10-15 求所有生成树求所有生成树(例例,续续) 100100 111000 010011 )( 654321 4 3 2 eeeeee v v vGM f v1 v2 v4 v3 e1e2 e3 e4 e6 e5 1,2,302,3,41 1,2,402,3,51 1,2,502,3,61 1,2,602,4,50 1,3,412,4,61 1,3,512,5,61 1,3,613,4,51 1,4,503,
9、4,60 1,4,613,5,61 1,5,614,5,61 集合论与图论第16讲16 2009-10-15 有向图邻接矩阵有向图邻接矩阵 设设D=是有向图是有向图,V=v1,v2,vn 邻接矩阵邻接矩阵(adjacence matrix): A(D)=aijn n, aij= 从从vi到到vj的边数的边数 v1 v2 v4 v3 1100 1000 0100 0120 )( 4321 4 3 2 1 vvvv v v v v DA 集合论与图论第16讲17 2009-10-15 有向图邻接矩阵有向图邻接矩阵(性质性质) 每行和为出度每行和为出度: nj=1aij=d+(vi) 每列和为入度每
10、列和为入度: ni=1aij=d-(vj) 握手定理握手定理: ni=1 nj=1aij= ni=1d-(vj)=m 环个数环个数: ni=1aii v1 v2 v4 v3 1100 1000 0100 0120 )( 4321 4 3 2 1 vvvv v v v v DA 集合论与图论第16讲18 2009-10-15 邻接矩阵与通路数邻接矩阵与通路数 设设A(D)=A=aijn n, Ar=Ar-1 A,(r 2), Ar=a(r)ijn n, Br=A+A2+Ar= b(r)ijn n 定理定理4: a(r)ij=从从vi到到vj长度为长度为r的通路总数且的通路总数且 ni=1 nj=
11、1a(r)ij=长度为长度为r的通路总数的通路总数 且且 ni=1a(r)ii=长度为长度为r的回路总数的回路总数 推论推论: b(r)ij=从从vi到到vj长度长度 r的通路总数的通路总数 且且 ni=1 nj=1b(r)ij=长度长度 r的通路总数的通路总数 且且 ni=1b(r)ii=长度长度 r的回路总数的回路总数. # 集合论与图论第16讲19 2009-10-15 定理定理10.4证明证明 证明证明: (归纳法归纳法) (1)r=1: a(1)ij=aij, 结论显然结论显然. (2) 设设r k时结论成立时结论成立, 当当r=k+1时时, a(k)it a(1)tj=从从vi到到
12、vj最后经过最后经过vt的长度为的长度为 k+1的通路总数的通路总数, a(k+1)ij= nt=1a(k)it a(1)tj=从从vi到到vj的长度为的长度为 k+1的通路总数的通路总数. # k1 集合论与图论第16讲20 2009-10-15 用邻接矩阵求通路数举例用邻接矩阵求通路数举例 v1 v2 v4 v3 1100 1000 0100 0120 )( 4321 4 3 2 1 vvvv v v v v DA 2100 1100 1000 1200 2 A 3200 2100 1100 3100 3 A 5300 3200 2100 4300 4 A 3200 2100 1100 1
13、320 2 B 6400 4200 2200 4420 3 B 11700 7400 4300 8720 4 B 集合论与图论第16讲21 2009-10-15 用邻接矩阵求通路数举例用邻接矩阵求通路数举例 v2到到v4长度为长度为3和和4的通路数的通路数: 1, 2 v2到到v4长度长度 4的通路数的通路数: 4 v4到到v4长度为长度为4的回路数的回路数: 5 v4到到v4长度长度 4的回路数的回路数: 11 2100 1100 1000 1200 2 A 3200 2100 1100 3100 3 A 5300 3200 2100 4300 4 A 3200 2100 1100 1320 2 B 6400 4200 2200 4420 3 B 11700 7400 4300 8720 4 B 集合论与图论第16讲22 2009-10-15 用邻接矩阵求通路数举例用邻接矩阵求通路数举例 长度长度=4的通路的通路(不含回路不含回路)数数: 16 长度长度 4的通路和回路数的通路和回路数: 53, 15 2100 1100 1000 1200 2 A 3200 2100 1100 3100 3 A
