主题
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].

参见

独立顶点集, 极大团, 极大集, 最大独立顶点集, 良覆盖图

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 上被引用

极大独立顶点集

请引用为

Weisstein, Eric W. "极大独立顶点集。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/MaximalIndependentVertexSet.html

主题分类