Returns true if and only if the graph G is connected.
The connected components of the 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 graph 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 set of cut vertices for the connected graph G (a set of vertices).
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.
Returns true if and only if the digraph G is strongly connected.
Returns true if and only if the digraph G is weakly connected.
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.
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.
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.
Returns true if and only if the graph G is triconnected.
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.
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.
> 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
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 H160E4 in this same chapter actually is an implementation in Magma code of the maximum matching algorithm.
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".
> 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} ]
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.
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".
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".
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".
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".
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".
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".
> 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