谱划分算法中特征向量选取方法的研究

图的划分是一个NP难问题,目前已经有很多关于这方面的新算法和文献已经发表,其中的差别主要是在特征向量的选择上。本文主要研究谱划分算法中特征向量的选取问题,从而说明对于具有不同规模和结构的图,应该如何有效的选择合适的特征向量进行划分。我们通过两个方法来讨论这个问题:(1)Fiedler特征向量;(2)前个特征向量。最后通过仿真实验来说明使用不同的特征向量选择方法进行划分时的优点和缺点,以及不同方法适用的领域。