《图论及其应用》课程教学课件（PPT讲稿）第二章 树 2-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 1 本次课主要内容 (一)、生成树的概念与性质 (二)、生成树的计数 (三)、回路系统简介

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

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