跳到内容

最小尺寸顶点分隔符

来源：R/flow.R
min_st_separators.Rd

列出所有对于无向图中某些 \(s\) 和 \(t\) 来说是最小 \((s,t)\) 分隔符的顶点集。

用法

min_st_separators(graph)

参数

graph

输入图。它可以是有向图，但边方向将被忽略。

值

一个数值向量列表。每个向量包含一个顶点集（由顶点 ID 定义），每个向量是输入图的 \((s,t)\) 分隔符，对于某些 \(s\) 和 \(t\)。

详细信息

\((s,t)\) 顶点分隔符是一组顶点，从图中移除这些顶点后，图中 \(s\) 和 \(t\) 之间没有路径。

如果 \((s,t)\) 顶点分隔符的任何真子集都不是同一 \(s\) 和 \(t\) 的 \((s,t)\) 顶点分隔符，则它是最小的。

注意

请注意，尽管其子集 {1} 也是一个分隔符，但下面的代码返回 {1, 3}。这是因为 {1, 3} 对于分隔顶点 2 和 4 来说是最小的。

g <- make_graph(~ 0-1-2-3-4-1)
min_st_separators(g)

#> [[1]]
#> + 1/5 vertex, named:
#> [1] 1
#>
#> [[2]]
#> + 2/5 vertices, named:
#> [1] 2 4
#>
#> [[3]]
#> + 2/5 vertices, named:
#> [1] 1 3

参考文献

Anne Berry, Jean-Paul Bordat 和 Olivier Cogis：Generating All the Minimal Separators of a Graph, In: Peter Widmayer, Gabriele Neyer 和 Stephan Eidenbenz (editors): Graph-theoretic concepts in computer science, 1665, 167–172, 1999. Springer.

参见

其他流： dominator_tree(), edge_connectivity(), is_min_separator(), is_separator(), max_flow(), min_cut(), min_separators(), st_cuts(), st_min_cuts(), vertex_connectivity()

作者

Gabor Csardi csardi.gabor@gmail.com

all_minimal_st_separators().

示例


ring <- make_ring(4)
min_st_separators(ring)
#> [[1]]
#> + 2/4 vertices, from 32f7c4d:
#> [1] 2 4
#> 
#> [[2]]
#> + 2/4 vertices, from 32f7c4d:
#> [1] 1 3
#> 

chvatal <- make_graph("chvatal")
min_st_separators(chvatal)
#> [[1]]
#> + 4/12 vertices, from 8014f07:
#> [1]  7 10 11 12
#> 
#> [[2]]
#> + 4/12 vertices, from 8014f07:
#> [1]  3  6  8 11
#> 
#> [[3]]
#> + 4/12 vertices, from 8014f07:
#> [1]  2  7  9 12
#> 
#> [[4]]
#> + 4/12 vertices, from 8014f07:
#> [1]  8 10 11 12
#> 
#> [[5]]
#> + 4/12 vertices, from 8014f07:
#> [1]  6  9 11 12
#> 
#> [[6]]
#> + 4/12 vertices, from 8014f07:
#> [1]  2  5  7 10
#> 
#> [[7]]
#> + 4/12 vertices, from 8014f07:
#> [1] 1 3 6 8
#> 
#> [[8]]
#> + 4/12 vertices, from 8014f07:
#> [1] 2 4 7 9
#> 
#> [[9]]
#> + 4/12 vertices, from 8014f07:
#> [1]  3  5  8 10
#> 
#> [[10]]
#> + 4/12 vertices, from 8014f07:
#> [1] 1 4 6 9
#> 
#> [[11]]
#> + 4/12 vertices, from 8014f07:
#> [1] 1 2 4 5
#> 
#> [[12]]
#> + 4/12 vertices, from 8014f07:
#> [1] 1 3 4 5
#> 
#> [[13]]
#> + 6/12 vertices, from 8014f07:
#> [1]  3  6  8 10 11 12
#> 
#> [[14]]
#> + 6/12 vertices, from 8014f07:
#> [1]  4  6  7  9 11 12
#> 
#> [[15]]
#> + 6/12 vertices, from 8014f07:
#> [1]  2  4  5  7 10 12
#> 
#> [[16]]
#> + 6/12 vertices, from 8014f07:
#> [1]  3  4  5  7 10 11
#> 
#> [[17]]
#> + 6/12 vertices, from 8014f07:
#> [1]  6  7  8  9 11 12
#> 
#> [[18]]
#> + 6/12 vertices, from 8014f07:
#> [1]  3  5  7  8 10 11
#> 
#> [[19]]
#> + 6/12 vertices, from 8014f07:
#> [1]  3  4  6  7  9 11
#> 
#> [[20]]
#> + 6/12 vertices, from 8014f07:
#> [1] 1 3 4 5 6 8
#> 
#> [[21]]
#> + 6/12 vertices, from 8014f07:
#> [1]  1  2  6  8  9 12
#> 
#> [[22]]
#> + 6/12 vertices, from 8014f07:
#> [1]  2  5  7  8 10 12
#> 
#> [[23]]
#> + 6/12 vertices, from 8014f07:
#> [1] 1 2 4 5 7 9
#> 
#> [[24]]
#> + 6/12 vertices, from 8014f07:
#> [1]  2  7  9 10 11 12
#> 
#> [[25]]
#> + 6/12 vertices, from 8014f07:
#> [1]  1  6  8  9 11 12
#> 
#> [[26]]
#> + 6/12 vertices, from 8014f07:
#> [1]  1  2  5  8 10 12
#> 
#> [[27]]
#> + 6/12 vertices, from 8014f07:
#> [1]  1  3  5  8 10 11
#> 
#> [[28]]
#> + 6/12 vertices, from 8014f07:
#> [1]  1  2  4  6  9 12
#> 
#> [[29]]
#> + 6/12 vertices, from 8014f07:
#> [1]  1  3  4  6  9 11
#> 
#> [[30]]
#> + 6/12 vertices, from 8014f07:
#> [1]  1  2  3  5  8 10
#> 
#> [[31]]
#> + 6/12 vertices, from 8014f07:
#> [1] 1 2 3 4 6 9
#> 
#> [[32]]
#> + 6/12 vertices, from 8014f07:
#> [1]  2  3  4  5  7 10
#> 
# https://github.com/r-lib/roxygen2/issues/1092