的定义与此定义的区别只是指定了一个特殊的 顶点 ——根，并由此使得顶点之间形成了层次 结构，而它同样也是一个无回路的连通图。
03.06.2020
离散数学
1
树的举例
树G：
a
取a为根： 取b为根：b
取e为根：
a
a dc
e
bd
b
e
d
ce
c
d 取d为根：d
b
b
e
e
显然它们是同构的。 a
c
ac
数据结构中的树指定了一个特殊的顶点为根。
03.06.2020
离散数学
2
树的应用举例
树的用途极其广泛，比如计算机网络中的最短
通路、二叉树排序，各种层次结构的表示、等
等。可以说，在计算机领域中几乎处处可以见 到她的婆娑身影。
例如：右图就是用树 表示的算术表达式：
(a+b)* c – d /c
–
*
/
+ c de
ab
03.06.2020
离散数学
G+uv中恰有一条回路；
(4) (5)
06.2020
离散数学
5
树是点比边多一的连通图
证明：因G是树，所以G连通， 下对p做归纳证 明 q=p–1：
(1) p=1时，显然q=p–1 ；
(2)假设对顶点数少于p的树，结论成立；
(3) 对于p个顶点的树G ，p2 , 取e=uv ∈E(G) , 由 定理6.1.1知，e是唯一的(u,v)––通路，于是， G–e不连通而且恰有两个连通分支G1(p1,q1)和 G2(p2，q2),显然，p1<p且p2<p .由归纳假设， q1=p1–1 , q2=p2–1 ,
03.06.2020
离散数学
15
连通是有生成树的充要条件
定理6.2.1： 图G有生成树当且仅当G是一 个连通图。 证明：若G连通，则存在一个G的连通子 图T满足：T连通且从T中去掉任何一条边 后T不连通，于是由定理6.1.2(5)知，G的 生成子图T是树，故T是G的生成树；
(因为在树中，q = p–1) 此为矛盾，故结论成立。
03.06.2020
离散数学
13
§6.2 生成树
图的生成树
生成树：G是一个图，若G的生成子图T是 树, 则称T为G的生成树。(G的生成树可能 不唯一。) 一个图G的生成树是 ⑴G的生成子图，因此它包含了G的全部 顶点； ⑵无回路的连通图（树）。
§6.1 树的定义
定义6.1.1： 连通无回路的图称为树。
让我们来看一下《数据结构》中的树的定义： 一棵树是一个或多个顶点的有限集合T，使得， ⑴有一个特殊标识的顶点，称为根； ⑵除根以外的其余顶点形成n≥0个划分，T1 ， T2 ，… ，Tn，它们也都是树，称为根的子树。
这里的树的定义更为一般。《数据结构》中树
树中至少有两个悬挂点
定理 6.1.3 任何非平凡树G(p,q)中至少有两个 顶点的度数为1（悬挂点 ）。 证明：(反证) 已知G中每个点的度 dG(v)1 ， 若G中最多只有一个点的度数为1，则G中至少 有p–1个顶点的度数大于或等于2，于是，
2q= d(v) 2(p–1) +1 > 2(p–1) = 2q vV (G)
➢ 此定理的逆不一定成立。
03.06.2020
离散数学
4
几种等价说法
定理 6.1.2 设G(p,q) 是一个图，于是，下列五 种说法相互等价：
G是树；
(1) (2)
G连通且q = p – 1;
(2) (3)
G无回路且q = p – 1;
(3) (4)
G无回路,但对任意的u,v∈V(G),若uv E(G),则
03.06.2020
离散数学
8
树若减条边就会不连通
证明：任取u,v ∈V(G) , 若uv∈E(G) , 则u和v 是连通的；若uv E(G) , 则有(4)知，G+uv有
唯一的回路C。由于G中无回路，所以，u,v必 在回路C上，显然，C – uv是G的连通子图，从 而G中含(u,v)–通路，即uv,故G是连通图。
3
树中只有单通路
定理 6.1.1x 树T中任何y两个P1 顶点之间恰有一条 通路。
u证明: (存在P性xy)因为树是连通图，所以任意v两点
之间有通路。
P2
(唯一性)设u,v∈V(T),若u和v之间有两条不同的 (x存uy,在v)E((xP,通y2)),路-显通P然路1,PHP2x=，yP.于于1∪是是PP2必-xxy+有yx是边y是连xyT通,中x图y的∈，一E从(P条而1)回,H但路中， 与树的定义相矛盾。所以定理得证。
。
03.06.2020
离散数学
10
少条边就不连通的图是树的证明图示
P不含e：
v
C
u
x
e y
P含e：
u
C v
xe y
03.06.2020
P G
离散数学
P G
11
平凡树和森林
只有一个顶点的图（平凡图）称为平凡 树。 具有多个连通分支，且每个连通分支都 是树的图称为森林。
03.06.2020
离散数学
12
03.06.2020
离散数学
7
树若添条边就会有回路
证明：设G有k个连通分支，由于G无回路，所 以G的每个连通分支均是树，于是，
k
k
qi=pi-1(i=1,…,k) ,q =qi = (pi-1)= p – k
i=1 i=1
但已知q = p–1 ,故k=1。即G连通，从而G是树。 对G的任意两个非邻接的顶点u , v，由定理 6.1.1,有唯一的(u,v )––通路，从而G+uv也就有 唯一的一条回路。
从而q=q1+q2+1=p1+p2–1=p–1 。
03.06.2020
离散数学
6
树是点比边多一的无回路图
假设G有回路，则显然可以依次从各回路中去 掉边而保持G的连通性。设从G中去掉了k条边 得到G的一个无回路的连通生成子图T，由定义 知T是G的生成树，且其边数是q–k ,顶点数是p, 由(2)知
q–k = p–1 但已知 q =p–1, 因此必有k =0 .这说明G本身就 无回路。
对任意e∈E(G) , 若G – e仍连通，则说明G中含
有回路，此与(4)矛盾，故G – e不连通。
03.06.2020
离散数学
9
少条边就会不连通的图是树
只须证G中无回路。 若G中含回路C，取e=xy∈E(C) ,则 C – e仍连 通，任取u,v∈V(G) ,因G连通，故G中有(u,v)––通 路P。若P不含e，则u,v在G – e中仍连通；若 P中 含e，则P中的e可以用C – e中的(x,y)––通路代替， 从而u,v在G – e中仍连通。总之，u与v在G – e中 连通，此与(5)矛盾。故G无回路，因此，G是树