主題
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

另請參閱

著色數, 團覆蓋, 圖補, 交集數, 最大團

使用 探索

參考文獻

West, D. B. 圖論導論，第二版 Englewood Cliffs, NJ: Prentice-Hall, p. 226, 2000.

請引用為

Weisstein, Eric W. "團覆蓋數。" 來自 網路資源。 https://mathworld.tw/CliqueCoveringNumber.html

主題分類