FindVertexCut
finds a smallest vertex cut of the graph g.
FindVertexCut[g,s,t]
finds a smallest s-t vertex cut of the graph g.
FindVertexCut[{vw,…},…]
uses rules vw to specify the graph g.
Details
- A vertex cut is also known as vertex cut set or separating set.
- A vertex cut of a graph g is a list of vertices whose deletion from g disconnects g.
- The s-t vertex cut is a list of vertices whose deletion from g disconnects g, with s and t in two different connected components.
- For a disconnected graph, FindVertexCut will return an empty list {}.
Examples
open all close allBasic Examples (2)
Scope (6)
FindVertexCut works with undirected graphs:
FindVertexCut[[image]]FindVertexCut[[image]]FindVertexCut[[image]]FindVertexCut[[image]]Find a smallest s-t vertex cut:
FindVertexCut[[image], 1, 4]Use rules to specify the graph:
FindVertexCut[{1 -> 2, 2 -> 3, 4 -> 3, 6 -> 1, 6 -> 5, 5 -> 2, 5 -> 4, 2 -> 6, 3 -> 5}]Properties & Relations (1)
Use VertexConnectivity to obtain the size of the vertex cut:
g = [image];FindVertexCut[g]VertexConnectivity[g]Text
Wolfram Research (2012), FindVertexCut, Wolfram Language function, https://reference.wolfram.com/language/ref/FindVertexCut.html (updated 2015).
CMS
Wolfram Language. 2012. "FindVertexCut." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindVertexCut.html.
APA
Wolfram Language. (2012). FindVertexCut. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindVertexCut.html