图论——树

定义
设G是连通图，T, T’是G 的两个生成树， 如E(T) 与E(T’)不同， 我们说这是两个不同的生成树。 记G的生成树的个数为
2.3 求生成树的方法
广度优先搜索
深度优先搜索
2.4 最小生成树
定义2.5 设T是无向连通带权图G＝<V,E,W>的一棵生成树， T的各边权之和称为T的权，记作W(T)。
例： 设T1和T2都是树T的子树， T3是T1与T2的公共边端点形成 的顶点子集的导出子图， 则T3也是树。
说明：由于T是树，T3是T的子图， T3一定不含圈，只需证明T3 连通。
证明： 如T3是空图， 得证。否则，
T3一定不含圈， 我们只需要证明T3连通。 在V(T3)中任取两个 顶点 u, v， 则u, v属于T1也属于T2.又由于T1和T2都是树， 则 在T1和T2分别存在唯一的路P1(u, v)和P2(u, v). 又因为 P1(u,v)和P2(u,v)是T上的路， 而T又是树， 所有 P1(u,v)=P2(u,v), 即P1(u,v)上的边也在T2上。 从而P1(u,v)是 T3上子图， 即， u,v在T3上连通。由于u, v的任意性知T3连通 。证毕。
V1,v2,..vt为叶，(1)若vi，vj为兄弟，则li=lj.
(2)设T+是带权w1+w2, w3, …, wt Huffman树, 将w1+w2 相应的叶子生出两个新叶分别带权w1，w2 则得到带 权w1，w2, w3, …, wt Huffman树
求最优树的算法去掉， 在剩下的 图中再找圈， 再破。。。直到不存在圈。
“生长法“
设S记录子树
初始化， S包含取定的任意一个点
从S到V-S中的边中选取权最小的一条边另外一个顶 点加入到S中
直到所有的点都被包含在S中
例2.3
例2.3 求下图所示两个图中的最小生成树。
W(T1)＝6
W(T2)＝12
例题
例如 求所示图的一棵最小生成树。
解答
最小生成树 W(T)=38
小节结束
2.6 根树及其应用
设D是有向图，若D的基图是无向树，则称D为有向树。 在所有的有向树中，根树最重要，所以我们只讨论根树。
二叉树的应用
根树的定义
定义2.6 T是n(n≥2)阶有向树， (1) T为根树— T中有一个顶点入度为0，其余顶点的入度均为1
根树的分类
(1)设T为根树，若将T中层数相同的顶点都标定次序， 则称T为有序树。
(2)分类：根据根树T中每个分支点儿子数以及是否有序
r叉树——每个分支点至多有r个儿子 r叉有序树——r叉树是有序的 r叉正则树——每个分支点恰有r个儿子 r叉正则有序树——r叉正则树是有序的
r叉完全正则树——树叶层数均为树高的r叉正则树
则Г∪(u,v)（(u,v)为加的新边）为G中的圈，
显然圈是唯一的。
(6)(1)
如果G中没有圈，但在任何两个不同的顶点之间加一条新边，在 所得图中得到唯一的一个含新边的圈，则G是树。
只需证明G是连通的。 u,v∈V，且u≠v，则新边(u,v)∪G产生唯一的圈C， 显然有C -(u,v)为G中u到v的通路，故u～v， 由u,v的任意性可知，G是连通的。
(3)(4)
如果G中无回路且m＝n-1，则G是连通的且m＝n -1。
只需证明G是连通的。（采用反证法）
假设G是不连通的，由s(s≥2)个连通分支G1,G2,…,Gs组成 ，并且Gi中均无回路，因而Gi全为树。
由(1)(2)(3)可知，mi＝ni-1。于是，
m mi (ni 1) ni s n s
分支点——度数大于或等于2的顶点。 举例 如图为九个顶点的树。
无向树的等价定义
定理 2.1 设 G＝<V,E> 是 n 阶 m 条边的简单无向图，则下面各命题 是等价的：
（1）G是树。
（2）G中任意两个顶点之间存在唯一的路径。 （3）G中无回路且m＝n1。 （4）G是连通的且m＝n1。 （5）G是连通的且G中任何边均为桥。
说明
注意：T 不一定连通，也不一定不含回路。
生成树的存在条件
定理2.3 无向图G具有生成树当且仅当G连通。 证明 必要性，显然。 充分性（破圈法）。 若G中无回路，G为自己的生成树。
若G中含圈，任取一圈，随意地删除圈上的一条边，
若再有圈再删除圈上的一条边，直到最后无圈为止。 易知所得图无圈(当然无回路)、连通且为G的生成子图， 所以为G的生成树。
(2)(3)
如果G中任意两个顶点之间存在唯一的路径， 则G中无回路且m＝n-1。 其次证明 m＝n-1。（归纳法） n＝1时，G为平凡图，结论显然成立。 设n≤k(k≥1)时结论成立， 当n=k+1时，设e＝(u,v)为G中的一条边， 由于G中无回路，所以G-e为两个连通分支G1、G2。 设ni、mi分别为Gi中的顶点数和边数，则ni≤k ，i＝1,2， 由归纳假设可知mi＝ni-1，于是 m＝m1+m2+1＝n1-1+n2-1+1＝n1+n2-1＝n-1。
举例
下图所示的三棵2叉树T1,T2,T3都是带权为2、2、3、3、5的2叉树 。
W(T1)=2×2+2×2+3×3+5×3+3×2=38 W(T2)=3×4+5×4+3×3+2×2+2×1=47 W(T3)=3×3+3×3+5×2+2×2+2×2=36
定理2.5
设T是Huffman树， w1≤w2 ≤ … ≤ wt
例2.1
人们常称只有一个分支点，且分支点的度数为n-1的 n(n≥3)阶无向树为星形图，称唯一的分支点为星心。
2.2 生成树
定义2.2 设G为无向图， （1）T为G的树—T是G的子图并且是树。 （2）T为G的生成树—T是G的生成子图并且是树。 （3）e为T的树枝—设T是G的生成树，e∈E(G)，若e∈E(T)。 （4）e为T的弦—设T是G的生成树，e∈E(G)，若eE(T)。 （5）生成树T的余树—导出子图G[E(G)-E(T)] 。记作 T
分支点—— 7个
高度—— 5
家族树
常将根树看成家族树，家族中成员之间的关系如下定义。 定义2.7 设T为一棵非平凡的根树， vi、vj∈V(T)，若vi可达vj，则称vi为vj的祖先，vj为vi的后代。 若vi邻接到 vj（即 <vi,vj>∈E(T)）， 则称vi 为 vj的父亲，而 vj为 vi 的儿子。 若vj、vk的父亲相同，则称vj与vk是兄弟。 定义2.8 设v为根树T中任意一顶点，称v及其后代的导出子图为 以v为根的根子树。
i 1 i 1 i 1
s
s
s
由于s≥2，与m＝n-1矛盾。
(4)(5)
如果G是连通的且m＝n1，则G是连通的且G中任何边均为桥。
只需证明G中每条边均为桥。 e∈E，均有|E(G-e)|＝n-1-1＝n-2，
由（若G是n阶m条边的无向连通图，则m≥n-1）可知，G-e已不是 连通图，
所以，e为桥。
(5)(6)
如果G是连通的且G中任何边均为桥，则G中没有回路，但在任 何两个不同的顶点之间加一条新边，在所得图中得到唯一的 一个含新边的圈。 因为G中每条边均为桥，删掉任何边，将使G变成不连通图， 所以，G中没有回路，也即G中无圈。 又由于G连通，所以G为树，由(1) (2)可知， u,v∈V，且u≠v，则u与v之间存在唯一的路径Г，
给定实数w1, w2, …, wt，且w1≤w2 ≤ … ≤ wt。 ①连接权为w1, w2的两片树叶，得一个分支点，其权为w1+w2。 ② 在w1+w2, w3, …, wt中选出两个最小的权，连接它们对应的顶 点（不一定是树叶），得新分支点及所带的权。
由定理2.1可知，Ti的边数mi＝5，
由握手定理可知，∑dTi(vj)＝10，且δ(Ti)≥1，△(Ti)≤5。 于是Ti的度数列必为以下情况之一。 (1) 1，1，1，1，1，5 (2) 1，1，1，1，2，4 (3) 1，1，1，1，3，3 (4) 1，1，1，2，2，3 (5) 1，1，2，2，2，2 (4)对应两棵非同构的树， 在一棵树中两个2度顶点相邻， 在另一棵树中不相邻， 其他情况均能画出一棵非同构 的树。
（6）G中没有圈，但在任何两个不同的顶点之间加一条新边，在 所得图中得到唯一的一个含新边的圈。
(1)(2)
如果G是树，则G中任意两个顶点之间存在唯一的路径。 存在性。
由G的连通性及定理14.5的推论（在n阶图G中，若从顶点vi到 vj(vivj)存在通路，则vi到vj 一定存在长度小于等于n-1的初级 通路(路径)）可知， u,v∈V，u与v之间存在路径。
G的所有生成树中权最小的生成树称为G的最小生成树。
求最小生成树的算法（避圈法(Kruskal)） (1)设n阶无向连通带权图G＝<V,E,W>有m条边。不妨设G中没有 环（否则，可以将所有的环先删去），将m条边按权从小到大 排序：e1,e2,…,em。 (2)取e1在T中。 (3) 依次检查 e2,…,em ，若 ej ( j≥2) 与已在 T 中的边不构成回路， 取ej也在T中，否则弃去ej。 (4)算法停止时得到的T为G的最小生成树为止。
充分性的另外一种证法：若G是连通图，T是G的边数 最少的连通生成子图，则任取e∈E(T), T-e已不连 通。 由定理可得， T是树。从而知连通图G有生成 树。
例题：连通图G的无圈子图T’是G的某个生成树的子图
注： 等价于要找到一个生成树包含这个无圈子图的 所有边。
证明：不妨设G不是树（如是树，结论已经成立）， 则G中含圈C. 则在C上有一条边e它不在T’上。 则 G1=G-e仍然连通，且T’是G1的无圈子图。G1上的圈数 比G的圈数少。 用G1代替G， 可使G1是圈数减少而保 持连通，但仍以T’为子图。由于G的圈数有限， 最后 得到一个图Gk, Gk无圈连通仍包含无圈子图T’，而Gk 是图G的生成树。于是T’是G是生成树Gk的子图。