Check whether removing this set of vertices would disconnect the graph.

is_separator() determines whether the supplied vertex set is a vertex separator: A vertex set \(S\) is a separator if there are vertices \(u\) and \(v\) in the graph such that all paths between \(u\) and \(v\) pass through some vertices in \(S\).

Usage

is_separator(graph, candidate)

Arguments

graph

The input graph. It may be directed, but edge directions are ignored.

candidate

A numeric vector giving the vertex IDs of the candidate separator.

Value

A Logical, whether the supplied vertex set is a (minimal) vertex separator or not. lists all vertex separator of minimum size.

Related documentation in the C library

is_separator(), vcount()

See also

Other flow: dominator_tree(), edge_connectivity(), is_min_separator(), max_flow(), min_cut(), min_separators(), min_st_separators(), st_cuts(), st_min_cuts(), vertex_connectivity()

Examples

ring <- make_ring(4)
min_st_separators(ring)
#> [[1]]
#> ── <vertex sequence> 2/4 · from f8b1e8b ────────────────────────────────────────
#> [1] 2 4
#> 
#> [[2]]
#> ── <vertex sequence> 2/4 · from f8b1e8b ────────────────────────────────────────
#> [1] 1 3
#> 
is_separator(ring, 1)
#> [1] FALSE
is_separator(ring, c(1, 3))
#> [1] TRUE
is_separator(ring, c(2, 4))
#> [1] TRUE
is_separator(ring, c(2, 3))
#> [1] FALSE