maximal_independent_set#
- maximal_independent_set(G, nodes=None, seed=None)[源代码]#
返回保证包含给定节点集的随机最大独立集。
一个独立集是一组节点,使得由这些节点引起的g的子图不包含边。最大独立集是一个独立集,因此不可能添加一个新的节点,仍然可以得到一个独立集。
- 参数
- G网络X图表
- nodes列表或可迭代
必须是独立集一部分的节点。这组节点必须是独立的。
- seed整数、随机状态或无(默认)
随机数生成状态的指示器。见 Randomness .
- 返回
- 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]