图的划分问题是图论研究的热点问题之一,在计算机科学、生物科学、大规模集成电路设计和图像分割等方面都有广泛的应用.图划分问题起源于最大割问题:给定一个图G,寻求图G的顶点集的一个二部划分V(G)= 1 ∪V2,使得e(V1,V2)尽可能大,其中e(V1,V2)表示一个端点在V1中,另一个端点在V2中的边的条数.最大割问题是计算机理论研究的基本问题之一,受到众多研究者的广泛关注.对于有向图D,以及两个不相交的顶点子集X,Y(?)V(D),用e(X,Y)表示由X指向Y的弧的条数.显然,在研究有向图D的一个划分V(D)= V1 ∪V2所对的割边时,我们需要考虑两个量:e(V1,V2),e(V2,V1).因此,有向图最大割问题是比图的最大割问题更复杂的问题,目前已有的研究成果较少.在本文,我们主要讨论图与定向图的最大割问题,论文结构如下:第一章,我们先介绍图论中的一些基本概念和符号.然后,介绍本文所研究的图划分问题的基本定义、最大割问题的历史背景与发展,最后给出论文的主要结果.第二章,我们主要讨论一类特殊图的最大割问题.构造图H:用一个点连接任意多个完全二部图K2,s(s ≥ 2).在本章,我们对不含H作为子图的图的最大割问题进行研究,证明了:若图G有m条边且不含H作为子图,则存在c = c(H)>0,以及G的一个二部划分V(G)= V1 ∪ V2,使得e(V1,V2)≥ m/2+ + cm4/5,并且这个下界是紧的.第三章,我们运用概率方法,主要研究了定向图的最大平衡割问题.对有向图D的一个划分V(D)= V1 ∪ V2,如果||V1|-|V2|| ≤ 1,则称这个划分为二部平衡划分.在本章,我们证明了:设d ≥ 4是正整数,D是有m条边的定向图,如果对任意∈ V(D),满足min{d+(v),d-(v)} ≥ d,则D存在二部平衡划分V(D)= 1 ∪V2,使得min{e(V1,V2),e(V2,V1)} ≥((d-1)/(2(2d-1)))+ o(1))m.最后,我们给出了两个值得进一步研究的问题。