最小k度限制树问题是网络优化中一个常见的问题，而一维装箱问题在组合最优化领域处于重要地位。结合这两个问题，本文研究了一个新的最优化问题:给定一个简单的连通无向网络G=（V,E;w;k;v0）及常数L,其中k为给定的正整数，v0∈V是网络中指定的一个顶点，w:E→R+为边的长度函数，这里w(e)允许大于L。我们用长度为“L”的材料构建k度限制树T，且T上的每条边至多能用一次料头（指材料构建完某条边后剩下的部分）。目标是使所用材料的根数m0尽可能小。与装箱问题一样，新问题也是NP-难的。本论文对所提问题设计了一个2-近似算法，接着将2-近似算法改进到7/4-渐进近似。以上算法均给出了相应的程序。　　 论文由以下五章组成:　　 在第一章中，阐述新问题的现实背景，追溯相关理论研究现状，简要说明本文主要研究结果。　　 在第二章中，介绍本文涉及到的定义和符号。　　 在第三章中，给出最小生成树、最小k度限制树及装箱问题相应算法和性质。　　 在第四章中，讨论网络中k度限制树的构建问题及算法。　　 在第五章中，给出相关结论以及未来研究方向。