带上限的连通图划分问题是组合最优化中图划分问题与调度理论中早期工作最大化问题的结合,在现实生活中有广泛的应用,如货车装载、农作物收割、任务分配等。给定一个赋权连通图G=（V,E,w）和常数B,其中w:→R≥0为顶点的权值函数,B是每个顶点子集的权值上界。带上限的连通二划分问题是将顶点集V划分为两个非空且不交的子集（V1,V2）,使得每个子集诱导的子图是连通的,目标是使得这两个子集的权值之和最大,其中每个子集的权值wB（Vi）为w（Vi）和B的最小值（i=1,2）。在第二章中,首先研究了二连通图上带上限的连通二划分问题,利用st编号的定义对图中的顶点进行重排,设计了一个近似比不超过8/7的近似算法;然后通过连通图的结构性质,构造图的块衔接树,将连通图上带上限的连通二划分问题转化为二连通图上的该问题,设计了一个近似比不超过8/7的近似算法。在第三章中,首先研究了区间图上带上限的连通二划分问题,并基于一个动态规划算法,证明了该问题存在一个全多项式时间近似方案;其次研究了网格图上带上限的连通二划分问题,通过对重顶点集中顶点的个数分类讨论,设计了一个近似比不超过14/13的近似算法。