但若增加一个周转站（新点P），连接4点的新网络的最短路线为PA十PB+PC。最短新路径之长N比原来只连三点的最短路径O要短。？这样得到的网络不仅比原来节省材料，而耳稳定性也更好。APB
❖ 但若增加一个周转站（新点P），连接4点的新网 络的最短路线为PA＋PB＋PC。最短新路径之长N 比原来只连三点的最短路径O要短。 ❖ 这样得到的网络不仅比原来节省材料，而且稳定性 也更好。 A B C P
斯坦纳（Steiner）最小树是可以在给定的点之外再增加若干个点(称为斯坦纳点)，然后将所有这些点连起来如果不允许增加任何额外的点作为网络的顶点，这种最短网络称为最小生成树在前面的例子中Steiner最小树的长为/3最小生成树的长为2，1968年贝尔实验室波雷克(Pollak)和研究员吉尔伯特(Gilbert)提出如下猜想：平面上任意n点集，斯坦纳最2小树长与最小生成树之长的比值的最小值是
斯坦纳（Steiner）最小树是可以在给定的点之外再增加 若干个点(称为斯坦纳点)，然后将所有这些点连起来。 如果不允许增加任何额外的点作为网络的顶点，这种最 短网络称为最小生成树。 在前面的例子中Steiner最小树的长为 3. 最小生成树的长为2. 1968年贝尔实验室波雷克(Pollak)和研究员吉尔伯特 (Gilbert)提出如下猜想：平面上任意n点集，斯坦纳最 小树长与最小生成树之长的比值的最小值是 . 3 2
1967年前，贝尔公司按照连结各分部的最小生成树的长度来收费。1967年一家航空公司戳了贝尔公司一个大洞。当时这家企业申请要求贝尔公司增加一些服务点，而这些服务点恰恰位于构造该公司各分部的斯坦纳最小树需增加的斯坦纳顶点上。这使得贝尔公司不仅要拉新线，增加服务网点，而耳还要减少收费这一意外事件迫使贝尔公司自此以后便采用了斯坦纳最小树原则
1967年前，贝尔公司按照连结各分部的最小生成树 的长度来收费。1967年一家航空公司戳了贝尔公司一 个大洞。当时这家企业申请要求贝尔公司增加一些服 务点，而这些服务点恰恰位于构造该公司各分部的斯 坦纳最小树需增加的斯坦纳顶点上。这使得贝尔公司 不仅要拉新线，增加服务网点，而且还要减少收费。 这一意外事件迫使贝尔公司自此以后便采用了斯坦纳 最小树原则
三.Kruskal算法2.算法思想(贪算法：总是选择权最小的边
三. Kruskal算法 2. 算法思想(贪婪算法)：总是选择权最小的边
3.算法描述：步骤1：按照权的递增顺序排列图G的边，置集合T为空集步骤2：检查排列序表中第一条未检查的边，此边被放入T中当且仅当它不与T中的边形成回路。若这条边被加入T中，进入步骤3，否则重复步骤2，步骤3：若T有n-1条边，则停止，T即为所找的最小支撑树，否则，进入步骤2
3. 算法描述： 步骤1：按照权的递增顺序排列图G的边，置集合T为空集 . 步骤2：检查排列序表中第一条未检查的边，此边被放入 T中当且仅当它不与T中的边形成回路。若这条边被 加入T中，进入步骤3，否则重复步骤2. 步骤3：若T有n-1条边，则停止，T即为所找的最小支 撑树，否则，进入步骤2