加权拉普拉斯方法及其理论应用
【摘要】 受到图拉普拉斯理论的部分启发，本文提出了一种加权拉普拉斯方法来更加方便地研究现阶段比较流行的图问题，例如，多层图分割，以及平衡最小割问题.由于加权拉普拉斯策略继承了谱方法的众多优点，因此相比于其他现有的启发式算法，用加权拉普拉斯设计图算法在算法性能上具有更强的理论保证.为了说明其在理论与实际中的强有力的应用价值，我们将分别给出加权拉普拉斯方法在多层图分割和平衡最小割问题上的应用.借助变分法和偏微分方程（PDE）理论，我们在加权分割问题（weightedcutproblem），平衡最小割问题（balancedminimumcutproblem），以及初始聚类问题（initialclusteringproblem）之间建立了等价性.其中，初始聚类问题会在基于多层结构的图分割算法的中间阶段出现.这些等价性的建立为基于加权拉
