电子科技大学：《图论及其应用 Graph Theory and its Applications》研究生课程教学资源（课件讲稿）07 生成树的概念与性质、生成树的计数、回路系统简介

本次课主要内容 (一)、生成树的概念与性质 (二)、生成树的计数 (三)、回路系统简介

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 2 本次课主要内容 (一)、生成树的概念与性质 (二)、生成树的计数 (三)、回路系统简介

(一)、生成树的概念与性质 1、生成树的概念 定义1图G的一个生成子图T如果是树，称它为G的一棵 生成树；若T为森林，称它为G的一个生成森林。 生成树的边称为树枝，G中非生成树的边称为弦。 例如： 图G 粗边构成的子图为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 3 1、生成树的概念 (一)、生成树的概念与性质 定义1 图G的一个生成子图T如果是树，称它为G的一棵 生成树；若T为森林，称它为G的一个生成森林。 生成树的边称为树枝，G中非生成树的边称为弦。 例如： 粗边构成的子图为G的生成树。 图G

2、生成树的性质 定理1每个连通图至少包含一棵生成树 证明：如果连通图G是树，则其本身是一棵生成树； 若连通图G中有圈C,则去掉C中一条边后得到的图仍 然是连通的，这样不断去掉G中圈，最后得到一个G的 无圈连通子图T,它为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 4 2、生成树的性质 定理1 每个连通图至少包含一棵生成树。 证明：如果连通图G是树，则其本身是一棵生成树； 若连通图G中有圈C，则去掉C中一条边后得到的图仍 然是连通的，这样不断去掉G中圈，最后得到一个G的 无圈连通子图T，它为G的一棵生成树。 定理1的证明实际上给出了连通图G的生成树的求法， 该方法称为破圈法。 利用破圈法，显然也可以求出任意图的一个生成森林

推论若G是(n,m)连通图，则m≥nl 连通图G的生成树一般不唯一！ (二)、生成树的计数 1、凯莱递推计数法 凯莱(Cayley1821一1895)：剑桥大学数学教授，著名 代数学家，发表论文数仅次于Erdos,Euler,,Cauchy.著 名成果是1854年定义了抽象群，并且得到著名定理：任 意一个群都和一个变换群同构。同时，他也是一名出色 的律师，作律师14年期间，发表200多篇数学论文，著 名定理也是在该期间发表的。 凯莱生成树递推计数公式是他在1889年建立的

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 5 推论 若G是(n, m)连通图，则m≧n-1 连通图G的生成树一般不唯一！ (二)、生成树的计数 1、凯莱递推计数法 凯莱(Cayley 1821—1895): 剑桥大学数学教授，著名 代数学家，发表论文数仅次于Erdos ,Euler, Cauchy. 著 名成果是1854年定义了抽象群，并且得到著名定理：任 意一个群都和一个变换群同构。同时，他也是一名出色 的律师，作律师14年期间，发表200多篇数学论文，著 名定理也是在该期间发表的。 凯莱生成树递推计数公式是他在1889年建立的

定义2图G的边e称为被收缩，是指删掉e后，把e的两 个端点重合，如此得到的图记为G.e 用τ(G)表示G的生成树棵数。 定理2(Cayley)设e是G的一条边，则有： (G)=t(G-e)+t(G e) 证明：对于G的一条边e来说，G的生成树中包含边e的 棵数为t(G.e),而不包含e的棵数为r(G-e)

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 定义2 图G的边e称为被收缩，是指删掉e后，把e的两 个端点重合，如此得到的图记为G.e e1 e5 e2 e4 e3 用τ(G)表示G的生成树棵数。 定理2 (Cayley) 设e是G的一条边，则有：  () ( ) ( ) G G e Ge     证明：对于G的一条边e来说，G的生成树中包含边e的 棵数为τ(G.e )，而不包含e的棵数为τ (G-e)

例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 7 例1，利用凯莱递推法求下图生成树的棵数。 共8棵生成树

凯莱公式的缺点之一是计算量很大，其次是不能具 体指出每棵生成树。 2、关联矩阵计数法 定义3：n×m矩阵的一个阶数为mim{n,m}的子方阵， 称为它的一个主子阵；主子阵的行列式称为主子行列式。 显然，当n<m时，nXm矩阵 个主子阵。 定理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 8 凯莱公式的缺点之一是计算量很大，其次是不能具 体指出每棵生成树。 2、关联矩阵计数法 定义3 ：n×m矩阵的一个阶数为min｛n, m｝的子方阵， 称为它的一个主子阵；主子阵的行列式称为主子行列式。 显然，当n<m时，n×m矩阵 个主子阵。 n C m 定理3 设Am是连通图G的基本关联矩阵的主子阵，则 Am非奇异的充分必要条件是相应于Am的列的那些边构 成G的一棵生成树。 证明：略

该定理给出了求连通图G的所有生成树的方法： (1)写出G的关联矩阵，进一步写出基本关联矩阵， 记住参考点； (2)找出基本关联矩阵的非奇异主子阵，对每个这样 的主子阵，画出相应的生成树

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 该定理给出了求连通图G的所有生成树的方法： (1) 写出G的关联矩阵，进一步写出基本关联矩阵， 记住参考点； (2) 找出基本关联矩阵的非奇异主子阵，对每个这样 的主子阵，画出相应的生成树

(2)找出基本关联矩阵的非奇异主子阵，对每个这样 的主子阵，画出相应的生成树。 例2，画出下图G的所有不同的生成树。 G 解：取4为参考点，G的基本关联矩阵为： d 0 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 (2) 找出基本关联矩阵的非奇异主子阵，对每个这样 的主子阵，画出相应的生成树。 例2，画出下图G的所有不同的生成树。 1 2 3 4 a b c d e G 解：取4为参考点，G的基本关联矩阵为： 11000 01110 00011 Af            abcde 1 2 3

共有10个主子阵，非奇异主子阵8个，它们是： 11 11

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 11 共有10个主子阵，非奇异主子阵8个，它们是： 1 2 3 4 a b d 1 110 011 001 A            abd 1 2 3 2 110 010 001 A            abe 1 2 3 1 2 3 4 a b e