主题
Search

团覆盖数

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

图 G 的团覆盖数 theta(G) 是覆盖图 G 的顶点集所需的最小团数，即形成 G 的顶点覆盖。由于 theta(G) 涉及最小团数，因此只需要考虑极大团（因为非极大团无法产生更小尺寸的团覆盖）。

团覆盖数也可以用以下公式表示：

theta(G)=chi(G^_),

其中 chi(H) 是图 H 的着色数，而 G^_ 是 G 的图补。

一些图类的团覆盖数如下：

图 Gtheta(G)
完全 k-部图 K_(n_1,...,n_k)，其中 k>1max_(1<=i<=k)n_i
完全图 K_n1
圈图 C_n{n/2 for n even; (n+1)/2 for n odd

另请参阅

着色数, 团覆盖, 图补, 交集数, 最大团

使用 Wolfram|Alpha 探索

参考文献

West, D. B. 图论导论，第二版 Englewood Cliffs, NJ: Prentice-Hall, p. 226, 2000.

请引用为

Weisstein, Eric W. "团覆盖数。" 来自 MathWorld--Wolfram 网络资源。 https://mathworld.net.cn/CliqueCoveringNumber.html

主题分类