Connectedness#

Connectedness in a Graph#

IsConnected(G): GrphUnd -> BoolElt#: Returns true if and only if the graph \(G\) is connected.

Components(G): GrphUnd -> [ { GrphVert} ]#: The connected components of the graph \(G\). These are returned in the form of a sequence of subsets of the vertex-set of \(G\).

Component(u): GrphVert -> Grph#: The subgraph corresponding to the connected component of the graph \(G\) containing vertex \(u\). The support and vertex/edge decorations are not retained in the resulting (structural) subgraph.

IsSeparable(G): GrphUnd -> BoolElt#: Returns true if and only if the graph \(G\) is connected and has at least one cut vertex.

IsBiconnected(G): GrphUnd -> BoolElt#: Returns true if and only if the graph \(G\) is biconnected.

CutVertices(G): Grph -> { GrphVert}#: The set of cut vertices for the connected graph \(G\) (a set of vertices).

Bicomponents(G): GrphUnd -> [GrphUnd]#: The biconnected components of the graph \(G\). These are returned in the form of a sequence of subsets of the vertex-set of \(G\). The graph may be disconnected.

Connectedness in a Digraph#

IsStronglyConnected(G): GrphDir -> BoolElt#: Returns true if and only if the digraph \(G\) is strongly connected.

IsWeaklyConnected(G): GrphDir -> BoolElt#: Returns true if and only if the digraph \(G\) is weakly connected.

StronglyConnectedComponents(G): GrphDir -> [ { GrphVert} ]#: The strongly connected components of the digraph \(G\). These are returned in the form of a sequence of subsets of the vertex-set of \(G\).

Component(u): GrphVert -> Grph#: The subgraph corresponding to the connected component of the digraph \(G\) containing vertex \(u\). The support and vertex/edge decorations are not retained in the resulting (structural) subgraph.

Graph Triconnectivity#

The linear-time triconnectivity algorithm by Hopcroft and Tarjan [Hopcroft and Tarjan, 1973] has been implemented with corrections of our own and from C. Gutwenger and P. Mutzel [Gutwenger and Mutzel, 2001]. This algorithm requires that the graph has a sparse representation. The input graph may be disconnected or have cut vertices.

The algorithm completely splits the graph into components that can later be reconstructed as triconnected graphs: It is our belief that the word “tricomponents” is misused in all the papers discussing Hopcroft and Tarjan’s algorithm, including [Hopcroft and Tarjan, 1973] and [Gutwenger and Mutzel, 2001]. Let us clarify this point.

Assume that \(G\) is a biconnected but not triconnected graph with vertex-set \(V\) and with one separation pair \((a, b)\) which splits \(V - \{a, b\}\) into \(V_1\) and \(V_2\). That is, for any vertices \(u\in V_1\) and \(v\in V_2\), every path from \(u\) to \(v\) in \(G\) contains at least one of \(a\) or \(b\).

Now, the algorithm will correctly find the separation pair \((a, b)\) and return the two subsets of \(V\), \(V_1 + \{a, b\}\) and \(V_2 + \{a, b\}\). Let \(G_1\) and \(G_2\) be the subgraphs of \(G\) induced by \(V_1 + \{a, b\}\) and \(V_2 + \{a, b\}\) respectively. We say that the algorithm splits \(G\) into \(G_1\) and \(G_2\).

But \(G_1\) and \(G_2\) are triconnected if and only if there is an edge \((a, b)\) in \(G\). We call \(G_1\) and \(G_2\) the split components of \(G\).

More generally, if \(G_1,\ldots, G_m\) are the split components of a graph \(G\), one can make the \(G_i\) triconnected by adding the edges \((a, b)\) to them for all the separation pairs \((a, b)\) of \(G\) with \(a\), \(b\in G_i\) for some \(i\).

The algorithm finds all the cut vertices and/or the separation pairs of a graph, unless only the boolean test is applied. When this is the case the algorithm stops as soon as a cut vertex or separation pair is found.

The triconnectivity algorithm only applies to undirected graphs.

IsTriconnected(G): GrphUnd -> BoolElt#: Returns true if and only if the graph \(G\) is triconnected.

Splitcomponents(G): GrphUnd -> [ { GrphVert } ], [ [ GrphVert ]]#: The split components of the graph \(G\). These are returned in the form of a sequence of subsets of the vertex-set of \(G\). The graph may be disconnected. The second return value returns the cut vertices and the separation pairs.

