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

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

用法

st_cuts(graph, source, target)

参数

graph

输入图。 必须是有向图。

source

源顶点。

target

目标顶点。

值

一个包含以下条目的列表

cuts

包含边 ID 的数值向量列表。 每个向量都是一个 \((s,t)\)-割。

partition1s

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

详细信息

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

参考文献

JS Provan 和 DR Shier: 一种列出图中 (s,t)-割的范式，Algorithmica 15, 351–372, 1996。

参见

其他流: dominator_tree(), edge_connectivity(), is_min_separator(), is_separator(), max_flow(), min_cut(), min_separators(), min_st_separators(), st_min_cuts(), vertex_connectivity()

作者

Gabor Csardi csardi.gabor@gmail.com

C 库中的相关文档

all_st_cuts().

示例

# A very simple graph
g <- graph_from_literal(a -+ b -+ c -+ d -+ e)
st_cuts(g, source = "a", target = "e")
#> $cuts
#> $cuts[[1]]
#> + 1/4 edge from ba10d11 (vertex names):
#> [1] a->b
#> 
#> $cuts[[2]]
#> + 1/4 edge from ba10d11 (vertex names):
#> [1] b->c
#> 
#> $cuts[[3]]
#> + 1/4 edge from ba10d11 (vertex names):
#> [1] c->d
#> 
#> $cuts[[4]]
#> + 1/4 edge from ba10d11 (vertex names):
#> [1] d->e
#> 
#> 
#> $partition1s
#> $partition1s[[1]]
#> + 1/5 vertex, named, from ba10d11:
#> [1] a
#> 
#> $partition1s[[2]]
#> + 2/5 vertices, named, from ba10d11:
#> [1] a b
#> 
#> $partition1s[[3]]
#> + 3/5 vertices, named, from ba10d11:
#> [1] a b c
#> 
#> $partition1s[[4]]
#> + 4/5 vertices, named, from ba10d11:
#> [1] a b c d
#> 
#> 

# 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")
#> $cuts
#> $cuts[[1]]
#> + 2/10 edges from b483fe7 (vertex names):
#> [1] s->a s->b
#> 
#> $cuts[[2]]
#> + 2/10 edges from b483fe7 (vertex names):
#> [1] s->a b->t
#> 
#> $cuts[[3]]
#> + 5/10 edges from b483fe7 (vertex names):
#> [1] s->b a->t a->1 a->2 a->3
#> 
#> $cuts[[4]]
#> + 5/10 edges from b483fe7 (vertex names):
#> [1] s->b a->t a->1 a->2 3->b
#> 
#> $cuts[[5]]
#> + 5/10 edges from b483fe7 (vertex names):
#> [1] s->b a->t a->1 a->3 2->b
#> 
#> $cuts[[6]]
#> + 5/10 edges from b483fe7 (vertex names):
#> [1] s->b a->t a->1 2->b 3->b
#> 
#> $cuts[[7]]
#> + 5/10 edges from b483fe7 (vertex names):
#> [1] s->b a->t a->2 a->3 1->b
#> 
#> $cuts[[8]]
#> + 5/10 edges from b483fe7 (vertex names):
#> [1] s->b a->t a->2 1->b 3->b
#> 
#> $cuts[[9]]
#> + 5/10 edges from b483fe7 (vertex names):
#> [1] s->b a->t a->3 1->b 2->b
#> 
#> $cuts[[10]]
#> + 5/10 edges from b483fe7 (vertex names):
#> [1] s->b a->t 1->b 2->b 3->b
#> 
#> $cuts[[11]]
#> + 2/10 edges from b483fe7 (vertex names):
#> [1] a->t b->t
#> 
#> 
#> $partition1s
#> $partition1s[[1]]
#> + 1/7 vertex, named, from b483fe7:
#> [1] s
#> 
#> $partition1s[[2]]
#> + 2/7 vertices, named, from b483fe7:
#> [1] s b
#> 
#> $partition1s[[3]]
#> + 2/7 vertices, named, from b483fe7:
#> [1] s a
#> 
#> $partition1s[[4]]
#> + 3/7 vertices, named, from b483fe7:
#> [1] s a 3
#> 
#> $partition1s[[5]]
#> + 3/7 vertices, named, from b483fe7:
#> [1] s a 2
#> 
#> $partition1s[[6]]
#> + 4/7 vertices, named, from b483fe7:
#> [1] s a 2 3
#> 
#> $partition1s[[7]]
#> + 3/7 vertices, named, from b483fe7:
#> [1] s a 1
#> 
#> $partition1s[[8]]
#> + 4/7 vertices, named, from b483fe7:
#> [1] s a 1 3
#> 
#> $partition1s[[9]]
#> + 4/7 vertices, named, from b483fe7:
#> [1] s a 1 2
#> 
#> $partition1s[[10]]
#> + 5/7 vertices, named, from b483fe7:
#> [1] s a 1 2 3
#> 
#> $partition1s[[11]]
#> + 6/7 vertices, named, from b483fe7:
#> [1] s a 1 2 3 b
#> 
#>