2009-7-26 1
运 筹 学 Operations Research
§ 6.2 树树 (tree),连通的无圈的图,
平凡树（ trivial tree）,.1的树
叶（ leaf）,树的悬挂点（度为 1的顶点）；
分支点（ branch vertex）,.2的顶点度?
2009-7-26 2
运 筹 学 Operations Research
的所有非同构的树：6
2009-7-26 3
运 筹 学 Operations Research
树的应用：
（ 1）概率树（ probability tree）
2009-7-26 4
运 筹 学 Operations Research
（ 2）组织结构
2009-7-26 5
运 筹 学 Operations Research
（ 3）在计算机上,Windows操作系统采用树形结构管理文件与目录系统,
2009-7-26 6
运 筹 学 Operations Research
（ 4）化学物质的结构：同分异构体
2009-7-26 7
运 筹 学 Operations Research
（ 5）家谱（ family tree）：
2009-7-26 8
运 筹 学 Operations Research
Lemma 1 任一非平凡树均至少有两个叶,
证：
▌
注：非平凡树的最长路的起点和终点必为悬挂点,
2009-7-26 9
运 筹 学 Operations Research
.)6(
)5(
)4(
1)3(
1)2(
)1(1
圈间添加一条边即得一个无圈，且在任两顶点之后即不连通连通，且去掉任一条边一一条路相连的任两顶点之间恰有唯连通，且无圈，且是树
T
T
T
T
T
TTh
注：树是极小连通图，极大无圈图,
▌
2009-7-26 10
运 筹 学 Operations Research
例 1 一个树中度为 2,3,4的顶点的个数分别为 2,1，
3，其余顶点为叶，求叶的个数,
9)1312(23413221
.312
xxx
xx 由图论第一定理有，，则解：设叶的个数为?
例 2 一个树有 20个顶点，其中有 8个叶，其余顶点的度均不大于 3，求 2,3度顶点的个数,
解,6,6.▌
▌
支撑树（ spanning tree）,本身是树的支撑子图,
2009-7-26 11
运 筹 学 Operations Research
注：图的支撑树是其极小连通支撑子图，其极大无圈支撑子图,
到其支撑树？中去掉多少条边才能得在完全图例?K3
)1()()( 2CTK n解,▌
.2 连通有支撑树图 GGTh?
.
.
保持连通性，破圈子图支撑树是极小连通支撑证：
▌
.1
.2h)(
.14
，矛盾故含有支撑树知，连通，则由假设反证法证：
不连通，则图求证：若例
GTG
G
▌
2009-7-26 12
运 筹 学 Operations Research
支撑树问题：
算法 1：破圈法在保持连通性的前提下，逐次破开所有圈（去掉圈的任一条边即可），直到无圈时为止,
算法 2：避圈法在保持无圈性的前提下，从某一顶点开始，逐次生长边，
直到连通（所有顶点都被生长到）时为止,
2009-7-26 13
运 筹 学 Operations Research
例 5 求图的支撑树：
解：（ 1）破圈法：
2009-7-26 14
运 筹 学 Operations Research
（ 2）避圈法：
▌
城市输电线路的架设问题：
今欲将 n个城市用电缆连结起来建立一个输电网络．问应如何架设输电线路，才能把 n个城市都连结起来，且造价最省（即所用的电缆的总长度最短）？
2009-7-26 15
运 筹 学 Operations Research
最小树问题最小树（最小权支撑树,MST,minimum weight spanning
tree）,图的权最小的支撑树,
最小树算法：
1,破圈法：在保持连通性的前提下,逐次去掉 图的 所有圈中的权最大的边,直到无圈时为止,
2,避圈法,在保持无圈性的前提下,从 图的 某一顶点开始,
逐次生长权最小的边,直到连通 （ 所有顶点都被生长到 ）
时为止,
！,贪心,算法,
2009-7-26 16
运 筹 学 Operations Research
例 6 图的最小树：
解：（ 1）破圈法：
2009-7-26 17
运 筹 学 Operations Research
（ 2）避圈法：
▌
森林（ forest）,无圈的图．
2009-7-26 18
运 筹 学 Operations Research
).1()2(
.)1(
是森林，则若都是树森林的每一个连通分支性质
F
，则的各连通分支分别为设证,?TTTF,,,)2( 21?
)()(]1)([)()(
111
FTTTF
i
i
i
i
i
i
▌
2009-7-26 19
运 筹 学 Operations Research
§ 6.2 over
运 筹 学 Operations Research
§ 6.2 树树 (tree),连通的无圈的图,
平凡树（ trivial tree）,.1的树
叶（ leaf）,树的悬挂点（度为 1的顶点）；
分支点（ branch vertex）,.2的顶点度?
2009-7-26 2
运 筹 学 Operations Research
的所有非同构的树：6
2009-7-26 3
运 筹 学 Operations Research
树的应用：
（ 1）概率树（ probability tree）
2009-7-26 4
运 筹 学 Operations Research
（ 2）组织结构
2009-7-26 5
运 筹 学 Operations Research
（ 3）在计算机上,Windows操作系统采用树形结构管理文件与目录系统,
2009-7-26 6
运 筹 学 Operations Research
（ 4）化学物质的结构：同分异构体
2009-7-26 7
运 筹 学 Operations Research
（ 5）家谱（ family tree）：
2009-7-26 8
运 筹 学 Operations Research
Lemma 1 任一非平凡树均至少有两个叶,
证：
▌
注：非平凡树的最长路的起点和终点必为悬挂点,
2009-7-26 9
运 筹 学 Operations Research
.)6(
)5(
)4(
1)3(
1)2(
)1(1
圈间添加一条边即得一个无圈，且在任两顶点之后即不连通连通，且去掉任一条边一一条路相连的任两顶点之间恰有唯连通，且无圈，且是树
T
T
T
T
T
TTh
注：树是极小连通图，极大无圈图,
▌
2009-7-26 10
运 筹 学 Operations Research
例 1 一个树中度为 2,3,4的顶点的个数分别为 2,1，
3，其余顶点为叶，求叶的个数,
9)1312(23413221
.312
xxx
xx 由图论第一定理有，，则解：设叶的个数为?
例 2 一个树有 20个顶点，其中有 8个叶，其余顶点的度均不大于 3，求 2,3度顶点的个数,
解,6,6.▌
▌
支撑树（ spanning tree）,本身是树的支撑子图,
2009-7-26 11
运 筹 学 Operations Research
注：图的支撑树是其极小连通支撑子图，其极大无圈支撑子图,
到其支撑树？中去掉多少条边才能得在完全图例?K3
)1()()( 2CTK n解,▌
.2 连通有支撑树图 GGTh?
.
.
保持连通性，破圈子图支撑树是极小连通支撑证：
▌
.1
.2h)(
.14
，矛盾故含有支撑树知，连通，则由假设反证法证：
不连通，则图求证：若例
GTG
G
▌
2009-7-26 12
运 筹 学 Operations Research
支撑树问题：
算法 1：破圈法在保持连通性的前提下，逐次破开所有圈（去掉圈的任一条边即可），直到无圈时为止,
算法 2：避圈法在保持无圈性的前提下，从某一顶点开始，逐次生长边，
直到连通（所有顶点都被生长到）时为止,
2009-7-26 13
运 筹 学 Operations Research
例 5 求图的支撑树：
解：（ 1）破圈法：
2009-7-26 14
运 筹 学 Operations Research
（ 2）避圈法：
▌
城市输电线路的架设问题：
今欲将 n个城市用电缆连结起来建立一个输电网络．问应如何架设输电线路，才能把 n个城市都连结起来，且造价最省（即所用的电缆的总长度最短）？
2009-7-26 15
运 筹 学 Operations Research
最小树问题最小树（最小权支撑树,MST,minimum weight spanning
tree）,图的权最小的支撑树,
最小树算法：
1,破圈法：在保持连通性的前提下,逐次去掉 图的 所有圈中的权最大的边,直到无圈时为止,
2,避圈法,在保持无圈性的前提下,从 图的 某一顶点开始,
逐次生长权最小的边,直到连通 （ 所有顶点都被生长到 ）
时为止,
！,贪心,算法,
2009-7-26 16
运 筹 学 Operations Research
例 6 图的最小树：
解：（ 1）破圈法：
2009-7-26 17
运 筹 学 Operations Research
（ 2）避圈法：
▌
森林（ forest）,无圈的图．
2009-7-26 18
运 筹 学 Operations Research
).1()2(
.)1(
是森林，则若都是树森林的每一个连通分支性质
F
，则的各连通分支分别为设证,?TTTF,,,)2( 21?
)()(]1)([)()(
111
FTTTF
i
i
i
i
i
i
▌
2009-7-26 19
运 筹 学 Operations Research
§ 6.2 over
