主题
Search

完全k-部图

CompleteKPartiteGraph

一个完全 k-部图是一个 k-部图 （即，图顶点的集合被分解为 k 个不相交的集合，使得同一集合内的任意两个 图顶点 都不相邻），并且来自不同集合的每对 图顶点 都相邻。如果这 k 个集合中分别有 p, q, ..., r 图顶点，则完全 k-部图记为 k-部图记为 K_(p,q,...,r)。上图显示了完全三部图 K_(2,3,5)。

符号 K_(m×n) 有时用来表示 K_(n,...,n_()_(m)) (Brouwer et al. 1989, p. 478)。

对于某个 k 而言，如果是完全k-部图的图被称为完全多部图 (Chartrand and Zhang 2008, p. 41)。完全多部图可以在多项式时间内通过有限禁忌子图特征来识别，因为完全多部图是 P^__3-free 的（其中 P^__3 是路径图 路径图 P_3 的图补图）。

形状为 p, q, ... 的完全多部图在 Wolfram 语言中实现为CompleteGraph[{p, q, ...}].

图兰图 是一个完全多部图，其部集的大小尽可能接近相等 (Gross and Yellen 2006, p. 476)。

特殊情况总结在下表中。

K_n完全图
K_(m,n)完全二部图
K_(1,n)星图 S_n
K_(k,m,n)完全三部图
K_(1,1,1,n)(3,n)-锥图
K_(m×1)完全图 K_m
K_(m×2)鸡尾酒会图 mP_2^_
K_(3×2)八面体图
K_(4×2)16-胞图

当 m>=2 时，完全 K_(n_1,n_2,...,n_m) 部图 K_(n_1,n_2,...,n_m) 具有哈密顿 [准哈密顿] 分解当且仅当 m>=2 且 n_1=n_2=...=n_m 是偶数 [奇数] (Bosák 1990, p. 124)。

另请参阅

完全二部图, 完全图, 完全三部图, k-部图, 图兰图

使用 Wolfram|Alpha 探索

参考文献

Bosák, J. 图的分解。 New York: Springer, 1990.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. 距离正则图。 New York: Springer-Verlag, 1989.Chartrand, G. and Zhang, P. 图着色理论。 Boca Raton, FL: Chapman and Hall/CRC, 2008.Gross, J. T. and Yellen, J. 图论及其应用，第二版。 Boca Raton, FL: CRC Press, pp. 476-477, 2006.Harary, F. 图论。 Reading, MA: Addison-Wesley, p. 23, 1994.Saaty, T. L. and Kainen, P. C. 四色问题：进攻与征服。 New York: Dover, p. 12, 1986.Skiena, S. "完全 k-部图。" §4.2.2 in 离散数学实现：组合数学和图论与 Mathematica。 Reading, MA: Addison-Wesley, pp. 142-144, 1990.

在 Wolfram|Alpha 中被引用

完全k-部图

请引用为

Weisstein, Eric W. "完全 k-部图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Completek-PartiteGraph.html

主题分类