树的应用实践

陈杰

摘要：树是图论中一类重要的图。随着时代的发展进步，树的知识内容发展得相对完备，以至于树的知识理论在人类的生活和社会生产实践中得到了广泛的应用。本文主要设计两个最优化的应用实践。

关键词：最小生成树；树形图；最优前缀码

本文主要介绍最小生成树及树形图，以其为基础设计了两个与树相关的实践优化方案案例.

1. 最小生成树的概念

定义1.1[1]设有两图，若且，则称是的子图，为的母图，记作．又若或，则称为的真子图，若，则称为的生成子图．

定义1.2不含回路的连通图称为树．

定义1.3[2]如果是的一个生成子图而且又是一棵树，则称是图的一棵生树．

定义1.4[3] 如果带权的无向连通图，是的一个生成树，的所有边权和称为的权．的一切生成树中，权最小的生成树称为的最小生成树．

1破回路法[3]

在中任取一个回路，删除其中一条边，然后再取一个回路，再删除这个回路中的一条边，如此持续下去，直到得到连通图的无回路的生成子图就是的一个生成树．

2用破回路法求带权的最小生成树的规程

在赋权图中任取一个回路，接着去掉这个回路中权最大的边，按此持续进行直到中不再有回路时为止，这时余下的边组成的子图就是最小树（最优树）．[3]

2．最小生成树应用案例

旅途中路程最短问题 ，对于游客，需要在最短的时间内用最少的钱来旅游最多的景区，故无论采取何种方案，门票的花费都相同且路费在速度一定的情况下可由路程量来求出，因此把问题转换为求旅游路线最短问题．

案例:某湿地公园的路径系统图如图2.1，其中为入口，为出口，，，，，为五个景点，现求如何能使观光车从入口到出口所经过的距离最短．

    

图2.1                                         图2.2

   用破回路法求带权的最小生成树的方法求解，求得旅游线路如图2.2.                                                                                        

由图2.2可知，从入口到出口的最短路径为

最短距离为：2+2+3+1+5=13．

3.树形图

    定义3.1 [4] 如果一个有向树假定恰有一个顶点的入度为0，其余一切顶点的入度为1，则称此有向树的为树形图。入度为0的顶点称为树形图的根。入度为1出度为0的顶点称为树形图的树叶。入度为1，出度非0的顶点称为内点。内点和根统称为分支点.

    在树形图中,  从根 到其它每个顶点 刚好有唯一一条有向路，其长度 称为该点  的层数。层数最大的顶点对应的层数称为树高。

4. 树形图在通信中的应用设计（最优前缀码）

在计算机和通迅中，常用二进制编码来表示符号。如：00,01,10,11可以分别表示A，B，C，D（等长）也可用1,01,001,000分别表示A，B，C，D （非等长），但不能用1,00,000,001分别表示A，B，C，D 。

问题：如何设计字符的二进制编码，使在传输信息时所使用二 进制位最少？------最优前缀码。

前缀码的构造：由一棵二元树能产生一个前缀码。将一个二元树的每一个分支点与它的左儿子之间的边标上0，和它的右儿子之间的边标上1，把从根点到每个叶子所经过的边的标号序列作为叶子的记号，这些叶子的记号的集合就是一个前缀码。

最优前缀码的构造：对26个英文字母，设各字母使用的频率别为: ，求出带权为 的最优二元树T，由T可以构造一个前缀码，这个前缀码就是所要的最优前缀码。

应用案例： 设7个英文字母在通讯中的频率如下：  a：35%   b：20%     c：15%   d：10%      e：10%   f：5%    g：5%，求传输它们的前缀码。要求画出最小树，标示出每个字母相对应的01组合编码。

解答：用Huffman算法构造，根据权为5,5,10,10,15,20,35画出的最优树如图4.1 最优二元树T（可不唯一，但其权不变）。

（2）a,b,…,g相对应的编码分别是： a —— 01, b —— 11, c —— 001, d —— 101, e —— 100, f —— 0001, g —— 0000.

 

                      图4.1 最优二元树T

[1]耿素云、屈婉玲．离散数学[M]．2版．北京：高等教育出版社，2004:274．

[2]王朝瑞．图论[M]．3版．北京：北京理工大学出版社，2002:26．

[3]方冬云．图论在旅游路线选择中的应用[J]．长春工业大学学报（自然科学版），2009,30（5）：583．

[4] 卜月华主编.图论及其应用，东南大学出版社，2018年1月第一版

作者简介：陈杰（1976年2月），男，贵州织金人，贵州大学硕士研究生，贵州大学人民武装学院副教授，主要研究方向：应用数学。