离散数学图论-树x

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

1、第16章树第十六章树一、无向树1）定义：连通无回路（初级回路或简单回路）的无向图称为无向树，或简称树常用T表示树，平凡图称为平凡树．若无向图G至少有两个连通分支，则称G为森林．在无向树中，悬挂顶点称为树叶，度数大于或等于2的顶点称为分支结点．2）树的等价定义设G＝是n阶m条边的无向图，则下面各命题是等价的：(1)G是连通无回路（树）．可通过循环证明(2)G中任意两个顶点之间存在惟一的路径．（连通则存在路径，若不唯一，不同路径则构成回路）(3)G中无回路且m=n-1．有长大于等于2的回路都与唯一路径

2、矛盾。对结点进行归纳：n=1平凡图m=0=n-1；设n=k成立；n=k+1时两个结点有唯一的路，去掉则为两个连通分支（各自满足假设）m=m1+m2+1=n1-1+n2-1+1=n1+n2-1=n-1(4)G是连通的且m=n-1．若不连通，对各个(s>=2)连通分支是树且有mi=ni-1m=n-ss>=2矛盾(5)G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的初级回路．(6)G是连通的，但删去任何一条边后，所得图不连通．G连通：若存在二个结点无通路，则在二个结点添加边后不

3、会出现回路3）树的性质对于给定的无向图—树是边数最小的连通图（mn-1则有回路）结点的度：Σd(vi)=2m=2(n-1)定理：设T是n阶非平凡的无向树，则T中至少有片树叶设：有x片树叶，其余结点度数至少为2x+2(n-x)<=2(n-1)例：无向树T中度为4、3、2的结点各一个，其余为树叶，树叶＝？4+3+2+k=2(3+k-1)4)阶数n比较小的所有非同构的无向树．例1：画出6阶所有非同构的无向树．m=n-1=5从树的节点之和来分析：结点之和为10分配给6个

4、结点111115111124111133111223112222例2：7阶无向树中有3片树叶和1个3度顶点，其余3个顶点的度数均无1和3．试画出满足要求的所有非同构的无向树．解答：从树的节点之和来分析：7阶无向树的边数m=（），于是∑d(vi)＝12＝3＋3+d(v5)+d(v6)+d(v7)1112223加入2，2，2如何组成结点的度数序列使之不同构主要分析：度为3的结点v与其三个邻接点的关系邻接关系不同就能得到不同构的树三个邻接点度数：112122222§16.2生成树（一些连通图不是树，但它的子图是树

5、——重要的是生成树）1、定义：设T是无向图G的子图并且为树，则称T为G的树．若T是G的树且为生成子图，则称T是G的生成树．设T是G的生成树，∀e∈E(G)，若e∈E(T)，则称e为T的树枝，否则称e为T的弦．并称导出子图G[E(G)—E(T)]为T的余树，记作．注：不一定连通，也不一定不含回路.(无规律)2、生成树的性质1）定理：无向图G具有生成树当且仅当G是连通图（破圈法-不断去掉回路）2）设G为n阶m条边的无向连通图，则m=

6、E(G)

7、≥

8、E(T)

9、=n-1．3）设G是n阶m条边的无向连通图，T为G的生

10、成树，则T的余树中含m–n+1条边(即T有m-n+1条弦)4）任何无向连通图G，都存在生成树无向连通图G的生成树是不唯一的实边图为该图的一棵生成树T，余树为虚边所示，它不连通，同时也含回路3、生成树的应用要建6个工厂，修建连接的通路（见图），为使5处都有路相通，至少要建几条路？如何铺设？由于n=6所以建5条路即可4、无向图G的生成树的确定：二种方法：1、破圈法：每次去掉回路中的一条边，去掉总数为m-n+1条弦2、避圈法：由一个结点开始选一条边，逐渐添加与边关联的结点（只要不构成回路即可）直到所有结点被添加，

11、(挑选n-1条边）3、带权图的最小生成树(1)定义5设无向连通带权图G＝，T是G的一棵生成树．T的各边权之和称为T的权，记作W(T)；G的所有生成树中权最小的生成树称为G的最小生成树。(2)最小生成树的求法（这里介绍避圈法Kruskal算法)设n阶无向连通带权圈G＝有m条边，不妨设G中没有环(否则，可以将所有的环先删去)，将m条边按权从小到大顺序排列，设为e1,e2，…,em；取e1在T中，然后依次检查e2，e3，…，em.若ej(j≥2)与已在T中的边不能构成回路，则取ej在T

12、中，否则弃去ej；算法停止时得到的T为G的最小生成树。避圈法Kruskal算法(n-1次)1121241245(1)(2)(3)(4)破圈法(1)512436(3)1245(2)12435作业：P319习题十六1、2、3、4、5、13§16.3根树及其应用有向树：设D是有向图，若D的基图是无向树，则称D为有向树.有向树中,根树最重要,故只讨论根树.一、根树1、定义：设T是n(n≥2)阶有向树,若T中有一个顶点的入