文档介绍：第九章树
无向树
根树及其应用
第1节无向树
1. 无向树连通且无回路的无向图称为无向树,简称为树,用T表示。T中度数为1的点称为叶子,度数大于1的结点称为分支点
森林非连通图,且每个连通分支是树的无向图称为森林。
叶子
分支点
平凡图称为平凡树
2 树的等价定义
给定图T=<V,E>,以下关于树的命题是等价的。
2) T无回路且m=n-1,其中|V|=n,|E|=m 。
3) T连通且m=n-1
4) T无回路,但增加一边后得到且仅得一个回路。
5) T连通,但删去任一边后就不连通。
6) 每一对结点间有且仅有一条通路。
1) T是连通且无回路(即T是树)。
3 无向树的性质及例题计算
性质:任何非平凡树至少有2片树叶。
例1 设树T有20个顶点,其中有8片树叶,其它点的度数均≤3,问:2度点和3度点各几个?
解:设2度点为t个,则3度点为20-8-t。
因2m=∑deg(vi)而m=n-1
∴2×(20-1)=1×8+2t+3(20-8-t)
解得
t=6(个)
所以,3度点共有20-8-6=6(个)
v1
v5
v4
v2
v3
4 生成树的定义
生成树若无向连通图G的生成子图是一棵树,则称这棵树为G的生成树;设G的一棵生成树为T,则T中的边称为树枝,在G中而不在T中的边称弦,所有弦的集合称为生成树T的余树。
v1
v5
v4
v2
v3
树枝
弦
5 生成树存在定理及其推论
生成树存在定理任何无向连通图G至少有一棵生成树。
推论:
1、设n阶无向简单连通图G中有m条边,则m≥n-1.
2、设n阶无向连通图G中有m条边,T是G的一颗生成树,T´是T的余树,则T´有m-n+1条弦。
6 基本回路与基本割集
1) 基本回路(Cr)
一条弦+其余都是树枝
基本回路系统
{基本回路}
2) 基本割集(Sr)
一条树枝+其余都是弦
基本割集系统
{基本割集}
思考:无向连通图G(n,m)有多少个基本回路?有多少个基本割集?
7 最小生成树的定义
设G=<V, E, W>是一带权连通图,
最小生成树在权图G所有生成树中,带权最小的那棵树
a
b
f
d
e
c
2
2
4
2
5
6
3
4
5
带权图
G的生成树T的权w(T)就是T的边上的权和.
8 求无向图的最小生成树的方法
Kruskal算法(避圈法)
,记作e1,置i=1
=n-1时结束,否则转3。
,e2,……eI,此时无回路。
在G中除这i条边外,选择边ei+1,该边使得{e1,…,ei+1}生成的子图中无回路,并ei+1是满足该条件中权最小的一条边。
:=i+1,转2
根树及其应用
1 有向树一个有向图,如果略去边的方向得到的无向图是一棵树,则称该图为有向树。
2 根树一棵非平凡的有向树,如果恰有一个点的入度为0,其余点的入度均为1
树根入度为零的点
树叶出度为0的点称为树叶;
内点出度不为零的点
分支点内点和树根