当前位置:课堂首页 >> 课程导航 >> 5.3.3 最小树问题的数学模型[2]
 
 
图不连通。 因此,具有相同顶点的图中,树形图的边数是最少的。这就提示我们,在研究涉及边长之和最短问题时,应该立刻想到树。

           
                                       图 5 — 8
    回到我们的例子。 为解决问题,先建立问题的图论模型。以七个单位为研究对象,其间有直达路线则连一条边,在相应的边旁标以相应的路长,便构成一个网络赋权图模型如图 5 — 9. 可见其中充满了圈,于是从中寻求树(顶点数相同)便成为关键 。
                   
                                         图 5 — 9
先看 四个顶点形成的图 5 - 10 ( a ) . 该图总边长为 19 。

   在保证通气条件下,这个路线的费用最贵。因为如果按照图 5 — 10 ( b )的树形图铺设,保证通气条件下,总费用仅为 14 ( km )的费用。而按树形图 5 — 10 ( C )铺设,则费用只有 8 (km)的费用。换句话讲,在相同顶点情形下,构成的树的总权数大小也有区别。因此自然提出了 最小赋权树 ,简称 最小树 的概念:在具有相同顶点的树中,总赋权数最小的树称为最小树。在本例,我们要寻求的就是上述图模型中的最小树 。
 
本节第 [1] 2 [3] [4] 部分