跳到内容

最小顶点分隔符

来源：R/flow.R
is_min_separator.Rd

检查给定的顶点集合是否为最小顶点分隔符。

用法

is_min_separator(graph, candidate)

参数

graph

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

candidate

一个数字向量，给出候选分隔符的顶点 ID。

值

一个逻辑标量，指示所提供的顶点集合是否为（最小）顶点分隔符。

详细信息

is_min_separator() 确定所提供的顶点集合是否为最小顶点分隔符。 最小顶点分隔符是一个顶点分隔符，其任何真子集都不是顶点分隔符。

参见

其他流相关函数：dominator_tree(), edge_connectivity(), is_separator(), max_flow(), min_cut(), min_separators(), min_st_separators(), st_cuts(), st_min_cuts(), vertex_connectivity()

is_minimal_separator().

示例

# The graph from the Moody-White paper
mw <- graph_from_literal(
  1 - 2:3:4:5:6, 2 - 3:4:5:7, 3 - 4:6:7, 4 - 5:6:7,
  5 - 6:7:21, 6 - 7, 7 - 8:11:14:19, 8 - 9:11:14, 9 - 10,
  10 - 12:13, 11 - 12:14, 12 - 16, 13 - 16, 14 - 15, 15 - 16,
  17 - 18:19:20, 18 - 20:21, 19 - 20:22:23, 20 - 21,
  21 - 22:23, 22 - 23
)

# Cohesive subgraphs
mw1 <- induced_subgraph(mw, as.character(c(1:7, 17:23)))
mw2 <- induced_subgraph(mw, as.character(7:16))
mw3 <- induced_subgraph(mw, as.character(17:23))
mw4 <- induced_subgraph(mw, as.character(c(7, 8, 11, 14)))
mw5 <- induced_subgraph(mw, as.character(1:7))

check.sep <- function(G) {
  sep <- min_separators(G)
  sapply(sep, is_min_separator, graph = G)
}

check.sep(mw)
#> [1] TRUE
check.sep(mw1)
#> [1] TRUE TRUE TRUE TRUE
check.sep(mw2)
#> [1] TRUE TRUE TRUE
check.sep(mw3)
#> [1] TRUE
check.sep(mw4)
#> [1] FALSE FALSE FALSE FALSE
check.sep(mw5)
#> [1] TRUE TRUE TRUE