maximal_independent_set#

maximal_independent_set(G, nodes=None, seed=None)[source]#

返回一个包含给定节点集合的随机最大独立集。

独立集是一组节点，由这些节点诱导的G的子图不包含任何边。最大独立集是一个独立集，无法再添加新节点而仍然保持独立集的性质。

Parameters:
GNetworkX图
nodes列表或可迭代对象

必须属于独立集的节点。这组节点必须是独立的。

seed整数，random_state，或None（默认）

随机数生成状态的指示器。 参见 随机性 。

Returns:
indep_nodes列表

属于最大独立集的节点列表。

Raises:
NetworkXUnfeasible

如果提供的列表中的节点不属于图或不构成独立集，则引发异常。

NetworkXNotImplemented

如果 G 是有向图。

Notes

该算法不解决最大独立集问题。

Examples

>>> G = nx.path_graph(5)
>>> nx.maximal_independent_set(G)  
[4, 0, 2]
>>> nx.maximal_independent_set(G, [1])  
[1, 3]
On this page