图划分的应用背景极其广泛，包括软硬件协同设计、大规模集成电路设计和数据划分等领域。其实，从图划分的众多应用背景来看，图划分问题是某一类问题的集合，即将一个给定的图的顶点集合分割成若干个子集，以满足某些限制，这些子集的并集构成了图中的顶点集。　　相对于非带权图的划分模型，带权图的划分模型因能更好地满足软硬件划分、多处理机系统、社交网络等应用场景的需求而具有重要的实际价值和理论意义。带权图的均衡k划分是把一个图的顶点集分成k个不相交的子集，使得任意两个子集中顶点的权值之和的差异达到极小，并且连接不同子集的边权之和也达到极小。而该划分问题已被证明是NP完全问题，所以通常通过设计一些近似算法来对此类问题进行求解。本文首先针对带权图的均衡k划分问题提出了能够生成优质近似解的启发式算法。所提出的算法在保证子集均衡的条件下，采用了最大化同一子集内部边权之和的策略来构造每一个顶点子集。大量而充分的实验数据表明，和当前国际最新的图划分算法相比，所提算法能产生质量较好的解，特别是平均性能上，解的最大改进幅度可达50％以上。　　针对带权图的划分问题，本文还采用了定制的禁忌搜索算法对生成的启发解实施进一步优化。而且，在算法的设计中提出了一种有效的移动操作以便能找到较好的邻域解，同时引入了扰动机制以增大算法的搜索空间，从而提高了算法全局搜索的能力。实验结果表明，当k=2，4，8时所提算法分别在86％、81％、68％的基准图上求得的平均解优于当前最新算法求得的平均解;解的最大改进幅度可达70％。