cut_size

cut_size(G, S, T=None, weight=None)

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

一个割是将图的节点划分为两个集合的一种划分。割的大小是两个节点集合之间边的权重的总和。

参数:

GNetworkX 图

S集合

图 G 中的一个节点集合。

T集合

图 G 中的一个节点集合。如果未指定，则认为是 S 的补集。

weight对象

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

返回:

数值

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

注意

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

示例

在一个由单条边连接两个团的图中，将图自然地二分划分为两个块，每个块对应一个团，产生的割的权重为 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

---

其他后端实现了此函数

graphblas : 支持 OpenMP 的稀疏线性代数后端。