部图

部图(partite graph)是一类特殊的图，即一个图的节点集可分成若干个子集，使得每一条边的两端点不在同一子集内，若一个图的节点集能分成k个两两不交的非空子集，使得这个图的每一条边的两端点不在同一个子集内，则称这个图为k部图。若k=2，则称这种k部图为二部图；若k=3，则称这种k部图为三部图，若在一个k部图中，任一节点与其他部的所有节点都相邻，则称它为完全k部图。

基本介绍若图G的点集V有一个划分

所有Vi非空，且均为全不连通的，则称G是一个n部图，2部图又称双图，(1)称为G的一个n部划分，G也记作G=()。显然任何p阶图是一个p部图。若n10吋，若H不含Kn+1，在H中取一点v，使deg v=Δ(H)，由v的郤域N(v)导出的子图中不含Kn，故E()已经定义，再加上p(H)-Δ(H)个点，使它们毎一个均与E()的毎个点邻接，即得到一个E(H)。一般地，E(H)不必唯一，显然p(E(H)= p(H)，今有下列引理。

引理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时成立1。

定理7对任何双图G=(V1，V2；X)，存在一个正则双图H，使G⊂H，且deg H=Δ(G)。

本词条内容贡献者为:

任毅如 - 副教授 - 湖南大学