主題
Search

最大獨立頂點集

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook

圖 graph G 的獨立頂點集是頂點的子集，使得子集中沒有兩個頂點表示圖 G 的邊。給定圖的頂點覆蓋，所有不在覆蓋中的頂點定義了一個獨立頂點集（Skiena 1990, p. 218）。最大獨立頂點集是對於給定圖，包含可能的最大頂點數的獨立頂點集。

最大獨立頂點集不等同於極大獨立頂點集，極大獨立頂點集只是一個不能擴充套件到更大獨立頂點集的獨立頂點集。每個最大獨立頂點集也是一個獨立頂點集，但反之不然。

圖的獨立數是最大獨立集的基數。

最大獨立頂點集對應於最小頂點覆蓋的補集。

MaximumIndependentSet

在給定的圖 graph g 中，可以使用 Wolfram 語言找到最大獨立頂點集，方法是使用FindIndependentVertexSet[g][[1]]。命令Sort[FindIndependentVertexSet[g,Length /@ FindIndependentVertexSet[g], All]] 將找到所有最大獨立頂點集。

另請參閱

獨立數, 獨立集, 獨立頂點集, 極大獨立頂點集, 最大獨立邊集, 最大獨立集問題, 最小頂點覆蓋, 頂點覆蓋

使用 探索

參考文獻

Myrvold, W. and Fowler, P. W. "Fast Enumeration of All Independent Sets up to Isomorphism." J. Comb. Math. Comb. Comput. 85, 173-194, 2013.Pemmaraju, S. and Skiena, S. "Maximum Independent Set." §7.5.3 載於 Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, p. 318, 2003.Skiena, S. "Maximum Independent Set." §5.6.3 載於 Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 218-219, 1990.

請引用為

Weisstein, Eric W. "Maximum Independent Vertex Set." 來自 Web 資源。 https://mathworld.tw/MaximumIndependentVertexSet.html

學科分類