# 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](../../references.md#cite-hoptar73)] has been implemented with corrections of our own and from C. Gutwenger and P. Mutzel [[Gutwenger and Mutzel, 2001](../../references.md#cite-gutmut01)]. 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](../../references.md#cite-hoptar73)] and  [[Gutwenger and Mutzel, 2001](../../references.md#cite-gutmut01)]. 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)`

```magma
> 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`.

```magma
> 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](../Networks/flow.md#multigraph-sec-flow) in Chapter [Multigraphs](../Multigraphs/index-multigraphs.md#multigraph). Example MultiGraph-ex:maxmat in this same chapter actually is an implementation in Magma code of the maximum matching algorithm.

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

```magma
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](sparse-graphs.md#graph-sec-sparse)).

```magma
> 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](#graph-subsec-maxmatching)) 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](../Networks/flow.md#multigraph-sec-flow) in Chapter [Multigraphs](../Multigraphs/index-multigraphs.md#multigraph). For details on how vertex and edge connectivity are implemented, see [[Even, 1979](../../references.md#cite-even)].

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

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

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

```magma
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`

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

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

```magma
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`

```magma
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](sparse-graphs.md#graph-sec-sparse)).

```magma
> 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

```