网络构建问题是组合最优化中的经典问题，而连通性则是网络设计问题中的一个核心问题。在这篇文章里，我们考虑了一个最优化问题：给定无向图G=(V,E；ω)，ω：E→Q+是权重函数，G＇=(V,E＇)为G的一个子图，要寻找E的一个子集E＂CE，使得由E＇∪ E＂所得的诱导子图是一个连通图，其目标是使得所有方案中权度最大者的权度值达到最小，其中此处定义某个点υ的权度ωd(υ)为E″中跟这个点相关联的所有边的权重之和。该问题是NP-难的。在本文中，对问题的特殊情况E＇=(?)，我们设计了两个时间复杂度分别为O(n2)和O(mn)的启发式算法，而E＇≠(?)的情况也可以类似讨论。　　 论文由以下部分构成：　　 第一章：介绍问题的由来，实际意义，给出了到目前为止的一些研究成果；　　 第二章：给出文中所出现的一些定义，概念和符号；　　 第三章：给出了最小权度的网络构建相关的算法，并利用设计的程序对具体实例进行验证；　　 结束语：给出相关结论以及未来的研究方向；　　 附录：给出了最小权度的网络构建相关的算法的程序。