图论生成树的概念与性质课件.ppt

1、 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 图论及其应用图论及其应用应用数学学院应用数学学院 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本次课主要内容本次课主要内容(一一)、生成树的概念与性质、生成树的概念与性质(二二)、生成树的计数、生成树的计数(三三)、回路系统简介、回路系统简介 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 31、生成树的概念、生成树的概念(一一)、生成树的概念与性质、生成树

2、的概念与性质定义定义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 42、生成树的性质、生成树的性质定理定理1 每个连通图至少包含一棵生成树。每个连通图至少包含一棵生成树。证明：如果连通图证明：如果连通图G是树

3、，则其本身是一棵生成树；是树，则其本身是一棵生成树；若连通图若连通图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

4、 1 0.5 0 0.5 1 n 5推论推论 若若G是是(n,m)连通图，则连通图，则mn-1n-1连通图连通图G的生成树一般不唯一！的生成树一般不唯一！(二二)、生成树的计数、生成树的计数1、凯莱递推计数法、凯莱递推计数法 凯莱凯莱(Cayley 18211895):剑桥大学数学教授，著名剑桥大学数学教授，著名代数学家，发表论文数仅次于代数学家，发表论文数仅次于Erdos,Euler,Cauchy.著著名成果是名成果是1854年定义了抽象群，并且得到著名定理：任年定义了抽象群，并且得到著名定理：任意一个群都和一个变换群同构。同时，他也是一名出色意一个群都和一个变换群同构。同时，他也是一名出色

5、的律师，作律师的律师，作律师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 6定义定义2 图图G的边的边e称为被收缩，是指删掉称为被收缩，是指删掉e后，把后，把e的两的两个端点重合，如此得到的图记为个端点重合，如此得到的图记为G.ee1e5e2e4e3用用(G)(G)表示表示G G的生成树棵数。的生成树棵数。定理定理2(Cayley)设

6、设e是是G的一条边，则有：的一条边，则有：()()()GGeG e证明：对于证明：对于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 7例例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 8 凯莱公式的缺点之一是计算量很大，其次是不能具凯莱公式

7、的缺点之一是计算量很大，其次是不能具体指出每棵生成树。体指出每棵生成树。2、关联矩阵计数法、关联矩阵计数法定义定义3：nm矩阵的一个阶数为矩阵的一个阶数为minn,m的子方阵，的子方阵，称为它的一个主子阵；主子阵的行列式称为主子行列式。称为它的一个主子阵；主子阵的行列式称为主子行列式。显然，显然，nm矩阵共有矩阵共有 个主子阵。个主子阵。nmC定理定理3 设设Am是连通图是连通图G的基本关联矩阵的主子阵，则的基本关联矩阵的主子阵，则Am非奇异的充分必要条件是相应于非奇异的充分必要条件是相应于Am的列的那些边构的列的那些边构成成G的一棵生成树。的一棵生成树。证明：必要性证明：必要性 0.8 1

8、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 设设Am是是Af的一个非奇异主子阵，并设与的一个非奇异主子阵，并设与Am的列相对的列相对应的边构成应的边构成G的子图的子图Gm.由于由于Am有有n-1行，故行，故Gm应该有应该有n-1个顶点个顶点(包括参考点包括参考点);又又Am有有n-1列列,所以所以Gm有有n-1条边。而条边。而Am非奇异，故非奇异，故Am的的秩为秩为n-1,即即Gm连通。这说明连通。这说明Gm是是n个点，个点，n-1条边的连通条边的连通图，所以，它是树。图，所以，它是树。充分性充分性 如果如果Am的列对应的边作成的列对应的

9、边作成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 10 (2)找出基本关联矩阵的非奇异主子阵，对每个这样找出基本关联矩阵的非奇异主子阵，对每个这样的主子阵，画出相应的生成树。的主子阵，画出相应的生成树。例例2，画

10、出下图，画出下图G的所有不同的生成树。的所有不同的生成树。1234abcdeG解：取解：取4为参考点，为参考点，G的基本关联矩阵为：的基本关联矩阵为：110000111000011fAabcde123 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个，它们是：个，它们是：1234abd1110011001Aabd1232110010001Aabe1231234abe 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、 123100011001Aacd1234100010001Aace1231234acd1234ace 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 135100010011Aade1236100111001Abcd1233124ade1234bcd 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 147100110001Aade1238100110011Abde1231234bce1234bde注：该方法的优点是不仅指出生成树棵数，而且能绘注：该方法的优点是不仅指出生成树

