王继强

(山东财经大学数学与数量经济学院， 济南 250014)

网络设计问题是离散最优化和计算机设计领域中的一个重要问题，它要求人们从网络图中找出满足某种特征的一个子图来。比如最短路问题、最大流问题、旅行商问题(TSP)、中国邮路问题及本文要研究的最小支撑树问题等都属于这类问题。顾名思义，最小支撑树问题就是要从赋权连通图中找出一个权最小的支撑树。这一问题在理论上有重要应用，如最短路问题、TSP、匹配问题、Steiner树问题等问题的解决；它在现实中也有很多应用，如场站建设、城市规划、超大规模集成电路(very large scale integration, VLSI)设计、交通道路布局、通信网络架设等[1-2]。

就算法复杂度而言，最小支撑树问题并不属于NP-困难问题，即它可以在关于问题输入规模的多项式函数的时间内完成求解。Kruscal算法、Prim算法都是求解最小支撑树问题的经典算法，但它们都是仅仅使用了组合最优化思想直接在图上完成操作的，而未能尽可能地利用问题本身的代数特征，建立数学规划模型，借助现代高性能计算软件(如LINGO、MATLAB、1stOpt等)完成问题的求解过程[3-4]。显然，在大数据时代，经典算法费时费力，给人以笨拙之感；对于图的规模相对较大的情形，“建模+软件”解法更贴近生产生活的实际需求。

1 问题陈述

在图与网络理论中，用点表示对象，边表示对象之间的关系，这样的“点-边”二元结构就是图。如有需要，可给图的边赋予一个数字作为权，是为赋权图。根据边有无方向，图可分为无向图和有向图。……