Connectedness

Contents

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 [HT73] has been implemented with corrections of our own and from C. Gutwenger and P. Mutzel [GM01]. 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 [HT73] and [GM01]. 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 V1 and V2. That is, for any vertices u∈V1 and v∈V2, 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, V1 + {a, b} and V2 + {a, b}. Let G1 and G2 be the subgraphs of G induced by V1 + {a, b} and V2 + {a, b} respectively. We say that the algorithm splits G into G1 and G2.

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

More generally, if G1, ..., Gm are the split components of a graph G, one can make the Gi triconnected by adding the edges (a, b) to them for all the separation pairs (a, b) of G with a, b∈Gi 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 Graph_Triconnectivity (H162E12)

> 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 ]
]
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

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 H164E4 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 Graph_MaxMatching (H162E13)

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} ]

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 [Eve79].

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∈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∈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∈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∈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 Graph_Connectivity (H162E14)

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
[Next][Prev] [Right] [Left] [Up] [Index] [Root]


Version: V2.29 of Fri Nov 28 15:14:01 AEDT 2025
Search: