该问题归结于在图中求所谓的最小生成树问题。或 称为赋权图中的最小连接问题。 例4化学中的分子结构与树 例如：CH0的两种同分异构结构图模型为 8
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 该问题归结于在图中求所谓的最小生成树问题。或 称为赋权图中的最小连接问题。 例4 化学中的分子结构与树 例如：C4H10的两种同分异构结构图模型为： h hh h hhh h h h h hhh h h h h h h
例5电网络中独立回路与图的生成树 早在19世纪，图论还没有引起人们关注的时候，物理学 家克希荷夫就已经注意到电路中的独立回路与该电路中的所 谓生成树的关系。即：如果电路是(m,)图，则独立回路的 个数为m-+1.并且，生成树添上生成树外的G的一条边，就 可以得到一独立回路。 总之，树在图论研究和图论应用上都是十分典型的特殊图
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 例5 电网络中独立回路与图的生成树 早在19世纪，图论还没有引起人们关注的时候，物理学 家克希荷夫就已经注意到电路中的独立回路与该电路中的所 谓生成树的关系。即：如果电路是(n, m)图，则独立回路的 个数为m-n+1.并且，生成树添上生成树外的G的一条边，就 可以得到一独立回路。 总之，树在图论研究和图论应用上都是十分典型的特殊图
(二)、树的性质 定理1每棵非平凡树至少有两片树叶。 证明设P-yY2v是非平凡树T中一条最长路，则y1 与v在T中的邻接点只能有一个，否则，要么推出P 不是最长路，要么推出T中存在圈，这都是矛盾！ 即说明v,与v是树叶。 定理2图G是树当且仅当G中任意两点都被唯一的路 连接。 证明：“必要性” 若不然，设P与P,是连接u与v的两条不同的路。则 10
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 10 定理1 每棵非平凡树至少有两片树叶。 证明 设P=v1v2…vk是非平凡树T中一条最长路，则v1 与vk在T中的邻接点只能有一个，否则，要么推出P 不是最长路，要么推出T中存在圈，这都是矛盾！ 即说明v1与v2是树叶。 定理2 图G是树当且仅当G中任意两点都被唯一的路 连接。 证明：“必要性” 若不然，设P1与P2是连接u与v的两条不同的路。则 (二)、树的性质