R igraph 手册页

st_cuts {igraph}

R 文档

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

描述

列出有向图中的所有 (s,t)-割。

用法

st_cuts(graph, source, target)

参数

图	输入图。必须是有向图。
来源	源顶点。
目标	目标顶点。

详细信息

给定一个有向图 G 和两个不同的、非相邻的顶点 s 和 t，一个 (s,t)-割是一组边，在从 G 中移除这些边后，不存在从 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_min_cuts 列出所有最小割。

示例

# A very simple graph
g <- graph_from_literal(a -+ b -+ c -+ d -+ e)
st_cuts(g, source="a", target="e")

# A somewhat more difficult graph
g2 <- graph_from_literal(s --+ a:b, a:b --+ t,
                   a --+ 1:2:3, 1:2:3 --+ b)
st_cuts(g2, source="s", target="t")

---