图划分问题是图论和网络优化领域最基本的问题之一。本论文主要研究顶点赋权图中的连通子图划分问题(简称为k-GP):给定一个简单顶点赋权无向连通图G=(V,E)和一个整数k≥2,将顶点集V划分成k个非空子集,使得每个顶点子集的导出子图是连通的,优化目标是极小化权重最大子集,即极小化顶点权重总和最大的子集。本文主要内容是设计了求解该问题的多项式时间近似算法,并从理论上证明了算法最坏情况界。全文分为五章来阐述。第一章首先介绍了组合优化问题和计算复杂性理论,描述了近似算法以及最坏情况界等基本概念。接着介绍了图论的基本知识,同时还介绍了与本文所研究问题密切相关的边赋权图中的连通子图划分问题,并指出了该问题与本文所研究的顶点赋权图中的连通子图划分问题之间的区别与联系。最后,综述了连通子图划分问题的国内外研究现状。第二章研究了 2-GP问题,即将顶点赋权无向连通图的顶点集V划分成2个非空子集,每个子集Vi(1≤i≤2)的导出子图G(Vi)是连通的,目标使顶点权重较大子集的总权重尽可能小。对于该问题设计了一个最坏情况界为4/3的多项式时间近似算法,并提供实例以说明该界是紧的。第三章研究了 3-GP问题,即将顶点赋权无向连通图的顶点集V划分成3个非空子集,每个子集Vi(1≤i≤3)的导出子图G(Vi)是连通的,目标使顶点权重较大子集的总权重尽可能小。对于该问题设计了一个最坏情况界为3/2的多项式时间近似算法,并提供实例以说明该界是紧的。特别地,该问题的算法最坏情况界理论证明更为复杂。第四章研究了一般情况的k-GP问题,即将顶点赋权的无向连通图的顶点集V划分成k个非空子集,每个子集Vi(1≤i≤k)的导出子图G(Vi)是连通的,目标使顶点权重较大子集的总权重尽可能小。基于3-GP问题的算法设计与分析,我们对于该问题设计了一个最坏情况界为k/2的多项式时间近似算法。第五章,对文章进行了总结,并给出了后续研究方向。