ppt8 生成树.pdf

1 Email: yc517922@ 图论及其应用任课教师:杨春数学科学学院 2本次课主要内容(一) 、生成树的概念与性质(二) 、生成树的计数(三) 、回路系统简介 3 1、生成树的概念(一) 、生成树的概念与性质定义 1 图G的一个生成子图 T如果是树,称它为 G的一棵生成树;若 T为森林,称它为 G的一个生成森林。生成树的边称为树枝, G中非生成树的边称为弦。例如: 粗边构成的子图为 G的生成树。图G4 2、生成树的性质定理 1 每个连通图至少包含一棵生成树。证明:如果连通图 G是树,则其本身是一棵生成树; 若连通图 G中有圈 C,则去掉 C中一条边后得到的图仍然是连通的,这样不断去掉 G中圈,最后得到一个 G的无圈连通子图 T,它为 G的一棵生成树。定理 1的证明实际上给出了连通图 G的生成树的求法,该方法称为破圈法。利用破圈法,显然也可以求出任意图的一个生成森林。 5 推论若G是(n, m) 连通图,则 m≧n-1 连通图 G的生成树一般不唯一! (二) 、生成树的计数 1、凯莱递推计数法凯莱( Cayley 1821 — 1895): 剑桥大学数学教授,著名代数学家,发表论文数仅次于 Erdos ,Euler, Cauchy. 著名成果是 1854 年定义了抽象群,并且得到著名定理:任意一个群都和一个变换群同构。同时,他也是一名出色的律师,作律师 14年期间,发表 200 多篇数学论文,著名定理也是在该期间发表的。凯莱生成树递推计数公式是他在 1889 年建立的。 6 定义 2 图G的边 e称为被收缩,是指删掉 e后,把 e的两个端点重合,如此得到的图记为 e 1e 5e 2e 4e 3用τ(G) 表示 G的生成树棵数。定理 2(Cayley) 设e是G的一条边,则有: ( ) ( ) ( ) G G e G e ? ? ?? ???证明:对于 G的一条边 e来说, G的生成树中包含边 e的棵数为 ,而不包含 e的棵数为 G-e. 7 例1,利用凯莱递推法求下图生成树的棵数。共8棵生成树。 8 凯莱公式的缺点之一是计算量很大,其次是不能具体指出每棵生成树。 2、关联矩阵计数法定义 3 :n×m矩阵的一个阶数为 min { n, m }的子方阵,称为它的一个主子阵;主子阵的行列式称为主子行列式。显然,当 n<m 时, n×m矩阵个主子阵。 nmC 定理 3 设A m是连通图 G的基本关联矩阵的主子阵,则 A m非奇异的充分必要条件是相应于 A m的列的那些边构成G的一棵生成树。证明:略 9 该定理给出了求连通图 G的所有生成树的方法: (1) 写出 G的关联矩阵,进一步写出基本关联矩阵, 记住参考点; (2) 找出基本关联矩阵的非奇异主子阵,对每个这样的主子阵,画出相应的生成树。 10 (2) 找出基本关联矩阵的非奇异主子阵,对每个这样的主子阵,画出相应的生成树。例2,画出下图 G的所有不同的生成树。 1234 a bcdeG解:取 4为参考点, G的基本关联矩阵为: 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 fA ? ?? ??? ?? ?? ? abcde123