更新时间：2022-08-25 16:47
部图(partite graph)是一类特殊的图，即一个图的节点集可分成若干个子集，使得每一条边的两端点不在同一子集内，若一个图的节点集能分成k个两两不交的非空子集，使得这个图的每一条边的两端点不在同一个子集内，则称这个图为k部图。若k=2，则称这种k部图为二部图；若k=3，则称这种k部图为三部图，若在一个k部图中，任一节点与其他部的所有节点都相邻，则称它为完全k部图。
若图G的点集V有一个划分
所有Vi非空，且 如果在一个n部图G=()中，，任何两点u∈Vi，v∈Vj，i≠j，i=1，2，…，n，均有u adj v，则称G为完全n部图，记作。图1中给出了完全2部图K2,3(a)和一个3部图(b)。 一般来说，一个n部图的n部划分不是唯一的，但对连通双图有下列定理。 定理1 连通双图G=(V1，V2；X)的2部划分唯一， 证 取v∈V1，由于G是连通的，对任何u∈V1∪V2，有联结v和u的道路，故d(v，u)有定义，因为任何一条以v为起点的道路交替地经过V1和V2的点，可知一点u∈V2当且仅当d(v，u)是奇数。这个准则唯一地决定了G的2部划分。证毕。 双图的特征由下列定理给出．
定理2 一个图G是一个双图当且仅当它不含有长度为奇数的圈。
定理3任何不含有三角形的(p, q)图G有
当G=Km,m或Km,m+1时等号成立。
定理3可以推广，事实. 上，它可以由下面的定理6推出。但定理6的证明较定理3复杂得多。设G和H是两个p阶图， 若存在V(G)到V(H)的一个一一对应μ，使对任何点u∈V(G)，有
degGu≥degHμ(u)，
则称G的度序列优于H。
现在我们对n≥0递推地定义不含Kn+1的图H的厄尔多斯
(Erdös)图E(H)，n=0时，若H不含K1，则H是全不连通的，令E(H)=H， n>0吋，若H不含Kn+1，在H中取一点v，使deg v=Δ(H)，由v的郤域N(v)导出的子图
引理4 对任何不含Kn+1的图H，E(H)是一个完全n部图，且E(H)的度序列优于H，此外，若更有E(H)的度序列与H的度序列相同，则
引理5 p阶n部图G有最多的线当且仅当G≌Tn,p。
定理6(托兰(Turán)定理)若p阶图G中不含Kn+1，则|X(G)|≤|X(Tn,p)|，等号当且仅当G≌Tn,p时成立。
定理7对任何双图G=(V1，V2；X)，存在一个正则双图H，使G⊂H，且deg H=Δ(G)。