本文研究的是关键节点问题:在一个无向图中，删除不超过K个节点的集合，使得剩余图在某种意义下尽可能的分裂.文中主要讨论了两种类型的关键节点问题,提出了相应的算法和数值试验.　　第一章介绍了关键节点问题的重要意义和国内外研究概况，并列出了本文研究所需要的预备知识.　　第二章研究了树上带有连通分支点数上界的关键节点问题.首先介绍了树上MaxNum型和MinMaxC型关键点问题的动态规划算法.接着分析了MaxNum型关键点问题刻画不连通性的缺陷，进而提出带有连通分支点数上界的关键点问题.最后设计一种多项式时间动态规划算法，分析其时间复杂度为O（n4），并进行数值试验和几种算法的结果分析.　　第三章提出一个新的比例型连通指数，证明了一般图上比例型连通指数下的关键节点问题是NP-完全的，给出了其整数规划数学模型;其次对于树上比例型连通指数下的关键节点问题，设计了一个多项式时间的动态规划算法，其时间复杂度为O(n4 log n)，并进行了数值试验.　　第四章对相关的研究工作作出总结与展望.