Connectedness#

All the functions relating to connectivity issues are the same for simple graphs and multigraphs. See Section Connectedness in a 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 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 for information about the maximum matching algorithm.

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

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 for details about the algorithms underlying the functions listed below. These functions apply to both undirected and directed graphs.

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

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

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#

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

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

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#

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.

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

Run in calculator