EdgeConnectivity - Maple Help

GraphTheory

 EdgeConnectivity
 compute edge connectivity of a graph
 VertexConnectivity
 compute vertex connectivity of a graph

 Calling Sequence EdgeConnectivity(G) VertexConnectivity(G)

Parameters

 G - graph

Options

 • output = value or ['value', 'cutset']
 Specify what the command returns: value is the connectivity value as a positive integer. cutset is a set of edges or vertices of size value that can be removed to disconnect the graph.

Description

 • EdgeConnectivity returns the edge connectivity of a graph, that is the minimum number of edges whose removal disconnects the graph. The output option can be used to return a cut-set of minimal size. This set is typically not unique. The IsCutSet command can be used to test whether a set of edges is a cut-set.
 • VertexConnectivity returns the vertex connectivity of a graph, that is the minimum number of vertices whose removal disconnects the graph. The output option can be used to return a minimal set of vertices tha can be used to disconnnect the graph. Again, this set is not unique.
 • In the general case, both these commands call MaxFlow iteratively over pairs of vertices in the graph (or a related graph) and they call MinCut to compute the cut-set.
 • By an elementary theorem of graph theory, the vertex connectivity of a graph is less than or equal to the edge connectivity, which is less than or equal to the minimum degree.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $G≔\mathrm{Graph}\left(\left\{\left\{1,2\right\},\left\{1,3\right\},\left\{1,4\right\},\left\{2,3\right\},\left\{3,4\right\},\left\{4,5\right\},\left\{4,6\right\},\left\{5,6\right\}\right\}\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected graph with 6 vertices and 8 edge\left(s\right)}}$ (1)
 > $\mathrm{DrawGraph}\left(G\right)$
 > $\mathrm{MinimumDegree}\left(G\right)$
 ${2}$ (2)
 > $\mathrm{EdgeConnectivity}\left(G\right)$
 ${2}$ (3)
 > $\mathrm{VertexConnectivity}\left(G,\mathrm{output}=\left['\mathrm{value}','\mathrm{cutset}'\right]\right)$
 ${1}{,}\left\{{4}\right\}$ (4)

When the vertex connectivity value is 1, then the disconnection point is an articulation point and was computed with the command ArticulationPoints.

 > $\mathrm{ArticulationPoints}\left(G\right)$
 $\left[{4}\right]$ (5)

The Peterson Graph is a good example where both connectivity values are equal to the minimum degree.

 > $P≔\mathrm{SpecialGraphs}:-\mathrm{PetersenGraph}\left(\right)$
 ${P}{≔}{\mathrm{Graph 2: an undirected graph with 10 vertices and 15 edge\left(s\right)}}$ (6)
 > $\mathrm{DrawGraph}\left(P\right)$
 > $\mathrm{MinimumDegree}\left(P\right)$
 ${3}$ (7)
 > $\mathrm{vc},\mathrm{vcut}≔\mathrm{VertexConnectivity}\left(P,\mathrm{output}=\left['\mathrm{value}','\mathrm{cutset}'\right]\right)$
 ${\mathrm{vc}}{,}{\mathrm{vcut}}{≔}{3}{,}\left\{{2}{,}{4}{,}{7}\right\}$ (8)
 > $\mathrm{DrawGraph}\left(\mathrm{DeleteVertex}\left(P,\mathrm{vcut}\right)\right)$
 > $\mathrm{ec},\mathrm{ecut}≔\mathrm{EdgeConnectivity}\left(P,\mathrm{output}=\left['\mathrm{value}','\mathrm{cutset}'\right]\right)$
 ${\mathrm{ec}}{,}{\mathrm{ecut}}{≔}{3}{,}\left\{\left\{{1}{,}{2}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{2}{,}{9}\right\}\right\}$ (9)
 > $\mathrm{IsCutSet}\left(P,\mathrm{ecut}\right)$
 ${\mathrm{true}}$ (10)
 > $\mathrm{DrawGraph}\left(\mathrm{DeleteEdge}\left(P,\mathrm{ecut}\right)\right)$
 > $\mathrm{ec}=\mathrm{vc}$
 ${3}{=}{3}$ (11)

Compatibility

 • The GraphTheory[EdgeConnectivity] and GraphTheory[VertexConnectivity] commands were updated in Maple 2024.
 • The output option was introduced in Maple 2024.