SeparationVertices(G): GrphUnd -> [ [ GrphVert ]], [ { GrphVert} ]#: The cut vertices and/or the separation pairs of the graph \(G\) as a sequence of vertices or pairs of vertices of \(G\). The graph may be disconnected. The second return value returns \(G\)’s split components.

Example: Triconnectivity (ex-1455c3)#

> G := Graph< 11 |
> {1, 3}, {1, 4}, {1, 7}, {1, 11}, {1, 2},
> {2, 4}, {2, 3},
> {3, 4},
> {4, 7}, {4, 11}, {4, 7}, {4, 5},
> {5, 10}, {5, 9}, {5, 8}, {5, 6},
> {6, 8}, {6, 7},
> {7, 8},
> {9, 11}, {9, 10},
> {10, 11}: SparseRep := true >;
> TS, PS := Splitcomponents(G);
> TS;
[
  { 5, 6, 7, 8 },
  { 5, 9, 10, 11 },
  { 1, 4, 5, 7, 11 },
  { 1, 4 },
  { 1, 2, 3, 4 }
]
> PS;
[
  [ 5, 7 ],
  [ 5, 11 ],
  [ 1, 4 ]
]

Run in calculator

Let G1 be the subgraph induced by TS[1]. We will verify that it is not triconnected and we make it triconnected by adding the edge [5, 7], since [5, 7] is a separation pair of G whose vertices belong to G1.

> G1 := sub< G | TS[1] >;
> IsTriconnected(G1);
false
> AddEdge(~G1, Index(VertexSet(G1)!VertexSet(G)!5),
>       Index(VertexSet(G1)!VertexSet(G)!7));
> IsTriconnected(G1);
true

Run in calculator

Maximum Matching in Bipartite Graphs#

The maximum matching algorithm is a flow-based algorithm. We have implemented two maximum flow algorithms, the Dinic algorithm, and a push-relabel algorithm. The latter is almost always the most efficient, it may be outperformed by Dinic only in the case of very sparse graphs. For a full discussion of these algorithms, the reader is referred to Section Maximum Flow and Minimum Cut in Chapter Multigraphs. Example MultiGraph-ex:maxmat in this same chapter actually is an implementation in Magma code of the maximum matching algorithm.

MaximumMatching(G): GrphUnd -> [ { GrphEdge} ]#

Al: MonStgElt                    Default: "PushRelabel"

A maximum matching in the bipartite graph \(G\). The matching is returned as a sequence of edges of G. The parameter Al enables the user to select the algorithm which is to be used: Al := "PushRelabel" or Al := "Dinic".

Example: Max Matching (ex-251f2b)#

We begin by creating a random bipartite graph. The matching algorithm is flow-based and is one of the algorithms which deals with graphs as adjacency lists. For this reason we might as well create the graph with a sparse representation (see Section Graphs with a Sparse Representation).

> n := 5;
> m := 7;
> d := 3;
> G := EmptyGraph(n);
> H := EmptyGraph(m);
> G := G join H;
> for u in [1..n] do
>     t := Random(0, d);
>     for tt in [1..t] do
>         v := Random(n+1, n+m);
>         AddEdge(~G, u, v);
>     end for;
> end for;
> G := Graph< Order(G) | G : SparseRep := true >;
>
> IsBipartite(G);
true
> Bipartition(G);
[
  { 1, 12, 2, 3, 4, 5, 7 },
  { 11, 6, 8, 9, 10 }
]
> MaximumMatching(G);
[ {1, 11}, {4, 10}, {2, 9}, {5, 8}, {3, 6} ]

Run in calculator

General Vertex and Edge Connectivity in Graphs and Digraphs#

As for the maximum matching algorithm (Subsection Maximum Matching in Bipartite Graphs) the vertex and edge connectivity algorithms are flow-based algorithms. We have implemented two flow algorithms, Dinic and a push relabel method. In general Dinic outperforms the push relabel method only in the case of very sparse graphs. This is particularly visible when computing the edge connectivity of a graph. For full details on those flow algorithms, refer to Section Maximum Flow and Minimum Cut in Chapter Multigraphs. For details on how vertex and edge connectivity are implemented, see [Even, 1979].

The general connectivity algorithms apply to both undirected and directed graphs.

VertexSeparator(G): Grph -> [ GrphVert ]#

Al: MonStgElt                    Default: "PushRelabel"

