图论是一个应用十分广泛的数学分支,它以图为研究对象.关于图论的研究已经有两百多年的历史,现在在许多方向上都有了很大的发展,其中图的点划分问题是图论研究中的重要问题.图的划分在许多科学与工程领域,如计算机科学、生物科学、VLSI物理设计和图像分割等方面都有广泛的应用.本文旨在研究图的点划分问题.本文将通过四个章节分别讨论了图的公平k-部划分,最大平衡3-部划分和边的大小至多为2的超图的划分.第一章,我们首先介绍图论中的一些基本概念和符号.然后,再介绍一下本文所研究的图的点划分问题的一些基本定义和研究现状.第二章,我们主要讨论了图的公平k-部划分问题.证明了如果图G含有m条边且满足最大k-部划分的割的大小为(k-1)m/k + α,k≥2,则当α≤m/k6时,存在图G顶点集的一个k-部划分V1,...,Vk使得当α>m/k6且m关于k充分大时,存在图G顶点集的一个k-部划分V1,...,Vk使得从而改进了 Bollobas和Scott的结果.第三章,我们考虑图的最大平衡3-部划分.证明了如果图G不含孤立点,且最大度为△,设G有τ个点不交的T分支,则存在图G顶点集的一个平衡3-部划分V1,V2,V3使得其中,由n/3个点不交的K3构成的图G是它的一类极图.从而推广了 Lee,Loh和Sudakov关于平衡二部划分的结果.第四章,我们考虑边的大小至多为2的超图的划分.证明了如果图G是边的大小至多为2的超图,对= 1,2,记mj为图G中边的大小为j的边的数目,则存在图G顶点集的一个k-部划分V1,...,Vk使得从而对Ma et al.的结果中的末项O(m4/5)进行了改进.