跳到内容

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

来源：R/flow.R
st_min_cuts.Rd

列出有向图对于给定 \(s\) 和 \(t\) 的所有最小 \((s,t)\) 切割。

用法

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

参数

graph

输入图。必须是有向图。

source

源顶点的ID。

target

目标顶点的 ID。

capacity

数值向量，给出边的容量。如果这是 NULL 并且图有一个 weight 边属性，则此属性定义边的容量。为了强制单位边容量，即使对于具有 weight 边属性的图，也在此处提供 NA。

值

一个包含以下条目的列表

value

数值标量，最小切割的大小。

cuts

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

partition1s

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

详细信息

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

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

如果一个 \((s,t)\) 切割的大小是最小可能的，则它是最小的。

参考文献

JS Provan 和 DR Shier: A Paradigm for listing (s,t)-cuts in graphs, Algorithmica 15, 351–372, 1996。

参见

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

作者

Gabor Csardi csardi.gabor@gmail.com

all_st_mincuts().

示例


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