本论文研究了网络中涉及的spider graph问题．Spider graph定义为：T=(V,E)为一棵树，在T中至多有—个顶点的度大于2，则称T为spider graph．论文研究了spider graph问题的两种情形： (1)去点情形的spider graph问题：给定无向图G=(V,E)，寻找VС-V，使得G-V的每个连通分支为spider graph，其目标是使｜V｜达到最小，即min｜V｜． (2)去边情形的spider graph问题；给定无向图G=(V,E)，寻找EС-E，使得G-E的每个连通分支为spider graph，其目标是使｜E｜达到最小，即min｜E｜．在一般图上对上述两个问题分别给出了复杂性为O(n3)的3-近似算法和复杂性为O(n2)的启发式算法．证明了在一般图上问题(2)为NP-完备，并对(2)考虑了当G=(V,E)为一棵树时赋权与不赋权两种情形下复杂性均为O(n)的启发式算法和多项式时间算法．对启发式算法给出了输出值的一个上界． 第一章：介绍问题的提出和到目前为止的一些研究成果及本文的结果． 第二章：预备知识．介绍本论文涉及有关图论、组合最优化、近似算法方面的基本概念、符号和术语． 第三章：讨论了去点情形的spider graph问题，给出相应的算法与复杂性分析． 第四章：讨论了去边情形的spider graph问题，给出相应的算法与复杂性分析． 第五章：结论和展望．