Connectedness, Paths and Circuits

Subsections

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

Connectedness in a Graph

IsConnected(G) : GrphUnd -> BoolElt

Returns true if the graph G is a connected graph, otherwise false.

Components(G) : Grph -> [ { GrphVert } ]

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

Component(u) : GrphVert -> Grph

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

IsSeparable(G) : GrphUnd -> BoolElt

True if and only if G is connected and has no cut vertices.

IsBiconnected(G) : GrphUnd -> BoolElt

True if and only if G is biconnected.

CutVertices(G) : Grph -> { GrphVert }

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

Bicomponents(G) : GrphUnd -> [GrphUnd]

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.

[Future release] Tricomponents(G) : GrphUnd -> { { GrphVert } }

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

Paths and Circuits in a Graph

Diameter(G) : Grph -> RngIntElt

The length of the longest path in the graph G. If G is not connected, the value -1 is returned. To see how the automorphism group of Gis computed see Subsection Graph Colouring and Automorphism Group.

DiameterPath(G) : Grph -> [GrphVert]

A sequence of vertices defining a longest path if the graph G is connected, or the empty sequence if G is not connected. To see how the automorphism group of Gis computed see Subsection Graph Colouring and Automorphism Group.

Distance(u, v) : GrphVert, GrphVert -> RngIntElt

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.

DistancePartition(u) : GrphVert -> [ { GrphVert } ]

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, { { GrphVert } } -> BoolElt

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) : { { GrphVert } }, GrphUnd -> { { GrphVert } }

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.

[Future release] EulerianCircuit(G) : GrphUnd -> [GrphVert]

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.

Geodesic(u, v) : GrphVert, GrphVert -> [GrphVert]

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.

Girth(G) : GrphUnd -> RngIntElt

The girth of graph G, i.e. the length of a shortest cycle. To see how the automorphism group of G is computed see Subsection Graph Colouring and Automorphism Group.

GirthCycle(G) : GrphUnd -> [GrphVert]

A cycle of shortest length in the graph G. To see how the automorphism group of G is computed see Subsection Graph Colouring and Automorphism Group.

Reachable(u, v) : GrphVert, GrphVert -> BoolElt

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

Connectedness, Paths and Circuits in a Digraph

Component(u) : GrphVert -> Grph

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

IsStronglyConnected(G) : GrphDir -> BoolElt

Returns true if the digraph G is strongly connected, false otherwise.

IsWeaklyConnected(G) : GrphDir -> BoolElt

Returns true if the digraph G is weakly connected, false otherwise.

StronglyConnectedComponents(G) : GrphUnd -> [GrphDir]

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.

DistancePartition(u) : GrphVert -> [ { GrphVert } ]

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.