多分图
在数学的分支图论中,一个 k-分图是一个图,其点集被分成 k 部分,各部分各自形成独立集。换句话说,可以把图的所有点着色,使得相邻的点着不同色且总共用了k 个颜色。k = 2 的情况被称作二分图,而 k = 3 的情况被称作三分图。
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。
参考资料
[编辑]- ^ Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, GT4, 1979, ISBN 0-7167-1045-5.
- ^ Hotho, Andreas; Jäschke, Robert; Schmitz, Christoph; Stumme, Gerd, FolkRank : A Ranking Algorithm for Folksonomies, LWA 2006: Lernen - Wissensentdeckung - Adaptivität, Hildesheim, October 9th-11th 2006: 111–114, 2006[失效链接].
- ^ Chartrand, Gary; Zhang, Ping, Chromatic Graph Theory, CRC Press: 41, 2008, ISBN 9781584888017.
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.