假设nk时结论成立，往证n=k+1时成 立。
因为T连通，所以(T) 1，由m=n-1及 d(v)=2m得，T中至少存在一点u，使 得d(u)=1。考虑T’=T-u，显然T’连通， 且|E(T’)|=|V(T’)|-1，由归纳假设，T’ 无回路，所以T无回路。
⑹ T无回路且m=n-1. ⑴ T无回路的连通图. ⑹k由⑴⑹2:得假。，设对任T不意连的通T，i，设TiT是1无, T回2,…路,的T连k为通T图的，连所通以分T支i是，树则，
283 164 75
23 184 765
2 83 14 7 65
283 16 754
23 184
…………………..
765
123 84
765
123 8 4 目标结点
7 65
五.m叉树与完全m叉树
1.m叉树:在根树中,如果每个结点的出度最大是m, 则称
此树是m叉树.
2.完全m叉树:在根树中,如果每个结点的出度都是m或者
7.树高:从树根到各个叶结点的路径中, 最长路径的长度,
称为该树的高度(树高).
三.举例: a)语法树
主语
句子
谓语短语
冠词
形容
词
The little
b)算术表达式树 ((a+b)÷c)×(d－e)
名 词 boy
÷
动词
宾
语 冠词
名
saw
词
The apple ×
－
+
cd
e
a
b
c)判定树:有四枚金币a,b,c,d,已知道三个是真的,最多一 个是假的,它们的外表完全相同,只是重量有点差别.给你 一架天平找出假币.
4.森林:一个无向图的每个连通分支都是树.如(b)
5.与树定义等价的几个命题 定理1给定图T, 以下关于树的定义是等价的. ⑴ T无回路的连通图. ⑵T无环且每对结点之间有一条且仅有一条路. ⑶ T无回路但在任一对不相邻的顶点间添加一条
新边e，则T+e包含唯一的回路. ⑷ T连通的,且每条边都是割边. ⑸ T连通的且m=n-1. ⑹ T无回路且m=n-1. 证明:⑴⑵:已知T是连通无回路图,所以T中无环。
8-9 树与生成树
树是一种特殊的图, 它是图论中重要的概念之一, 它有
着广泛的应用.在计算机科学中有如判定树、语法树、分
类树、搜索树、目录树等等.
一.树 (Tree)
1.树的定义:一个连通无回路的
(a)
无向图T,称之为树. 如(a)
2.叶结点:度数为1的结点, 称为叶结点.
3.分支结点(内结点):度数大于1的结点. (b)
|E(Ti)|=|V(Ti)|-1 故m=i=1k|E(Ti)|=i=1k|V(Ti)|-k
=n-k<n-1 矛盾。
定理2：每一非平凡树至少有两片树叶。 证明：设T是一非平凡树，则m=n-1。 因为T连通且非平凡，所以(T) 1。
设T有k片树叶，则剩余的n-k个顶点的度至少为2。由 d(v)=2m得，k+2(n-k)m=2(n-1), 所以 k 2。
⑷ T连通的,且每条边都是割边.
⑵⑶:显然T无回路，否则对回路上的任一对顶 点都至少存在两条路，与⑵矛盾。设u，v是T 中任意两个不相邻的点，令e=uv，由⑵，T中 有一条唯一的u-v路，所以T+e中包含唯一的回 路。
⑶⑷:因为T无回路，所以T的每条边都是割边； 若 uTV不(T连1)通, v，设V(TT12，),T则2是uTv的两E(个T)分，支显，然设T+uv 不存在回路，与⑶矛盾。
无向图时),是一棵树,则称G是有向树. v4
例如:
v1
v2
v1 v2 v3
v4
v3 v6
v6 v5 v4
v5
二.根树:如果一棵有向树,恰有一个结点的入度为0,其余
所有结点的入度均为1,则称此树为根树.
v1
1.树根:入度为0的结点. 2.叶:出度为0的结点.
v2
3.分支结点(内结点):出度不为0的结点. v4
|E(T1)|=|V(T1)|-1， |E(T2)|=|V(T2)|-1 故m=|E(T1)|+|E(T2)|+1
=|V(T1)|-1+ |V(T2)|-1+1 =n-1。
⑸ T连通的且m=n-1.
⑹ T无回路且m=n-1.
⑸⑹:只需证明T无回路。对T关于顶点 数归纳。
当n=1或n=2时，显然成立。
v3 v6
4.父结点与子结点:如果<vi,vj>是根树中
v5 v7
的一条边,则称vi是vj的父结点, vj是vi的子结点.
5.祖先结点与后裔结点: 在根树中,如果从vi到vj有路,则 称
vi是vj的祖先结点, vj是vi的后裔结点. 6.根树结点的层次:从根结点到某个结点的路径的长度,称
为该结点的层次. 同一层次的结点称为兄弟结点.
定义：[Sk , Sk ] {uv | u Sk，v Sk}。 Step0. 设v为V的任一顶点. 令S0={v}, E0=,
k=0.
Step1. 若Sk=V, 结束. 以Sk为点集, Ek为边集 的图即是G的最优树. 否则转Step2.
Step2. 构造[Sk , Sk ], 若[Sk , Sk ] , 则G不连
七. m叉有序树转化成二叉树 因为二叉树便于存贮, 也便于处理, 所以通常可以将多叉 树化成二叉树.方法是:
1.每个结点保留左儿子结点, 剪掉右边其分支. 被剪掉 的结点如下处理(重新嫁接). 2.同一个层次的结点, 从左到右依次画出(被剪掉的结 点 嫁接到它的哥哥结点上).
r
a
c
eb
h di f g
⑵后序遍历右子树
⑶访问根结点.
后序遍历:32x2－×－x3x＋÷＋
九. 最优树(哈夫曼树 Huffman)
二叉树的一个重要应用就是最优树.
1.带权二叉树的定义:设有一组权值:w1, w2, w3,… , wm, 不仿设w1≤w2≤w3≤…≤wm, 设有一棵二叉树有m片 叶子,分别带有权值w1, w2, w3,… , wm,称此树为带权二 叉树.
通, 停止. 否则, 设
w(ek )
min
w(e)
ek

