树：连通且不含圈的无向图称为树。常用T表示。树中的边称为树枝，树中度为1的顶点称为树叶。
生成树：若T是包含图G的全部顶点的子图，它又是树，则称T是G的生成树。
最小生成树：设T=(V,E1)是赋权图G=(V,E)的一棵生成树，称T中全部边上的权数之和为生成树的权，记为w(T)，即w(T)=Σw(e)。如果生成树T*的权w(T*)是G的所有生成树的权最小者，则称T*是G的最优树，即w(T*)=Σmin{w(T)}.
在许多实际问题中，如在许多城市间建立公路网、输电网或通信网，都可以归结为赋权图的最优树问题。
图论中最有树的求解方法通常有两种算法：
Krukal算法和Prim算法
这里利用LINGO求解最优树。
问题1 有10个城镇，城镇1处有一条河流，现需要从各城镇之间铺设管道，使城镇1处的水可以输送到个城镇，求铺设管道最少的设计方式。
!最优树的LINGO程序; model: sets: point/1..10/:u; link(point,point):d,x; endsets data: !各城镇之间的距离; d=0,8,5,9,12,14,12,16,17,22, 8,0,9,15,16,8,11,18,14,22, 5,9,0,7,9,11,7,12,12,17, 9,15,7,0,3,17,10,7,15,15, 12,16,9,3,0,8,10,6,15,15, 14,8,11,17,8,0,9,14,8,16, 12,11,7,10,10,9,0,8,6,11, 16,18,12,7,6,14,8,0,11,11, 17,14,12,25,15,8,6,11,0,10, 22,22,17,15,15,16,11,11,10,0; @text()=@writefor(link(i,j)|x(i,j)#GT#0:‘x(‘,i,‘,‘,j,‘)=‘,x(i,j),‘‘); enddata min=@sum(link(i,j)|i#ne#j:d(i,j)*x(i,j)); n=@size(point); @sum(point(j)|j#gt#1:x(1,j))>=1; @for(point(i)|i#ne#1:@sum(point(j)|j#ne#i:x(j,i))=1); @for(link(i,j):@BIN(x(i,j))); @for(link(i,j)|i#ne#j:u(i)-u(j)+n*x(i,j)<=n-1);!不构成圈; end
结果为：
x(1,2)=1 x(1,3)=1 x(3,4)=1 x(3,7)=1 x(4,5)=1 x(5,6)=1 x(5,8)=1 x(7,9)=1 x(9,10)=1
原文链接:https://www.icourse163.org/
原文：https://www.cnblogs.com/kmxojer/p/12237650.html