给定一个简单无向图G=（V,E）,图划分问题的目标是找到一种满足特定要求的顶点划分方式。顶点平分问题是图划分问题的一个重要变种问题,即平分顶点集合V为两个集合B和B’,其目的是最小化B中顶点v的个数,其中v与B’中至少一个顶点u有边相连。顶点平分问题通常情况下是NP难的,但在某些特殊的图结构如超立方体和森林等存在多项式时间的求解算法。顶点平分问题有着广泛的实际应用,如超大规模集成电路设计、网络通信、图像处理以及多处理器系统中的任务调度等。因此,顶点平分问题的研究有着重要的理论价值和现实意义。本文提出了一种基于聚类的混合迭代搜索算法求解顶点平分问题。首先,提出了一种针对顶点平分问题的相似度度量策略,并结合生成的相似度矩阵使用基于层次的聚类方法对图进行预处理,从而生成一个较优的初始解。第二,提出了一种受聚类约束的移动操作来进行局部搜索。在该操作过程中,某些簇中的顶点始终聚合不会进行移动。最后,提出了一种基于聚类的扰动程序,在扰动过程中通过改变簇的状态来进行多样化搜索使其跳出局部优。本文对所提出的混合迭代搜索算法进行实验测试,并将实验结果与目前最好的算法结果进行比较。实验对比结果表明,结合聚类的搜索算法能够更有效地求解顶点平分问题,并且在大规模的算例上,聚类有利于提高算法的搜索效率。