实际上，根树是许多问题的模型，如社会结构， 计算机数据结构，数学中的公式结构，分类枚举表 示等。 例3道路的铺设与树 假设要在某地建造4个工厂，拟修筑道路连接这4处。 经勘探，其道路可按下图的无向边铺设。现在每条边的 长度已经测出并标记在图的对应边上，如果我们要求铺 设的道路总长度最短，这样既能节省费用，又能缩短 工期，如何铺设？
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 实际上，根树是许多问题的模型，如社会结构， 计算机数据结构，数学中的公式结构，分类枚举表 示等。 例3 道路的铺设与树 假设要在某地建造4个工厂，拟修筑道路连接这4处。 经勘探，其道路可按下图的无向边铺设。现在每条边的 长度已经测出并标记在图的对应边上，如果我们要求铺 设的道路总长度最短，这样既能节省费用，又能缩短 工期 ，如何铺设？ v2 v3 v4 e2 e3 e4 v1 e1 e5 e6
该问题归结于在图中求所谓的最小生成树问题。或 称为赋权图中的最小连接问题。 例4化学中的分子结构与树 例如：CH1的两种同分异构结构图模型为： hh h h h h
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 该问题归结于在图中求所谓的最小生成树问题。或 称为赋权图中的最小连接问题。 例4 化学中的分子结构与树 例如：C4H10的两种同分异构结构图模型为： h h h h h h h h h h h h h h h h h h h h
例5电网络中独立回路与图的生成树 早在19世纪，图论还没有引起人们关注的时候，物理学 家克希荷夫就已经注意到电路中的独立回路与该电路中的所 谓生成树的关系。即：如果电路是(m,m)图，则独立回路的 个数为m-n+1.并且，生成树添上生成树外的G的一条边，就 可以得到一独立回路。 例6通信网络中的组播树 在单播模型中，数据包通过网络沿着单一路径从源主机向 目标主机传递，但在组播模型中，组播源向某一组地址传递数 据包，而这一地址却代表一个主机组。为了向所有接收者传 递数据，一般采用组播分布树描述P组播在网络里经过的路 径。组播分布树有四种基本类型：泛洪法、有源树、有核树 和Steiner7树
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 8 例5 电网络中独立回路与图的生成树 早在19世纪，图论还没有引起人们关注的时候，物理学 家克希荷夫就已经注意到电路中的独立回路与该电路中的所 谓生成树的关系。即：如果电路是(n, m)图，则独立回路的 个数为m-n+1.并且，生成树添上生成树外的G的一条边，就 可以得到一独立回路。 例6 通信网络中的组播树 在单播模型中，数据包通过网络沿着单一路径从源主机向 目标主机传递，但在组播模型中，组播源向某一组地址传递数 据包，而这一地址却代表一个主机组。为了向所有接收者传 递数据，一般采用组播分布树描述IP组播在网络里经过的路 径。组播分布树有四种基本类型：泛洪法、有源树、有核树 和Steiner树
总之，树在图论研究和图论应用上都是十分典型 的特殊图。 (二)、树的性质 定理1每棵非平凡树至少有两片树叶。 证明设PVY2Vk是非平凡树T中一条最长路，则v 与V在T中的邻接点只能有一个，否则，要么推出P 不是最长路，要么推出T中存在圈，这都是矛盾！ 即说明v,与y2是树叶。 定理2图G是树当且仅当G中任意两点都被唯一的路 连接。 证明：“必要性” 若不然，设P,与P是连接u与v的两条不同的路。则
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 9 总之，树在图论研究和图论应用上都是十分典型 的特殊图。 定理1 每棵非平凡树至少有两片树叶。 证明 设P=v1v2.vk是非平凡树T中一条最长路，则v1 与vk在T中的邻接点只能有一个，否则，要么推出P 不是最长路，要么推出T中存在圈，这都是矛盾！ 即说明v1与v2是树叶。 定理2 图G是树当且仅当G中任意两点都被唯一的路 连接。 证明：“必要性” 若不然，设P1与P2是连接u与v的两条不同的路。则 (二)、树的性质