数学的分支图论中,一个 k-分图是一个,其点集被分成 k 部分,各部分各自形成独立集。换句话说,可以把图的所有点着色,使得相邻的点着不同色且总共用了k 个颜色。k = 2 的情况被称作二分图,而 k = 3 的情况被称作三分图

特殊种类的完全 k-分图
K2,2,2 K3,3,3 K2,2,2,2

正八面体顶点和边组成的图

复广义正八面体的顶点和边组成的图

正十六胞体的顶点和边组成的图

事实上,辨别一个图是二分图只需要多项式时间。但当 k > 2,辨别一个图是否为 k-分图却是NP完全[1] 。不过,在一些图论的应用场合中,给计算器处理 k-分图会包含 k 个部分的划分,比如说各个部分所代表的是不同类型的物件。例如可以用三分图做大众分类法的数学模型,三个部分分别为系统的使用者、系统拥有的资料来源、使用者给资料来源的标签[2]

一个完全 k-分图是一个 k-分图,其中两点若属于相异的部分则必相邻。该图的记为一个大写 K,在下标标注个部分的顶点数,并用英文逗号分开。例如 K2,2,2 可以想成正八面体的顶点和边,其中三个独立集使三组对顶点。所有的完全 k-分图统称为完全多分图[3]图兰图是一种特殊的完全多分图,其中各部分的顶点数至多差 1。

参考资料

编辑