例1，利用凯莱递推法求下图生成树的棵数。 共8棵生成树
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 例1，利用凯莱递推法求下图生成树的棵数。 共8棵生成树
凯莱公式的缺点之一是计算量很大，其次是不能具 体指出每棵生成树。 2、关联矩阵计数法 定义3：n×m矩阵的一个阶数为mim{n,m}的子方阵， 称为它的一个主子阵；主子阵的行列式称为主子行列式。 显然，当n<m时，n×m矩阵Cm个主子阵。 定理3设Am是连通图G的基本关联矩阵的主子阵，则 Am非奇异的充分必要条件是相应于Am的列的那些边构 成G的一棵生成树。 证明：必要性
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 凯莱公式的缺点之一是计算量很大，其次是不能具 体指出每棵生成树。 2、关联矩阵计数法 定义3 ：n×m矩阵的一个阶数为min｛n, m｝的子方阵， 称为它的一个主子阵；主子阵的行列式称为主子行列式。 显然，当n<m时，n×m矩阵 Cm n 个主子阵。 定理3 设Am是连通图G的基本关联矩阵的主子阵，则 Am非奇异的充分必要条件是相应于Am的列的那些边构 成G的一棵生成树。 证明：必要性
设Am是A的一个非奇异主子阵，并设与A的列相对 应的边构成G的子图Gm 由于Am有n-l行，故Gm应该有n个顶点（包括参考点）； 又Am有n-1列，所以Gm有n-1条边。而Am非奇异，故Am的 秩为n-1,即G连通。这说明Gm是n个点，n-1条边的连通 图，所以，它是树。 充分性 如果A的列对应的边作成G的一棵生成树，因树是连通 的，所以，它对应的基本关联矩阵Am非奇异。 该定理给出了求连通图G的所有生成树的方法： (1)写出G的关联矩阵，进一步写出基本关联矩阵， 记住参考点；
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 8 设Am是Af的一个非奇异主子阵，并设与Am的列相对 应的边构成G的子图Gm. 由于Am有n-1行，故Gm应该有n个顶点(包括参考点); 又Am有n-1列,所以Gm有n-1条边。而Am非奇异，故Am的 秩为n-1 ,即Gm连通。这说明Gm是n个点，n-1条边的连通 图，所以，它是树。 充分性 如果Am的列对应的边作成G的一棵生成树，因树是连通 的，所以，它对应的基本关联矩阵Am非奇异。 该定理给出了求连通图G的所有生成树的方法： (1) 写出G的关联矩阵，进一步写出基本关联矩阵， 记住参考点；
(2)找出基本关联矩阵的非奇异主子阵，对每个这样 的主子阵，画出相应的生成树。 例2，画出下图G的所有不同的生成树。 解：取4为参考点，G的基本关联矩阵为： 0
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 9 (2) 找出基本关联矩阵的非奇异主子阵，对每个这样 的主子阵，画出相应的生成树。 例2，画出下图G的所有不同的生成树。 1 2 3 4 a b c d e G 解：取4为参考点，G的基本关联矩阵为： 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 Af = a b c d e 1 2 3
共有10个主子阵，非奇异主子阵8个，它们是： 1 的 10
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 10 共有10个主子阵，非奇异主子阵8个，它们是： 1 2 3 4 a b d 1 1 1 0 0 1 1 0 0 1 A = a b d 1 2 3 2 1 1 0 0 1 0 0 0 1 A = a b e 1 2 3 1 2 3 4 a b e