图划分问题是一类有着广泛用途的问题，它在大规模集成电路设计，计算机信息存储方案中均有应用。本文所讨论图划分问题为最小化k限制连通分支数问题：对于任意连通图G=(V， E)，给定V上的权重函数ω，对任意整数k，将V划分为尽可能少的互不相交的顶点集{V1，V2，…Vj)，使得所有Vi在原图中的诱导子图为连通图，并且权重ω(Vi)≤k。该问题即使对于顶点均为单位权重的简单图仍为NP一完全问题。已知存在多项式时间精确算法，能够解决该问题限制在树上的情形。对于一般连通图上的极小化k限制连通分支数问题还缺乏相应的近似算法。本文先分析了若干启发式算法对该问题的求解质量问题，指出常见的启发式算法仅考虑顶点问的权重关系，而忽略了对图中割点性质的挖掘。本文进而提出了兼顾割点性质与权重的新启发式算法，并给出其对于二种特殊图近似比分别为4与3的证明。