randomized_partitioning

randomized_partitioning(G, seed=None, p=0.5, weight=None)

计算图节点的一个随机划分及其割值。

通过观察每个节点并决定以概率 p 将其添加到第一个分区中，计算出一个随机割及其对应的值（连接不同分区的边的权重之和）。

Parameters:

GNetworkX 图

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

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

p标量

每个节点属于第一个分区的概率。 应在 [0,1] 范围内。

weight对象

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

Returns:

cut_size标量

最小割的值。

partition节点集对

定义最小割的节点划分。

Raises:

NetworkXNotImplemented

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

Examples

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