one_exchange

one_exchange(G, initial_cut=None, seed=None, weight=None)

计算图的节点划分及其对应的割值。

使用贪心的一交换策略来找到一个局部最大割及其值，该策略通过找到最佳节点（即对割值贡献最大的节点）添加到当前割中，并重复此过程直到无法再改进。

Parameters:

Gnetworkx 图

要找到最大割的图。

initial_cut集合

用作起点的割。如果未提供，算法从空割开始。

seed整数, random_state, 或 None (默认)

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

weight对象

用作权重的边属性键。如果未指定，边权重为1。

Returns:

cut_value标量

最大割的值。

partition节点集对

定义最大割的节点划分。

Raises:

NetworkXNotImplemented

如果图是有向的或是一个多重图。

Examples

>>> G = nx.complete_graph(5)
>>> curr_cut_size, partition = nx.approximation.one_exchange(G, seed=1)
>>> curr_cut_size
6
>>> partition
({0, 2}, {1, 3, 4})