主題
Search

極大獨立頂點集

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本

圖的極大獨立頂點集是一個獨立頂點集，它不能透過在圖中新增任何頂點來擴充套件為另一個獨立頂點集。

圖G的極大獨立頂點集等價於圖補圖G^'上的極大團。

請注意，極大獨立頂點集不等價於最大獨立頂點集，後者是一個獨立頂點集，在所有獨立頂點集中包含可能最多的頂點。一個最大獨立頂點集總是極大的，但反之則不然。

圖的頂點集V的子集B subset V是一個極大獨立頂點集當且僅當B既是支配集又是獨立頂點集（Burger等人1997）。

任何極大獨立頂點集也是極小支配集和極大非冗餘集（Mynhardt 和 Roux 2020）。因此，下獨立數（即最小極大獨立頂點集的大小）等價於獨立支配數。

圖的極大獨立頂點集可以使用 Wolfram 語言 計算，使用方法如下FindIndependentVertexSet[g,Infinity]，所有極大獨立頂點集可以使用以下方法計算FindIndependentVertexSet[g,Infinity, All].

參見

獨立頂點集, 極大團, 極大集, 最大獨立頂點集, 良覆蓋圖

使用 探索

參考文獻

Burger, A. P.; Cockayne, E. J.; 和 Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.Hedetniemi, S. T. 和 Laskar, R. C. "A. Bibliography on Dominating Sets in Graphs and Some Basic Definitions of Domination Parameters." Disc. Math. 86, 257-277, 1990.Mynhardt, C. M. 和 Roux, A. "Irredundance Graphs." 2020年4月14日. https://arxiv.org/abs/1812.03382.Myrvold, W. 和 Fowler, P. W. "Fast Enumeration of All Independent Sets up to Isomorphism." J. Comb. Math. Comb. Comput. 85, 173-194, 2013.

在 上被引用

極大獨立頂點集

請引用為

Weisstein, Eric W. "極大獨立頂點集。" 來自 Web 資源。 https://mathworld.tw/MaximalIndependentVertexSet.html

主題分類