maximal_independent_set#
- maximal_independent_set(G, nodes=None, seed=None)[源代码]#
返回一个随机极大独立集，该独立集保证包含给定的节点集合。
独立集是一个节点集合，使得这些节点诱导的 G 的子图不包含任何边。极大独立集是一个独立集，且不能再添加新的节点并仍然形成独立集。
- 参数：
- GNetworkX 图
- nodes列表或可迭代对象
必须是独立集一部分的节点。此节点集合必须是独立集。
- seed整数、random_state 或 None (默认)
随机数生成状态的指示符。参见 随机性。
- 返回：
- indep_nodes列表
构成极大独立集一部分的节点列表。
- 引发：
- NetworkXUnfeasible
如果提供的列表中的节点不是图的一部分，或不构成独立集，则会引发异常。
- NetworkXNotImplemented
如果
G是有向图。
注意
此算法不解决最大独立集问题。
示例
>>> G = nx.path_graph(5) >>> nx.maximal_independent_set(G) [4, 0, 2] >>> nx.maximal_independent_set(G, [1]) [1, 3]