Subsections

• Connectedness, Paths and Circuits in a Graph
• Connectedness, Paths and Circuits in a Digraph

Biconnected components of G. These are returned as a sequence of subgraphs of G, each with the vertex set of G and the edges of a biconnected component of G.

The subgraph corresponding to the connected component of the graph G containing vertex u.

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 set of cut vertices for the graph G (a set of vertices).

The length of the longest path in the graph G. If G is not connected, the value -1 is returned.

A sequence of vertices defining a longest path if the graph G is connected, or the empty sequence if G is not connected.

Given two vertices u and v belonging to a graph G, return the length of a shortest path from u to v. If u and v lie in different components, the value -1 is returned.

Given a vertex u belonging to the graph G, return the partition P_0 union P_1 union ... union P_d of the vertex set of G, where P_i is the set of vertices lying at distance i from vertex u. The partition is returned as a sequence of sets. Any vertices not connected to u are treated as being at infinite distance from u and are returned as the last set of the partition.

IsEquitable(G, P) : GrphUnd, { { RngIntElt } } -> BoolElt

Given a partition P of the vertex set V(G) of the graph G, return the value true if P is an equitable partition.

EquitablePartition(P, G) : { { RngIntElt } }, GrphUnd -> { { GrphVert } }

Given a partition P of the vertex set V(G) of the graph G, return the coarsest partition of V(G) that refines P and which is equitable.

Let G be a graph in which the degree of every vertex is even, i.e. G is an eulerian graph. This function returns a sequence of vertices of G that form an eulerian circuit.

Given vertices u and v belonging to the graph G, return a sequence of vertices u = v_1, v_2, ..., v_n = v such that the sequence of edges v_1v_2, v_2v_3, ... v_(n - 1)v_n forms a shortest path joining u and v. If u and v lie in different components of G, the empty sequence is returned.

The girth of graph G, i.e. the length of a shortest cycle.

A cycle of shortest length in the graph G.

Return true if and only if vertices u and v of a graph G are in the same component of G.

Triconnected components of G. These are returned in the form of a partition of the vertex set of G.

True if the digraph G is strongly connected, false otherwise.

True if the digraph G is weakly connected, false otherwise.

Given a vertex u belonging to the digraph G, return the partition P_0 union P_1 union ... union P_d of the vertex set of G, where P_i is the set of vertices lying at distance i from vertex u. The partition is returned as a sequence of sets. Any vertices not connected to u are treated as being at infinite distance from u and are returned as the last set of the partition.