在当前的算法框架下,图上的NP难问题不大可能存在多项式时间的精确算法(除非P=NP)。关于NP难问题的研究主要集中在参数算法、近似算法、启发式算法和精确算法等多方面。核心化算法作为参数算法理论的重要组成部分,不仅可用于设计更好的参数算法,同时由于其本身的特性,也常常作为NP难问题常用的预处理手段。核心化算法的主要思想是,对于参数化问题Q的输入大小为n的一个实例(G,k)进行快速预处理,或者将该问题解决,或者输出一个等价的实例(G’,k’)。算法同时保证G’的大小不超过由k确定的一个界g(k),而与输入大小n无关。g(k)便称为该问题的问题核。由于大多数问题在实际应用中都存在一个小参数k,因此在实际问题中问题核通常不会很大,此时即便运用暴力算法也可快速将原问题解决。核心化的特点,在于它不仅在实际中运用效果良好,而且存在严格的理论支撑,它保证了得到的解是原问题的精确解。也正因为此,核心化算法用于近似算法、启发式算法和精确算法时的预处理手段也取得了很好的效果。对于某些问题,核心化算法甚至能够直接得到最优的精确解。同时,一个问题存在问题核当且仅当它是固定参数可解的。因此核心化算法也常常做为其他参数算法的设计基础。本文从当前的核心化技术入手,结合了核心化技术中“皇冠分解”和“区域分解”的思想并将其扩展延伸。针对图上的参数化几乎导出匹配问题及3-路径覆盖问题,分别提出核心化算法,通过点集划分和局部规则调整,寻找到图的一种特定划分,对于每一部分的大小分别进行分析。如果该部分包含顶点超过某个界,我们或者可以将该问题解决,或者可以确定该问题实例满足一定性质。本文分别对两个问题定义了一种“类皇冠结构”,在上述性质下可快速找到该结构,并利用该结构对问题进行约简。因此,当实例中不存在该类结构时我们得到了问题的问题核。本文的算法改进了之前的最好结果,针对参数化的几乎导出匹配问题和3-路径覆盖问题分别得到大小为8k和5k的问题核。此外,本文针对某一类具有小距离属性的NP难图问题,提出了一种一般性的核心化算法框架。上述两个问题作为该框架的应用实例,取得了很好的效果。同时,利用该框架可以为一类问题设计更好的核心化算法,给其他问题的改进奠定了基础。