离散数学-图论-树

《离散数学-图论-树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树LuChaojun,SJTU1注意主要参考曹老师书：P302-310部分参考清华教材作业中红色标记为选做树结构简介•树(tree)是用来表示层次结构的图.–称为树是因为这种图可以画成树状:常倒过来画(即树根在上,树叶在下).•树结构的例子:–化学:Cayley最早(1857年)用树来研究化合物结构.–计算机科学技术:二叉查找树,B树,R树,…–信息管理:目录系统–管理:层次式组织机构–生物学:进化树–商务:传销(金字塔销售模式)LuChaojun,SJTU3树的定义•定义:无圈（回路）连通无向图称为无向树,简称树.–树中最长路的长度称为树的高度;–边也称为树枝;–度为1的顶

2、点称为树叶,即悬点;•平凡图（只有一个顶点的图）是树,称为平凡树.•树必不含重边和环,故是简单图.•定义:无圈（回路）无向图称为森林.–森林可能不是连通的.–森林的每个连通支都是树.树的等价定义•定理:设G是顶点数n2的图,则下列性质互相等价:(1)G是树(即连通且无圈);满足连通,无圈,有n1条(2)G连通且有n1条边;边之任意两个就是树(3)G有n1条边且无圈;(4)G连通且每条边都是割边;树是边数最少的连(5)G无圈,但任意增加一边通图;也是边数最多的无圈图.后恰有一个圈;(6)T的任意两顶点间有唯一通道.树的其他性质•设树T的顶点数n2,则T中必有树叶.证法1:若

3、各顶点度都2,则总度数2n2m2(n1).证法2:考虑从任一顶点v出发沿边前进,走过的边不重复,则必止步于某树叶.•设树T的顶点数n2,则T至少有两个树叶.证明:同上面证法2,考虑从一树叶出发前进,必止步于另一个树叶.•若森林F有n个结点和k个连通支,则F有nk条边.生成树•定义:如果T是图G的生成子图,而且是树,则称T是G的生成树(或支撑树).•图G有生成树iffG是连通的.:显然:不断对G破除圈即可得到生成树.•若图G本身不是树,则其生成树不唯一.LuChaojun,SJTU7一个连通图的生成树可能不唯一。因为在取定一个回路后，就可以从中去掉任一条边，去掉的边

4、不一样，故可能得到不同的生成树。ccc67677b5d5bdbd3143141a2eeaae)(a))(c(b在上图(a)中，删去边2,3,5，就得到生成树(b)，若删去边2，4，6,可得到生成树(c)。余树•定义:设T是G的生成树,则从E(G)删去E(T)中的边及,所构成的G的子图称为T的余树T.–注意:余树不一定连通，也不一定无回路，=>余树本身不一定是树,更不一定是生成树。•定理:设G是连通图,T是G的生成树.(1)则T有mn1条边.(2)若C是G中圈,则E(T)E(C).dadaadfefefebbcbcc(a)(b)(c)(a)G(b)生成树(c)余树构造生成树

5、•破圈法•广度优先搜索(BFS)–从顶点s出发,标记其邻点为1(s);u上标记k(v)的含义:u与s距离是k,u到s的最短路上的上一个顶点是v–从对每个标记为k(v)的顶点u,若其邻点未标记,则标记为k+1(u);–直至没有与已标记顶点相邻的未标记顶点.–若顶点v标记k(u),则取边uv,所有这种边的集合即构成生成树.–结果不唯一•深度优先搜索(DFS)最小生成树•最小生成树问题:设G是带权连通图,求G的总权值最小的生成树.•应用例:在若干加油站之间铺设输油管道,在确保各加油站供应的条件下,要使建设费用最小.Kruskal算法•算法思想:不断加入权值最小的边,并保持无圈.•Kru

6、skal算法的描述如下（曹老师书上为等价描述）:T←Φ。当

7、T

8、

9、T

10、

11、'T.由算法的k挑选规则可推知:以e换e'所得T''也是生成树(因k为连通且有n1条边),且其权值不会比T'大,故也是最小生成树.但T''与T有更多公共e,...,e,矛盾.1k故必有kn,即TT'.Prim算法•算法思想:初始U为任一顶点,然后不断向U中加入距离U最近的顶点.(1)T;U{u};(2)从V(G)U中选择与U中顶点相邻且边权值最小的顶点v:将v加入U,该边加入T;(3)重复执行(2),直至UV.Prim算法实例UU1115561566