cut_size#

cut_size(G, S, T=None, weight=None)[source]#

返回两个节点集合之间的割的大小。

割 是将图的节点分成两个集合的分区。割的大小 是两个节点集合之间边的权重的总和。

Parameters:
GNetworkX 图
S集合

图 G 中的节点集合。

T集合

图 G 中的节点集合。如果未指定，则视为 S 的补集。

weight对象

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

Returns:
数字

从集合 S 中的节点到集合 T 中的节点的所有边的总权重（对于有向图，还包括从集合 T 中的节点到集合 S 中的节点的所有边）。

Notes

在多重图中，割的大小是包括多重性的边的总权重。

Examples

在由一条边连接两个团（完全子图）的图中，将图自然地分成两个块，每个团一个块，得到的割的权重为1:

>>> G = nx.barbell_graph(3, 0)
>>> S = {0, 1, 2}
>>> T = {3, 4, 5}
>>> nx.cut_size(G, S, T)
1

在多重图中，每条平行边在确定割大小时都会被计算:

>>> G = nx.MultiGraph(["ab", "ab"])
>>> S = {"a"}
>>> T = {"b"}
>>> nx.cut_size(G, S, T)
2

Additional backends implement this function

graphblas : OpenMP-enabled sparse linear algebra backend.

On this page