文档介绍：最小生成树问题
例
我国西部的 SV 地区共有 1 个城市（标记为 1）和 9
个乡镇（标记为 2--10）组成，该地区不久将用上天
然气，其中城市 1 含有井源。现要设计一供气系统，
最小生成树问题
例
我国西部的 SV 地区共有 1 个城市（标记为 1）和 9
个乡镇（标记为 2--10）组成，该地区不久将用上天
然气，其中城市 1 含有井源。现要设计一供气系统，
使得从城市 1 到每个乡镇（2--10）都有一条管道相
边， SV
地区的地理位置图，下表给出了城镇之间的距离。

Kruskal 在1956 年给出求最优生成树的一个算法（称
Kruskal 算法）。(1) 选择边e1, 使得边e1 的长度尽可能小;
若已选定边则从余下的边
(2) ee12,, ei ,
中选取使得
Eee\{12 , , ei } ei1,
① 为无圈图
Gee[{12 , , ei 1 }] ;
②边ei1 为满足①的长度尽可能小的边.
(3) 当(2)不能继续执行时, 停止。
最小生成树问题的数学表达式
将最小生成树问题写成数学规划的形式还需要一定
的技巧。我们将上例中的无向赋权图看作是双向赋
权图，设dij 是顶点i到顶点 j之间的距离，由于我们
将无向赋权图看作是双向赋权图，所以ddij ji . 设
xij  0或 1（1 表示顶点i到顶点 j有连接，0 表示不连
接），则数学表达式为:
min  dxij ij ;
(,ij ) E
顶点1至少有一条边连接到其他边
.  x1 j 1,( )
jV
除顶点外，每个点只有一条边进入
 xiji  1, 1,( 1 )
jV
（各边不构成圈）
xij  01或注：第三个约束条件“各边不构成圈”，下面给出一个不构
成圈的充分约束条件：
uuij(1)* n nxij
ui  0

u j  0
(,ij 1,2, , n ;)
LINGO 程序求解
model:
sets:
cities/1..10/:u;
link(cities, cities): d,x;
e