本论文研究的是关键节点问题:在无向图G上,删去一些点的集合,使得导出子图在某种意义下的分散程度尽可能大.本文提出一个新的思路来描述图的分散程度,即综合考虑剩余图的连通指数和剩余图的度的关系,通过优化它们之间的关系来使得剩余图不连通性增加,从而使得图分散的结果更好.第一章介绍了关键节点问题的背景知识以及一些前人提出的描述图的分散程度的函数,并列出了本文研究所需要的一些预备知识.第二章研究了综合考虑剩余图的连通指数和剩余图的度的关系后树上的关键节点问题的动态规划解法.我们分析其时间复杂度为O(n3K2),并进行数值试验和结果分析.第三章我们的目标函数综合考虑了剩余图的连通指数,剩余图的度和,剩余图的最大度这三个因素的关系.在这一章节,我们考虑了删除点的权重wi以及删除的对应的边的权重cij.我们先从树上的问题开始考虑,然后再推广到一般图上.对于树上和一般图上,我们都针对不同的wi和cij考虑了六种情况,包括(0,1),(0,≥ 1),(1,0),(≥1,0),(1,1),(≥ 1,≥ 1),其中两个元素分别表示点权向量w和边权矩阵向量c的取值情况,对于不同的系数组合,我们都提出了对应的寻找关键点的贪婪算法.在不同的情况下,我们都进行了不同的数值实验.第四章对本文的研究工作作出总结与展望.