支配集

對於一個 圖 和一個 頂點集 的子集 ，用 表示 中頂點集合，這些頂點在 中或與 中的頂點相鄰。如果 ，那麼 被稱為支配集（ 中的頂點）。

最小尺寸的支配集稱為最小支配集，其大小稱為支配數。不是任何其他支配集的真子集的支配集稱為極小支配集。

例如，在上面所示的Petersen 圖中，集合 是一個支配集（實際上，是一個最小支配集）。

支配多項式編碼各種大小的支配集的數量。

可以定義常見支配集的其他變體，包括所謂的全支配集。

如果一個集合是支配的且無冗餘的，那麼它是極大無冗餘的和極小支配的 (Mynhardt and Roux 2020)。

一個支配集是極小支配的 當且僅當 它是無冗餘的 (Mynhardt and Roux 2020)。

可以使用 Wolfram 語言 獲取許多命名圖的預計算支配集GraphData[graph,"DominatingSets"].