第8章 计算机专业应用数学.pptVIP

图8.13返回图8.14返回图8.15返回图8.16返回图8.17返回图8.18返回图8.19返回图8.20返回图8.21返回图8.22返回图8.23返回图8.24返回*8.3图论及其应用8.3.4树树是图论中的一个重要概念.在1847年克希霍夫就提出用树的理论来研究电网络，1857年凯莱在计算有机化学中C2H2n+2的同分异构物数日时一也用到了树的理论.而树在计算机科学中应用更加广泛.本节介绍树的基本知识，其中谈到的图都假定为简单图.1.树的概念定义8.22一个连通无回路图称为树.树中度数为1的结点称为树叶(或终端结点)，度数大于1的结点称为分枝点(或内点，或非终端结点)一个无回路图称为森林.显然，若图G是森林，则G的每个连通分支是树.如图8.14(a)图所示的是一棵树;（b）图所示的是森林.上一页下一页返回8.3图论及其应用定理8.5一个(n,m)图G是树的充分必要条件是G连通且m=n-1.上一页下一页返回8.3图论及其应用定理8.G设T是一棵(n,m)树，则T有如下性质:(1)T中去掉任意一条边后，所得的图G是不连通的.(2)T中每一对结点间有且仅有一条通路相连.(3)在T中不相邻接的任意两结点间添加一条边后形成的图有且仅有一个回路.(4)若树T的结点数n≥2，则T至少有两片树叶.证明(1)如果G是连通的，那么G仍是树.由定理8.5知，G有n-1条边，即与T的边数相同，矛盾.(2)因为T连通，由定理8.3知，T的任一对结点u、v之间有一条通路相连.若u,v间通路不唯一，则T中必有回路，与树的定义矛盾.所以仅有一条通路连接u与v.上一页下一页返回8.3图论及其应用上一页下一页返回8.3图论及其应用由定理8.5所描述的树的特征得出:在结点数给定的所有图中，树是边数最少的连通图，是边数最多的无回路图.由此可知，在一个(n，m)图G中，若mn-1,则G是不连通的;若mn-1，则G必定有回路.2.生成树定义8.23若连通图G的生成子图是一棵树，则称该树是G的生成树，记为TG.生成树TG中的边称为树枝，图中其他边称为TG的弦，所有这些弦的集合称为TG的补.如图8.15(b)所示的树T1是图8.15(a)的生成树，而8.15(c)(d)所示的树T2,T3不是8.15(a)图的生成树一般的，图的生成树不唯一上一页下一页返回8.3图论及其应用例8-18某地要兴建5个工厂，拟修筑道路连接这5处.经勘测其道路可依如图8.16的无向边铺设.为使这5处都有道路相通，问至少要铺几条路?解这实际上是求G的生成树的边数问题.一般情况下，设连通图有n个结点，m条边.由树的性质知，T有n个结点，n-1条树枝，m-n+1条弦.在图8.16中，n=5，则n-1=5-1=4,所以至少要修4条路才行.3.最小生成树定义8.24设G=(V,E)是一连通的有权图，则G中具有最小权的生成树TG称为G的最小生成树.求最小生成树问题是有实际意义的.上一页下一页返回8.3图论及其应用上一页下一页返回8.3图论及其应用例8-19求图8.17中有权图的最小生成树.解因为图中n=8，所以按算法要执行n-1=7次，其过程见图8.17中(a)～(g)8.3.5根树及其应用1.根树、有序树、M叉树定义8.25一个有向图，若不考虑边的方向，它是一棵树，则这个有向图称为有向树一棵有向树，如果仅有一个结点的人度为0，其余所有结点的人度都为1,则称为根树，其中人度为0的结点称为根，出度为0的结点称为叶，出度不为0的结点称为分枝点或内点.如图8.18(a)表示一棵根树，其中v1为根，v2，v3为分枝点，其余结点为叶，一般情况下，习惯把根树的根画在上方，叶画在下方.这样就可以省去根树的箭头，如上一页下一页返回8.3图论及其应用图8.18(b).在根树中，称从树根到结点v的距离为该点的层次.这样对图8.17中的根树，v1的层次为0，v2、v3的层次为1，其余结点的层次均为2.我们用家族关系表示根树中各结点的关系.上一页下一页返回8.3图论及其应用定义8.28如果在根树中规定了每一层次上结点的次序，这样的根树称为有序树.在有序树中规定同一层次结点的次序是从左至右.在树的实际应用中，经常研究完全刀m叉树.定义8.29在根树中，若每个结点的出度小于或等于m，则称这棵树为m叉树.如果每个结点的出度恰好等于0