图论起源于18世纪30年代，数学家欧拉在1736年解决哥尼斯堡七桥问题的文章是图论领域的开山之作.图是建立各种数学模型强有力的工具，近年来，图论在解决自然科学、社会科学领域的多个问题方面己经显示出其优越性，得到了广泛的关注.　　图的划分理论是图论的重要组成部分，是当今图论领域的热点和难点问题，在图染色问题、计算机理论、统计物理等研究工作中都有着重要的应用.　　传统的划分问题是寻求顶点集的某种划分从而最优化图中的某个单一变量，如最大割问题;而图的公平划分问题则是要在划分中同时最优化若干个变量.本文旨在研究图与超图的公平划分问题，结合极值理论和概率方法，分析不同划分情形下图与超图的拓扑结构性质，给出了某些划分问题的最优界，部分地解决了Bollobás和Scott关于公平划分的猜想。　　我们分别用G、H来表示图和超图.对于超图H中边e，如果|e|=i，那么称边e为超图的i-边.若超图的所有边满足|e|=r，则称超图H为r-一致超图;若超图边的大小不全相等，则称H为混合超图;若超图的边满足|e|=1或者|e|=2，则称H为1，2-混合超图.　　给定R+表示非负实数集合，G为赋权图是指在图G上定义了赋权函数ω，满足ω:V(G）∪ E(G)→R+;赋权1，2-混合超图H是指在1，2-混合超图H上定义了赋权函数ω，满足ω:E(H）→R+.我们用ω1，ω2分别来表示所有图（超图）中的点（1-边）、边（2-边）的总赋权值，用α表示点(1-边)所赋权中的最大值.对任意顶点υ∈V(G)，定义赋权度ΤωG(υ)为与υ邻接的所有边权值之和，即ΤωG（υ）=∑ω(e)，从而有图的最大赋权度△ω(G)=max{ΤωG(υ):υ∈V}，最{e∈E(G):υ与e邻接}小赋权度δω(G)=min{ΤωG(υ):υ∈V}.　　给定整数κ≥2，图G（超图H）的κ-划分是指存在顶点集合的划分V1，…，Vk，使得V(G)（V（H））=V1∪…∪ Vk，且对于1≤i＜j≤κ，有Vi∩Vj=(0).如果这些划分集合同时满足对于1≤i，j≤κ，有||Vi|-|Vj||≤1，则称这样的一个划分为平衡κ-划分.　　对于图和超图的划分问题，Bollobás和Scott[13]给出了如下猜想.　　猜想1.设H是满足上述条件的边赋权超图，则超图H中存在一个二部划分V（H）=V1∪V2使得每个顶点子集相交边的权值和至少为ω1-α/2+2ω2/3.　　猜想2.给定常数κ≥2，若图G的边数为m≥(k2)，则图中存在一个κ-划分，使得每个划分子集相交边的数目至少为2/2k-1m.　　猜想3.给定整数κ≥2，任意有m条边的图G都存在一个顶点集的κ-划分，使得每个划分子集都与至少(1+o(1))（1-（1-1/k2）m条边相交.　　本文主要围绕以上三个猜想展开，研究几类图与超图的公平划分问题.具体的说，我们主要讨论赋权图的平衡二部划分、1，2-混合超图的平衡二部划分、图的3-划分、稠密图的κ-划分、完全二部图的k-划分.论文分为四部分.　　第一章是绪论.在本章中，我们给出了一个相对完整的简介，首先介绍了图论中的一些基本概念和定义，其次我们给出了图与超图划分问题研究的背景和历史，最后一节列出了论文中的主要结论.　　第二章主要讨论赋权图和1，2-混合超图的划分，首次研究了赋权情况下的平衡二部划分问题.第一小节介绍了在本章证明中用到的符号和术语.接下来的第二小节是本章的重点，我们分别考查了赋权图G、赋权1，2-混合超图H的平衡二部划分问题，证明了在赋权图G中存在平衡二部划分，使得每个顶点子集相交边的权值和至少为ω1-α/2+3ω2-△ω/4.其中△ω表示最大赋权度，极图是奇数个顶点的星图K1.2n，这一结论部分地解决了猜想1.同时，我们还首次给出了1，2-混合超图平衡二部划分的上界，证明了每个顶点至少与5条2-边关联的超图H中存在一个平衡二部划分V（H）=V1∪V2，使得每个顶点子集相交边的数目至少为m1-1/2+2m2/3，其中m1，m2分别表示超图中1-边、2-边的数目.进一步地，我们指出猜想2的条件是不完备的，并给出了图在3-划分情形下猜想2成立的一个充分条件:对于边数m≥2且不同构于K1,3的图G，如果最大度△≥2/5m，那么图中存在一个3-划分，使得每个顶点子集相交边的数目至少为2/5m.　　第三章主要讨论图的公平κ-划分下每个顶点子集相交边数的下界，研究猜想3对不同图类成立的条件.我们证明了猜想3对于稠密图是成立的，即如果图的最小度δ(G)≥εn，则图G中存在κ-划分，使得每个划分子集都与至少(1+o(1))（1-（1-1/k)2）m条边相交.我们还利用二阶矩法证明了如果图满足如下条件之一，m≥ε-2n或者d(υ)≤ε2n，则G中存在κ-划分同时限制顶点子集内部以及顶点子集之间的边的数目.在第四小节中，我们指出猜想3的条件是不完备的，进而讨论了完全二部图的κ-划分情形，研究并确定了划分参数κ与最小度δ之间的关系，ε-3≤δ≤n/2或者k2-k/2k-1≤δ≤κ，给出了完全二部图满足猜想3的充分条件.　　最后一章总结了全文的要点，并提出了可以进一步研究的问题.