图论及其应用 应用数学学院 1 本次课主要内容 (一)、生成树的概念与性质 (二)、生成树的计数 (三)、回路系统简介 2 1、生成树的概念 (一)、生成树的概念与性质 定义1 图G的一个生成子图T如果是树，称它为G的一棵 生成树；若T为森林，称它为G的一个生成森林 生成树的边称为树枝，G中非生成树的边称为弦 例如： 粗边构成的子图为G的生成树 图G 3 2、生成树的性质 定理1 每个连通图至少包含一棵生成树 证明：如果连通图G是树，则其本身是一棵生成树； 若连通图G中有圈C，则去掉C中一条边后得到的图仍 然是连通的，这样不断去掉G中圈，最后得到一个G的 无圈连通子图T，它为G的一棵生成树 定理1的证明实际上给出了连通图G的生成树的求法 ，该方法称为破圈法 利用破圈法，显然也可以求出任意图的一个生成森林 4 推论 若G是(n, m)连通图，则m≧n-1 连通图G的生成树一般不唯一！ (二)、生成树的计数 1、凯莱递推计数法 凯莱(Cayley 1821—1895): 剑桥大学数学教授，著名 代数学家，发表论文数仅次于Erdos ,Euler, Cauchy. 著 名成果是1854年定义了抽象群，并且得到著名定理：任 意一个群都和一个变换群同构。
同时，他也是一名出色 的律师，作律师14年期间，发表200多篇数学论文，著 名定理也是在该期间发表的 凯莱生成树递推计数公式是他在1889年建立的 5 定义2 图G的边e称为被收缩，是指删掉e后，把e的两个 端点重合，如此得到的图记为G.e e1 e5 e2 e4e3 用τ(G)表示G的生成树棵数 定理2(Cayley) 设e是G的一条边，则有： 证明：对于G的一条边e来说，G的生成树中包含边e的 棵数为G.e ，而不包含e的棵数为G-e. 6 例1，利用凯莱递推法求下图生成树的棵数 共8棵生成树 7 凯莱公式的缺点之一是计算量很大，其次是不能具 体指出每棵生成树 2、关联矩阵计数法 定义3 ：n×m矩阵的一个阶数为min｛n, m｝的子方阵 ，称为它的一个主子阵；主子阵的行列式称为主子行列 式 显然，n×m矩阵共有 个主子阵 定理3 设Am是连通图G的基本关联矩阵的主子阵，则 Am非奇异的充分必要条件是相应于Am的列的那些边构 成G的一棵生成树 证明：必要性 8 设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的列对应的边作成G的一棵生成树，因树是连通 的，所以，它对应的基本关联矩阵Am非奇异 该定理给出了求连通图G的所有生成树的方法： (1) 写出G的关联矩阵，进一步写出基本关联矩阵， 记住参考点； 9 (2) 找出基本关联矩阵的非奇异主子阵，对每个这样 的主子阵，画出相应的生成树 例2，画出下图G的所有不同的生成树 12 3 4 a b c d e G 解：取4为参考点，G的基本关联矩阵为： abcde 1 2 3 10 共有10个主子阵，非奇异主子阵8个，它们是： 12 3 4 a b d abd 1 2 3 abe 1 2 3 12 3 4 a b e 11 acd 1 2 3 ace 1 2 3 12 3 4 a c d 12 3 4 a c e 12 ade 1 2 3 bcd 1 2 3 3 12 4 ad e 12 3 4 b c d 13 ade 1 2 3 bde 1 2 3 12 3 4 b c e 12 3 4 b d e 注：该方法的优点是不仅指出生成树棵数，而且能绘 出所有不同生成树；缺点是找所有非奇异主子阵计算 量太大！ 14 定理3 (矩阵树定理) 设G是顶点集合为V(G)=｛v1,v2,…,vn｝, 的图，设A=(aij)是G的邻接矩阵，C=(cij)是n阶方阵，其中： 3、矩阵树定理 则G的生成树棵数为C的任意一个余子式的值。
说明：(1) 该定理是由物理学家克希荷夫提出的他于 1824年出生于普鲁士的哥尼斯堡1845年因宣布著名的克 希荷夫电流电压定律而闻名，1847年大学毕业时发表了生 成树计数文章，给出了矩阵树定理他的一生主要花在实 验物理上担任过德国柏林数学物理会主席职务 15 (2) 矩阵树定理的证明很复杂，在此略去证明； (3) 定理中的矩阵C又称为图的拉普拉斯矩阵，又可定 义为： 其中，D(G)是图的度对角矩阵，即主对角元为对应顶 点度数，其余元素为0A(G)是图的邻接矩阵 图的拉普拉斯矩阵特征值问题是代数图论或组合矩 阵理论的主要研究对象之一该问题因为在图论、计算 机科学、流体力学、量子化学和生物医学中的重要应用 而受到学者们的高度重视研究方法大致有3种：代数 方法、几何方法和概率方法 16 例3 利用矩阵树定理求下图生成树的棵数 v4 v1v2 v3 解：图的拉氏矩阵为： 一行一列对应的余子式为： 17 例4 证明τ(Kn)=nn-2(教材上定理7） 证明：容易写出Kn的拉氏矩阵为： 一行一列对应的余子式为： 所以： 18 注：例4的证明有好几种不同方法用矩阵树定理证明是 最简单的方法1967年，加拿大的Moon用了10种不同方 法证明，之后有人给出了更多证明方法。
Moon的学术生涯主要是对树和有向图问题进行研究 同时，正如大多数科学家一样，他对音乐也很感兴趣 他还认为：当一个人发现了新事物，而且很难对非数学工 作者解释该发现时，他就会产生一种满足喜悦感 例5 证明：若e为Kn的一条边，则： 证法一：若e为Kn的一条边，由Kn中的边的对称性以及每 棵生成树的边数为n-1，Kn的所有生成树的总边数为： 19 所以，每条边所对应的生成树的棵数为： 所以，K n - e 对应的生成树的棵数为： 证法二：假设在Kn中去掉的边e=v1vn, 则Kn-e的拉氏矩阵 为： 20 于是由矩阵树定理： 21 (三)、回路系统简介 定义4 设T是连通图G的一棵生成树，把属于G但不属于T的 边称为G关于T的连枝，T中的边称为G关于T的树枝 在上图中，红色边导出图的一棵生成树则红色边为G对 应于该生成树的树枝，白色边为G对应于该生成树的连枝 G 22 定义5 设T是连通图G的一棵生成树，由G的对应于T一条连枝 与T中树枝构成的唯一圈C，称为G关于T的一个基本圈或基 本回路若G是(n, m)连通图，把G对应于T的n-m+1个基本回 路称为G对应于T的基本回路组记为Cf. a b c d e G a c e T 基本回路为： a b c C1 c d e C2 23 基本回路的性质: 定理4 设T是连通图G=(n, m) 的一棵生成树,C1, C2,…,Cn-m+1是 G对应于T的基本回路组。
定义：1.Gi=Gi , 0.Gi=Φ,Gi是G的回 路则则G的回路组组作成的集合对对于该该乘法和图图的对对称差运算 来说说作成数域F=｛0,1｝上的n-m+1维向量空间 证明: (1) 非空、两闭、8条容易证明 (2) 首先证明C1, C2,…,Cn-m+1线性无关 若不然，设C1, C2,…,Cn-m+1线性相关，那么存在一组不全为 零的数a1,a2,…,an-m+1,使得： 24 但是，任意两个基本回路包含两条不同连枝，所以，若某个 ak≠0, 则则 矛盾！ 其次证明G的任意一个回路均可由C1, C2,…,Cn-m+1线性表出 设B是G的任一回路，显然，它至少含一条连枝，不失一般性 ，令： 其中： 25 令： 显然，B1中只含有B中连枝，于是BΔB1只含树枝不含回路 但是，两个回路的环和一定是回路，这就导出矛盾！ 定理4说明，连通图G的所有回路作成子图空间的一个子空间 ，该空间称为回路空间或回路系统 例6 求下图G的回路空间的一个基底和它的全部元素 26 解：取G的一棵生成树T为： G a b c d e f g h a b dg T G对于生成树T的基本回路为： 27 C1 a b c 图形为： C2 a b d e C4 d f g a b dg h C3 所有可能的环和为： 28 B1 c d e B2 c dg h B3 a b c d f g B4 e g h B5 a b e f g 29 B6 a b f h B2 a b c d e f h B2 c e f g B7 a b c e g h B2 c f h B2 d e f h 30 作业 P43 习题2 ： 12, 14, 15 31 Thank You ! 32 。