If \(G\) is an undirected graph, a vertex separator for \(G\) is a smallest set of vertices \(S\) such that for any \(u\), \(v\in V(G)\), every path connecting \(u\) and \(v\) passes through at least one vertex of \(S\).

If \(G\) is a directed graph, a vertex separator for \(G\) is a smallest set of vertices \(S\) such that for any \(u\), \(v\in V(G)\), every directed path from \(u\) to \(v\) passes through at least one vertex of \(S\).

VertexSeparator returns the vertex separator of \(G\) as a sequence of vertices of \(G\). The parameter Al enables the user to select the algorithm which is to be used: Al := "PushRelabel" or Al := "Dinic".

VertexConnectivity(G): Grph -> RngIntElt, [ GrphVert ]#

Al: MonStgElt                    Default: "PushRelabel"

Returns the vertex connectivity of the graph \(G\), the size of a minimum vertex separator of \(G\). Also returns a vertex separator for \(G\) as the second value. The parameter Al enables the user to select the algorithm which is to be used: Al := "PushRelabel" or Al := "Dinic".

IsKVertexConnected(G, k): Grph, RngIntElt -> BoolElt#

Al: MonStgElt                    Default: "PushRelabel"

Returns true if the graph \(G\)’s vertex connectivity is at least \(k\), false otherwise. The parameter Al enables the user to select the algorithm which is to be used: Al := "PushRelabel" or Al := "Dinic".

EdgeSeparator(G): Grph -> [ GrphEdge ]#

Al: MonStgElt                    Default: "PushRelabel"

If \(G\) is an undirected graph, an edge separator for \(G\) is a smallest set of edges \(T\) such that for any \(u\), \(v\in V(G)\), every path connecting \(u\) and \(v\) passes through at least one edge of \(T\).

If \(G\) is a directed graph, an edge separator for \(G\) is a smallest set of edges \(T\) such that for any \(u\), \(v\in V(G)\), every directed path from \(u\) to \(v\) passes through at least one edge of \(T\).

EdgeSeparator returns the edge separator of \(G\) as a sequence of edges of \(G\). The parameter Al enables the user to select the algorithm which is to be used: Al := "PushRelabel" or Al := "Dinic".

EdgeConnectivity(G): Grph -> RngIntElt, [ GrphEdge ]#

Al: MonStgElt                    Default: "PushRelabel"

Returns the edge connectivity of the graph \(G\), the size of a minimum edge separator of \(G\). Also returns as the second value an edge separator for \(G\). The parameter Al enables the user to select the algorithm which is to be used: Al := "PushRelabel" or Al := "Dinic".

IsKEdgeConnected(G, k): Grph, RngIntElt -> BoolElt#

Al: MonStgElt                    Default: "PushRelabel"

Returns true if the graph \(G\)’s edge connectivity is at least \(k\), false otherwise. The parameter Al enables the user to select the algorithm which is to be used: Al := "PushRelabel" or Al := "Dinic".

Example: Connectivity (ex-c02f9d)#

We compute the vertex and edge connectivity for a small undirected graph and we perform a few checks. The connectivity algorithm is one of the algorithms which deals with graphs as adjacency lists. For this reason we might as well create the graph with a sparse representation (see Section Graphs with a Sparse Representation).

> G := Graph< 4 | {1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}
> : SparseRep := true >;
> IsConnected(G);
true
>
> vc := VertexConnectivity(G);
> S := VertexSeparator(G);
> vc;
2
> S;
[ 3, 2 ]
>
> H := G;
> vs := [ Integers() | Index(x) : x in S ];
> RemoveVertices(~H, vs);
> IsConnected(H);
false
> for k in [0..vc] do
>     IsKVertexConnected(G, k);
> end for;
true
true
true
> for k in [vc+1..Order(G)-1] do
>     IsKVertexConnected(G, k);
> end for;
false
>
>
>
> ec := EdgeConnectivity(G);
> T :=  EdgeSeparator(G);
> ec;
2
> T;
[ {1, 2}, {1, 3} ]
>
> H := G;
> M := [ { Index(e[1]), Index(e[2]) }
> where e := SetToSequence(EndVertices(e)) : e in T ];
> RemoveEdges(~H, M);
> IsConnected(H);
false
> for k in [0..ec] do
>     IsKEdgeConnected(G, k);
> end for;
true
true
true
> for k in [ec+1..Order(G)-1] do
>     IsKEdgeConnected(G, k);
> end for;
false

Run in calculator