基本关联矩阵与生成树 定理103:G连通,M是M(G)中任意n-1 ene2…,cod+T是导出子图SN 列组成的方阵,M中各列对应的边集 eio.e n T是G的生成树>M的行列式M0 证明:MT=M,T是G的生成树台→T连通 台r(M(T)=n-1<(Mp=n-1<M满秩← M#≠0.# 说明:上述运算是在F=0,1}上进行的 《集合论与图论》第22讲
《集合论与图论》第22讲 11 基本关联矩阵与生成树 定理10.3: G连通, M’f是Mf(G)中任意n-1 列组成的方阵, M’f中各列对应的边集是 {ei1,ei2,…, ei(n-1)}, T是导出子图G[{ei1, ei2,…,ei(n-1)}], 则 T是G的生成树 ⇔ M’f的行列式|M’f|≠0 证明: Mf(T)=M’f, T是G的生成树⇔T连通 ⇔r(Mf(T))=n-1⇔r(M’f)=n-1⇔M’f 满秩⇔ |M’f|≠0. # 说明: 上述运算是在F={0,1}上进行的
用关联矩阵求所有生成树 忽略环,求关联矩阵 任选参考点,求基本关联矩阵 求所有n-1阶子方阵,计算行列式行列式 非0的是生成树 《集合论与图论》第22讲
《集合论与图论》第22讲 12 用关联矩阵求所有生成树 忽略环, 求关联矩阵 任选参考点, 求基本关联矩阵 求所有n-1阶子方阵,计算行列式,行列式 非0的是生成树
求所有生成树(例) e1 e2e MG= 10010 V3 《集合论与图论》第22讲 13
《集合论与图论》第22讲 13 求所有生成树(例) ⎥⎥⎥⎥⎦⎤ ⎢⎢⎢⎢⎣⎡ = 0 0 1 0 0 1 0 0 0 1 1 1 1 1 0 0 1 0 1 1 1 1 0 0 ( ) 1 2 3 4 5 6 4 3 2 1 e e e e e e v v v v M G v1 v2 v4 v3 e1 e2 e3 e4 e6 e5
求所有生成树(例续) e1 e2e M,(G)=n2 10010 00011 《集合论与图论》第22讲
《集合论与图论》第22讲 14 求所有生成树(例,续) ⎥⎥⎥⎥⎦⎤ ⎢⎢⎢⎢⎣⎡ = 0 0 1 0 0 1 0 0 0 1 1 1 ( ) 1 1 0 0 1 0 1 2 3 4 5 6 4 3 2 e e e e e e v v M G v f v1 v2 v4 v3 e1 e2 e3 e4 e6 e5
求所有生成树(例续) 12302.34 12402,3.5 12.50236 1,2.6 0 2,4.50 1,3412,4.6 ee e3 e4 es e6 13511256 MO=811001 1361345 000111 4503460 0010011461356 1.5614.56 《集合论与 15
《集合论与图论》第22 讲 15 求所有生成树 ( 例 , 续 ) ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = 0 0 1 0 0 1 0 0 0 1 1 1 ( ) 1 1 0 0 1 0 1 2 3 4 5 6 4 3 2 e e e e e e v v M G v f v1 v 2 v 4 v 3 e1 e 2 e 3 e 4 e 6 e 5 1,4,6 1 3,5,6 1 1,2,4 0 2,3,5 1 1,5,6 1 4,5,6 1 1,3,6 1 3,4,5 1 1,3,4 1 2,4,6 1 1,2,5 0 2,3,6 1 1,4,5 0 3,4,6 0 1,3,5 1 2,5,6 1 1,2,6 0 2,4,5 0 1,2,3 0 2,3,4 1