R igraph 手册页

st_min_cuts {igraph}

R 文档

列出图的所有最小 (s,t)-割

描述

列出给定 s 和 t 的有向图的所有最小 (s,t)-割。

用法

st_min_cuts(graph, source, target, capacity = NULL)

参数

图	输入图。必须是有向图。
来源	源顶点的 ID。
目标	目标顶点的 ID。
容量	数值向量，给出边的容量。如果这是 NULL 并且该图具有 weight 边属性，则此属性定义边的容量。要强制使用单位边容量，即使对于具有 weight 边属性的图，也请在此处提供 NA。

详细信息

给定一个 G 有向图和两个不同的非相邻顶点 s 和 t，一个 (s,t)-割是一组边，使得从 G 中删除这些边之后，不存在从 s 到 t 的有向路径。

(s,t)-割的大小定义为割中容量（或权重）的总和。对于未加权（=等权重）图，这只是边的数量。

如果 (s,t)-割的大小尽可能小，则它是最小割。

值

包含以下条目的列表

值	数值标量，最小割的大小。
割	包含边 ID 的数值向量列表。每个向量都是一个最小 (s,t)-割。
partition1s	包含顶点 ID 的数值向量列表，它们对应于边割。每个顶点集都是相应割的生成器，即在图 G=(V,E) 中，顶点集 X 及其补集 V-X 生成恰好包含从 X 到 V-X 的边的割。

作者

Gabor Csardi csardi.gabor@gmail.com

参考

JS Provan 和 DR Shier: 列出图中 (s,t) 切割的范例, Algorithmica 15, 351–372, 1996。

参见

st_cuts, min_separators

示例

# A difficult graph, from the Provan-Shier paper
g <- graph_from_literal(s --+ a:b, a:b --+ t,
               a --+ 1:2:3:4:5, 1:2:3:4:5 --+ b)
st_min_cuts(g, source="s", target="t")

---