|
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.
Returns true if and only if the undirected
graph G is a connected graph.
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.
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.
Returns true if and only if the graph G is connected and has at least
one cut vertex.
Returns true if and only if the graph G is biconnected.
The graph G must be undirected.
The set of cut vertices for the connected undirected graph G
(as a set of vertices).
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.
Returns true if and only if
the multidigraph G is strongly connected.
Returns true if and only if the multidigraph G is weakly
connected.
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.
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.
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.
Returns true if and only if G is triconnected.
The graph G must be undirected.
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.
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 .
We refer the reader to Subsection Maximum Matching in Bipartite Graphs
for information about the maximum matching algorithm.
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".
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.
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∈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".
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".
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".
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∈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".
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".
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".
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 > ]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|