# Connectedness

All the functions relating to connectivity issues are the same for simple graphs and multigraphs. See Section [Connectedness in a Graph](../Graphs/connectedness-path-circuit.md#graph-subsec-connect-graph) and its subsections for specific details about the algorithms underlying these functions.

## Connectedness in a Multigraph

### `IsConnected(G): GrphMultUnd -> BoolElt`

Returns `true` if and only if the undirected graph $G$ is a connected graph.

### `Components(G): GrphMultUnd -> [ { GrphVert } ]`

The connected components of the undirected graph $G$. These are returned in the form of a sequence of subsets of the vertex-set of $G$.

### `Component(u): GrphVert -> GrphMult`

The subgraph corresponding to the connected component of the multigraph $G$ containing vertex $u$. The support and vertex/edge decorations are *not* retained in the resulting (structural) subgraph.

### `IsSeparable(G): GrphMultUnd -> BoolElt`

Returns `true` if and only if the graph $G$ is connected and has at least one cut vertex.

### `IsBiconnected(G): GrphMultUnd -> BoolElt`

Returns `true` if and only if the graph $G$ is biconnected. The graph $G$ must be undirected.

### `CutVertices(G): GrphMultUnd -> { GrphVert}`

The set of cut vertices for the connected undirected graph $G$ (as a set of vertices).

### `Bicomponents(G): GrphMultUnd -> [ { GrphVert } ]`

The biconnected components of the undirected 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 Multidigraph

### `IsStronglyConnected(G): GrphMultDir -> BoolElt`

Returns `true` if and only if the multidigraph $G$ is strongly connected.

### `IsWeaklyConnected(G): GrphMultDir -> BoolElt`

Returns `true` if and only if the multidigraph $G$ is weakly connected.

### `StronglyConnectedComponents(G): GrphMultDir -> [ { GrphVert} ]`

The strongly connected components of the multidigraph $G$. These are returned in the form of a sequence of subsets of the vertex-set of $G$.

### `Component(u): GrphVert -> GrphMult`

The subgraph corresponding to the connected component of the multidigraph $G$ containing vertex $u$. The support and vertex/edge decorations are *not* retained in the resulting (structural) subgraph.

## Triconnectivity for Multigraphs

We refer the reader to Subsection [Graph Triconnectivity](../Graphs/connectedness-path-circuit.md#graph-subsec-triconn) of the graphs chapter for details about the triconnectivity algorithm implemented here, and especially about the meaning of the `Splitcomponents` function. The triconnectivity algorithm applies to undirected graphs only.

### `IsTriconnected(G): GrphMultUnd -> BoolElt`

Returns `true` if and only if $G$ is triconnected. The graph $G$ must be undirected.

### `Splitcomponents(G): GrphMultUnd -> [ { GrphVert} ], [ [ GrphVert ]]`

The split components of the undirected 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 as sequences of one or two vertices respectively.

### `SeparationVertices(G): GrphMultUnd -> [ [ GrphVert ]], [ { GrphVert} ]`

The cut vertices and/or the separation pairs of the undirected graph $G$ as a sequence of sequences of one and/or two vertices respectively. The graph may be disconnected. The second return value returns the split components of $G$ .

## Maximum Matching in Bipartite Multigraphs

We refer the reader to Subsection [Maximum Matching in Bipartite Graphs](../Graphs/connectedness-path-circuit.md#graph-subsec-maxmatching) for information about the maximum matching algorithm.

### `MaximumMatching(G : parameters): GrphMultUnd -> [ { GrphEdge rbrace ]`

```magma
Al: MonStg                    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"`.

## General Vertex and Edge Connectivity in Multigraphs and Multidigraphs

See Subsection [General Vertex and Edge Connectivity in Graphs and Digraphs](../Graphs/connectedness-path-circuit.md#graph-subsec-gen-connect) for details about the algorithms underlying the functions listed below. These functions apply to both undirected and directed graphs.

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

```magma
Al: MonStg                    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 : parameters): GrphMult -> RngIntElt, [ GrphVert ]`

```magma
Al: MonStg                    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 : parameters): GrphMult, RngIntElt -> BoolElt`

```magma
Al: MonStg                    Default: "PushRelabel"
```

Returns `true` if the vertex connectivity of the graph $G$ 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 : parameters): GrphMult -> [ GrphEdge ]`

```magma
Al: MonStg                    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 : parameters): GrphMult -> RngIntElt, [ GrphEdge ]`

```magma
Al: MonStg                    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 : parameters): GrphMult, RngIntElt -> BoolElt`

```magma
Al: MonStg                    Default: "PushRelabel"
```

Returns `true` if the edge connectivity of the graph $G$ 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: GrphMult Conn (ex-e96180)`

We demonstrate that the connectivity functions deal properly with multiple edges.

```magma
> G := MultiGraph< 3 | < 1, {2, 3} >, < 1, {2, 3} >, < 2, {2, 3} > >;
> G;
Multigraph
Vertex  Neighbours

1       3 2 3 2 ;
2       3 2 2 1 1 ;
3       2 1 1 ;

> EdgeConnectivity(G);
3
> EdgeSeparator(G);
[ < {3, 2}, 11 >, < {1, 2}, 5 >, < {1, 2}, 1 > ]

```