12、棵数，而且能绘出所有不同生成树；缺点是找所有非奇异主子阵计算出所有不同生成树；缺点是找所有非奇异主子阵计算量太大！量太大！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 15定理定理3(矩阵树定理矩阵树定理)设设G是顶点集合为是顶点集合为V(G)=v1,v2,vn,的图，设的图，设A=(aij)是是G的邻接矩阵，的邻接矩阵，C=(cij)是是n阶方阵，其中：阶方阵，其中：3、矩阵树定理、矩阵树定理(),iijijd vijcaij则则G的生成树棵数为的生成树棵数为C的任意一个余子式的值。的任意一个余子式的值。说明：说明：(1)该定理是

13、由物理学家克希荷夫提出的。他于该定理是由物理学家克希荷夫提出的。他于1824年出生于普鲁士的哥尼斯堡。年出生于普鲁士的哥尼斯堡。1845年因宣布著名的克年因宣布著名的克希荷夫电流电压定律而闻名，希荷夫电流电压定律而闻名，1847年大学毕业时发表了生年大学毕业时发表了生成树计数文章，给出了矩阵树定理。他的一生主要花在实成树计数文章，给出了矩阵树定理。他的一生主要花在实验物理上。担任过德国柏林数学物理会主席职务。验物理上。担任过德国柏林数学物理会主席职务。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 16(2)矩阵树定理的证明很复杂，在

14、此略去证明；矩阵树定理的证明很复杂，在此略去证明；(3)定理中的矩阵定理中的矩阵C又称为图的拉普拉斯矩阵，又可定又称为图的拉普拉斯矩阵，又可定义为：义为：()()CD GA G其中，其中，D(G)是图的度对角矩阵，即主对角元为对应顶是图的度对角矩阵，即主对角元为对应顶点度数，其余元素为点度数，其余元素为0。A(G)是图的邻接矩阵。是图的邻接矩阵。图的拉普拉斯矩阵特征值问题是代数图论或组合矩图的拉普拉斯矩阵特征值问题是代数图论或组合矩阵理论的主要研究对象之一。该问题因为在图论、计算阵理论的主要研究对象之一。该问题因为在图论、计算机科学、流体力学、量子化学和生物医学中的重要应用机科学、流体力学、量

15、子化学和生物医学中的重要应用而受到学者们的高度重视。研究方法大致有而受到学者们的高度重视。研究方法大致有3种：代数种：代数方法、几何方法和概率方法。方法、几何方法和概率方法。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 17例例3 利用矩阵树定理求下图生成树的棵数。利用矩阵树定理求下图生成树的棵数。v4v1v2v3解：图的拉氏矩阵为：解：图的拉氏矩阵为：2110121011310011C一行一列对应的余子式为：一行一列对应的余子式为：1 1210(1)1310113 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1