v
k
v
' k
,
vk Sk.

e[Sk , Sk ]
令 Sk1 Sk {vk' }, Ek1 Ek {ek }.
置k=k+1. 返回Step1.
例：求图G的最小生成树。 v2
1
3
v1
24 4
v4 2
v5
2
4
v3
有三种遍历方式 1.先序遍历 2.中序遍历 3.后序遍历
1.先序遍历 ⑴访问根结点. ⑵先序遍历左子树
+
－
÷
⑶先序遍历右子树
3
x
结果:＋－3×2－x2÷x＋3x
×
+
2.中序遍历 ⑴ 中序遍历左子树
2
－
3 x
⑵访问根结点. ⑶中序遍历右子树
x 2
结果:3－2×x－2＋x÷3＋x
3.后序遍历
⑴后序遍历左子树
表示两个城市间的距离, 从一个城市出发走遍各个城市,
如何选择最优的旅行路线.又如城市间的通信网络问题,如
何布线,使得总的线路长度最短.
例如:右图所示
2.求最小生成树算法 ---Kruskal算法: (贪婪算法)
v1
v2 71
2 3 2
v53 1
8 v8
7
v53
4 24
3 4 6 v4
v7
6
v6
Kruskal算法: 设G是有n个结点,m条边(m≥n-1)的连通 图. S=Φ i=0 j=1
二. 生成树
在图论的应用中,找出一个连通图的所有不同的生成树,以
及找出最小生成树是很有意义的.
1.定义:如果图G的生成子图是树,则称此树为G的生成树.
2.弦:图G中,不在其生成树里的边,称作弦. 所有弦的集合,
称为该生成树的补.
v1
定理2 连通图G中至少有一棵生成树. 证明:如果G中无回路, 则G本身就是树.
破圈法
----Prin算法的对偶方法. 最适合于在图 上作业. 当图比较大时, 还可以几个人同 时在各个局部作业.
Step0. 令G0=G. k=0.
Step1. 若Gk不含圈, 转Step2. 若Gk中
含有圈C.
设ekE(C),
且
w(ek )

max
ew (C)
w(e)
令Gk+1= Gk- ek, 若k=k+1, 返回Step1.
将所有边按照权升序排序: e1, e2, e3,… ,em
S=S∪{ai} j=j+1
|S|=n-1 Y 输出S 停 N
N
取ej使得
ai=ej i=i+1
S∪{ ej}有回路?
|S|=n-1, 说明是树
Y
最后S={a1, a2, a3,… ,an-1}
j=j+1
边按升序排序:边(vi, vj)记成eij 边 e28 e34 e23 e38 e17 e24 e45 e57 e16 权1 1 2 2 2 3 3 3 4
jkl
r
a
c
eb f
hd
i
g jk
l
八.遍历二叉树 在二叉树的一些应用中, 常常要在树中查找具有某些
特征的结点,或者对所有结点逐一进行某种处理, 这就提 出了遍历二叉树问题. 即按照一定规律巡访树中每个结点 一次.
由于二叉树是一个非线性结构, 每个结点都可能在左右 两棵子树上, 为此要寻找一种规律, 以便使二叉树上结点 的信息排成一个线性队列上, 从而便于遍历.