图论及其应用ppt8.ppt
《图论及其应用ppt8.ppt》由会员分享,可在线阅读,更多相关《图论及其应用ppt8.ppt(32页珍藏版)》请在三一文库上搜索。
1、1,Email: ,图论及其应用,任课教师:杨春,数学科学学院,2,本次课主要内容,(一)、生成树的概念与性质,(二)、生成树的计数,(三)、回路系统简介,3,1、生成树的概念,(一)、生成树的概念与性质,定义1 图G的一个生成子图T如果是树,称它为G的一棵生成树;若T为森林,称它为G的一个生成森林。,生成树的边称为树枝,G中非生成树的边称为弦。,例如:,粗边构成的子图为G的生成树。,4,2、生成树的性质,定理1 每个连通图至少包含一棵生成树。,证明:如果连通图G是树,则其本身是一棵生成树;,若连通图G中有圈C,则去掉C中一条边后得到的图仍然是连通的,这样不断去掉G中圈,最后得到一个G的无圈连
2、通子图T,它为G的一棵生成树。,定理1的证明实际上给出了连通图G的生成树的求法,该方法称为破圈法。,利用破圈法,显然也可以求出任意图的一个生成森林。,5,推论 若G是(n, m)连通图,则mn-1,连通图G的生成树一般不唯一!,(二)、生成树的计数,1、凯莱递推计数法,凯莱(Cayley 18211895): 剑桥大学数学教授,著名代数学家,发表论文数仅次于Erdos ,Euler, Cauchy. 著名成果是1854年定义了抽象群,并且得到著名定理:任意一个群都和一个变换群同构。同时,他也是一名出色的律师,作律师14年期间,发表200多篇数学论文,著名定理也是在该期间发表的。,凯莱生成树递推
3、计数公式是他在1889年建立的。,6,定义2 图G的边e称为被收缩,是指删掉e后,把e的两个端点重合,如此得到的图记为G.e,用(G)表示G的生成树棵数。,定理2(Cayley) 设e是G的一条边,则有:,证明:对于G的一条边e来说,G的生成树中包含边e的棵数为G.e ,而不包含e的棵数为G-e.,7,例1,利用凯莱递推法求下图生成树的棵数。,共8棵生成树。,8,凯莱公式的缺点之一是计算量很大,其次是不能具体指出每棵生成树。,2、关联矩阵计数法,定义3 :nm矩阵的一个阶数为minn, m的子方阵,称为它的一个主子阵;主子阵的行列式称为主子行列式。,显然,当nm时,nm矩阵 个主子阵。,定理3
4、 设Am是连通图G的基本关联矩阵的主子阵,则Am非奇异的充分必要条件是相应于Am的列的那些边构成G的一棵生成树。,证明:必要性,9,设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的关联矩阵,进一步写出基本关联
5、矩阵,记住参考点;,10,(2) 找出基本关联矩阵的非奇异主子阵,对每个这样的主子阵,画出相应的生成树。,例2,画出下图G的所有不同的生成树。,解:取4为参考点,G的基本关联矩阵为:,11,共有10个主子阵,非奇异主子阵8个,它们是:,12,13,14,注:该方法的优点是不仅指出生成树棵数,而且能绘出所有不同生成树;缺点是找所有非奇异主子阵计算量太大!,15,定理3 (矩阵树定理) 设G是顶点集合为V(G)=v1,v2,vn,的图,设A=(aij)是G的邻接矩阵,C=(cij)是n阶方阵,其中:,3、矩阵树定理,则G的生成树棵数为C的任意一个余子式的值。,说明:(1) 该定理是由物理学家克希荷
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 论及 应用 ppt8
链接地址:https://www.31doc.com/p-3401204.html