离散数学-图论-树.pptxVIP

第16章树;第十六章树

一、无向树

1〕定义：连通无回路〔初级回路或简单回路〕的无向图称为无向树，或简称树

常用T表示树，平凡图称为平凡树．

假设无向图G至少有两个连通分支，那么称G为森林．

在无向树中，悬挂顶点称为树叶，度数大于或等于2的顶点称为分支结点．

2〕树的等价定义

设G＝V，E是n阶m条边的无向图，

那么下面各命题是等价的：

(1)G是连通无回路〔树〕．

可通过循环证明

(2)G中任意两个顶点之间存在惟一的路径．

〔连通那么存在路径，假设不唯一，不同路径那么构成回路〕

(3)G中无回路且m=n-1．

有长大于等于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-1

m=n-ss=2矛盾;(5)G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的初级回路．

(6)G是连通的，但删去任何一条边后，所得图不连通．

G连通：假设存在二个结点无通路，那么在二个结点添加边后不会出现回路

3〕树的性质

对于给定的无向图—树是边数最小的连通图〔mn-1那么不连通〕

树是边数最多的无回路图〔mn-1那么有回路〕

结点的度：Σd(vi)=2m=2(n-1)

定理：设T是n阶非平凡的无向树，那么T中至少有片树叶

设：有x片树叶，其余结点度数至少为2

x+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个结点

111115

111124

111133

111223

112222

例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;?;3、生成树的应用

要建6个工厂，修建连接的通路〔见图〕，为使5处都有路相通，至少要建几条路？如何铺设？

由于n=6所以建5条路即可

4、无向图G的生成树确实定：

二种方法：1、破圈法：每次去掉回路中的一条边，

去掉总数为m-n+1条弦

2、避圈法：由一个结点开始选一条边，

逐渐添加与边关联的结点〔只要不构成回路即可〕

直到所有结点被添加，(挑选n-1条边〕;3、带权图的最小生成树

(1)定义5设无向连通带权图G＝V，E，W，T是G的一棵生成树．

T的各边权之和称为T的权，记作W(T)；

G的所有生成树中权最小的生成树称为G的最小生成树。

(2)最小生成树的求法〔这里介绍避圈法Kruskal算法)

设n阶无向连通带权圈G＝V，E,W有m条边，

不妨设G中没有环(否那么，可以将所有的环先删去)，将m条边按权从小到大顺序排列，设为e1,e2，…,em；

取e1在T中，然后依次检查e2，e3，