最小生成树模型与实验(共13页).doc

精选优质文档-倾情为你奉上第六章 最小生成树模型与实验树是图论中的一个重要概念，由于树的模型简单而实用，它在企业管理、线路设计等方面都有很重要的应用。6.1树与树的性质上章已讨论了图和树的简单基本性质。为使更清楚明了，现在使用实例来说明。图 6.1 例6.1 已知有五个城市，要在它们之间架设电话线，要求任何两个城市都可以互相通话（允许通过其它城市），并且电话线的根数最少。 用五个点代表五个城市，如果在某两个城市之间架设电话线，则在相应的两个点之间联一条边，这样一个电话线网就可以用一个图来表示。为了任何两个城市都可以通话，这样的图必须是连通的。其次，若图中有圈的话，从圈上任意去掉一条边，余下的图仍是连通的，这样可以省去一根电话线。因而，满足要求的电话线网所对应的图必定是不含圈的连通图。图6.1的表达式满足要求的一个电话线网。定义6.1 一个无圈的连通图称为树.例6.2 某大学的组织机构如下所示:文科办公室 教务处