16、.5 2 1 0.5 0 0.5 1 n 18例例4 证明证明(K Kn n)=n)=nn-2n-2(教材上定理教材上定理7 7）证明：容易写出证明：容易写出Kn的拉氏矩阵为：的拉氏矩阵为：一行一列对应的余子式为：一行一列对应的余子式为：111111()111nnnC Kn1 1111111(1)111nnn所以：所以：2()nnKn 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 19注：例注：例4的证明有好几种不同方法。用矩阵树定理证明是的证明有好几种不同方法。用矩阵树定理证明是最简单的方法。最简单的方法。1967年，加拿大的年，

17、加拿大的Moon用了用了10种不同方种不同方法证明，之后有人给出了更多证明方法。法证明，之后有人给出了更多证明方法。Moon的学术生涯主要是对树和有向图问题进行研究。的学术生涯主要是对树和有向图问题进行研究。同时，正如大多数科学家一样，他对音乐也很感兴趣。他同时，正如大多数科学家一样，他对音乐也很感兴趣。他还认为：当一个人发现了新事物，而且很难对非数学工作还认为：当一个人发现了新事物，而且很难对非数学工作者解释该发现时，他就会产生一种满足喜悦感。者解释该发现时，他就会产生一种满足喜悦感。例例5 证明：若证明：若e为为Kn的一条边，则：的一条边，则：3()(2)nnKenn证法一：若证法一：若e

18、为为Kn的一条边，由的一条边，由Kn中的边的对称性以及每中的边的对称性以及每棵生成树的边数为棵生成树的边数为n-1，Kn的所有生成树的总边数为：的所有生成树的总边数为：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 20所以，每条边所对应的生成树的棵数为：所以，每条边所对应的生成树的棵数为：2(1)nnn所以，所以，K n-e 对应的生成树的棵数为：对应的生成树的棵数为：23(1)21(1)2nnnnnn n233()2(2)nnnnKennnn证法二：假设在证法二：假设在Kn中去掉的边中去掉的边e=v1vn,则则Kn-e的拉氏矩阵的

19、拉氏矩阵为：为：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 21于是由矩阵树定理：于是由矩阵树定理：210111012nnCn11111111()11111112nnnKenn11111110111111101111111 011111111nnnnnnn 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 22232nnnn32nnn(三三)、回路系统简介、回路系统简介定义定义4 设设T是连通图是连通图G的一棵生成树，把属于的一棵生成树，把属于G但不属于但不属于T的边称为的

20、边称为G关于关于T的连枝，的连枝，T中的边称为中的边称为G关于关于T的树枝。的树枝。在上图中，红色边导出图的一棵生成树。则红色边为在上图中，红色边导出图的一棵生成树。则红色边为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 23定义定义5 设设T是连通图是连通图G的一棵生成树，由的一棵生成树，由G的对应于的对应于T一条连一条连枝与枝与T中树枝构成的唯一圈中树枝构成的唯一圈C，称为，称为G关于关于T的一个基本圈或的一个基本圈或

21、基本回路。若基本回路。若G是是(n,m)连通图，把连通图，把G对应于对应于T的的n-m+1个基本个基本回路称为回路称为G对应于对应于T的基本回路组。记为的基本回路组。记为Cf.abcdeGaceT基本回路为：基本回路为：abcC1cdeC2 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 24基本回路的性质基本回路的性质:定理定理4 设设T是连通图是连通图G=(n,m)的一棵生成树的一棵生成树,C1,C2,Cn-m+1是是G对应于对应于T的基本回路组。定义：的基本回路组。定义：1.Gi=Gi,0.Gi=,G Gi i是是G G的回的回

22、路。则路。则G G的回路组作成的集合对于该乘法和图的对称差运算来的回路组作成的集合对于该乘法和图的对称差运算来说作成数域说作成数域F=F=0,1上的上的n-m+1维向量空间。维向量空间。证明证明:(1)非空、两闭、非空、两闭、8条容易证明。条容易证明。(2)首先证明首先证明C1,C2,Cn-m+1线性无关。线性无关。若不然，设若不然，设C1,C2,Cn-m+1线性相关，那么存在一组不全为线性相关，那么存在一组不全为零的数零的数a1,a2,an-m+1,使得：使得：112211n mn ma Ca CaC 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0

23、 0.5 1 n 25但是，任意两个基本回路包含两条不同连枝，所以，若某个但是，任意两个基本回路包含两条不同连枝，所以，若某个ak0,则则112211n mn ma Ca CaC 矛盾！矛盾！其次证明其次证明G的任意一个回路均可由的任意一个回路均可由C1,C2,Cn-m+1线性表出。线性表出。设设B是是G的任一回路，显然，它至少含一条连枝，不失一般性，的任一回路，显然，它至少含一条连枝，不失一般性，令：令：121,jjkiiiiiBeeeee其中：其中：121,jjkiiiiieeeee为连枝，为树枝 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0

24、0.5 1 n 26令：令：1212,jjiiiiiieeeCCC又设包含连枝的基本回路为121jiiiBCCC显然，显然，B1中只含有中只含有B中连枝，于是中连枝，于是BB B1 1只含树枝不含回路。只含树枝不含回路。但是，两个回路的环和一定是回路，这就导出矛盾！但是，两个回路的环和一定是回路，这就导出矛盾！定理定理4说明，连通图说明，连通图G的所有回路作成子图空间的一个子空间，的所有回路作成子图空间的一个子空间，该空间称为回路空间或回路系统。该空间称为回路空间或回路系统。例例6 求下图求下图G的回路空间的一个基底和它的全部元素。的回路空间的一个基底和它的全部元素。0.8 1 0.6 0.4

25、 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 27解：取解：取G的一棵生成树的一棵生成树T为：为：GabcdefghabdgTG对于生成树对于生成树T的基本回路为：的基本回路为：1,Ca b c2,Ca b d e3,Ca b d g h4,Cd f 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 28C1abc图形为：图形为：C2abdeC4dfgabdghC3所有可能的环和为：所有可能的环和为：112,BCCc d e213,BCCc d g h314,BCCa b c d f g423,B

26、CCe g h524,BCCa b e f g634,BCCa b f h7123,BCCCa b c e g h 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 298124,BCCCc e f g9134,BCCCc f h10234,BCCCd e f h111234,BCCCCa b c d e f hB1cdeB2cdghB3abcdfgB4eghB5abefg 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 30B6abfhB2abcdefhB2cefgB7abceghB2cfhB2defh 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 31 作业作业 P43 习题习题2：12,14,15 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 32Thank You!