图分割是图处理领域中一种重要方法,并且可应用到计算机科学的其它分支,例如计算机视觉、数据挖掘等,具有重要的影响。由于大规模图分割在实践中意义重大,其性质和处理方法不同于小规模的图,因此对于大规模图的研究是一项重要工作。为了提高图分割质量,降低运行时间,本文将多层次图分割框架和谱聚类方法的思想结合起来,提出大规模图上新的图分割方法。本文的主要工作包括如下几个方面:(1)边加权图或是点加权图上的图分割已经得到了充分的研究,双重加权图是一种边和点都带权的加权图,在很多问题中有重要的应用,例如路径规化、最优圈问题等,然而尚未得到充分研究。本文提出了加权拉普拉斯方法,较好地解决了双重加权图上的图分割问题。该方法受谱聚类方法的启发,利用图上的加权拉普拉斯来处理最小割问题,其中加权拉普拉斯是图拉普拉斯的推广。借助这一概念,我们将双重加权图上的最小割问题转化为加权拉普拉斯的特征分解问题,并称为加权拉普拉斯方法。通过计算加权拉普拉斯的前k个最小的特征向量,并对这些向量的各个分量逐一进行聚类,最终能产生双重加权图上的k-分割。通过研究加权拉普拉斯的性质,并利用Eluer-Lagrange方程计算最小割的极值,证明了上述方法产生的结果是图分割问题的松弛版本的最优解,因而根据谱聚类的相关工作可知,加权拉普拉斯方法几乎总是给出原问题的最优解。(2)我们证明了平衡最小割问题、双重加权图上的最小割问题和初始聚类问题三者之间的等价性,其中初始聚类问题是多层次图分割产生的中间问题。它们之间的等价性说明了双重加权图上的最小割问题本质上是一个平衡最小割问题,而初始聚类问题可以转化为最小割问题,从而可以使用加权拉普拉斯方法来研究初始聚类问题。我们提出了基于加权拉普拉斯方法的加权谱算法,该方法适用于多层次图分割的初始聚类阶段。我们还进行了实验验证,加权谱算法的产生的分割质量最优,同时该算法在运行时间上也与目前的谱聚类算法相似。(3)另外,针对多层次图分割框架中粗化规则的选择问题,我们证明了在准正则图上,存在多项式间内的最小割问题的近似算法。我们利用了准正则图上的正则性引理,该引理给出了准正则图上存在一个近似于随机图的分割方式。证明过程给出了具体的构造方法,从而说明了在准正则图上最好的粗化规则的形式,后续的实验部分验证了该结果。