6 Properties of digraphs

6.1 Edge properties

6.1-1 DigraphHasLoops

6.1-2 IsAntisymmetricDigraph

6.1-3 IsBipartiteDigraph

6.1-4 IsCompleteBipartiteDigraph

6.1-5 IsCompleteDigraph

6.1-6 IsEmptyDigraph

6.1-7 IsFunctionalDigraph

6.1-8 IsMultiDigraph

6.1-9 IsReflexiveDigraph

6.1-10 IsSymmetricDigraph

6.1-11 IsTournament

6.1-12 IsTransitiveDigraph

6.1-13 IsPreorderDigraph

6.1-14 IsPartialOrderDigraph

6.1-15 IsMeetSemilatticeDigraph

6.1-1 DigraphHasLoops

6.1-2 IsAntisymmetricDigraph

6.1-3 IsBipartiteDigraph

6.1-4 IsCompleteBipartiteDigraph

6.1-5 IsCompleteDigraph

6.1-6 IsEmptyDigraph

6.1-7 IsFunctionalDigraph

6.1-8 IsMultiDigraph

6.1-9 IsReflexiveDigraph

6.1-10 IsSymmetricDigraph

6.1-11 IsTournament

6.1-12 IsTransitiveDigraph

6.1-13 IsPreorderDigraph

6.1-14 IsPartialOrderDigraph

6.1-15 IsMeetSemilatticeDigraph

`‣ DigraphHasLoops` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

Returns `true`

if the digraph `digraph` has loops, and `false`

if it does not. A loop is an edge with equal source and range.

gap> gr := Digraph([[1, 2], [2]]); <digraph with 2 vertices, 3 edges> gap> DigraphEdges(gr); [ [ 1, 1 ], [ 1, 2 ], [ 2, 2 ] ] gap> DigraphHasLoops(gr); true gap> gr := Digraph([[2, 3], [1], [2]]); <digraph with 3 vertices, 4 edges> gap> DigraphEdges(gr); [ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 3, 2 ] ] gap> DigraphHasLoops(gr); false

`‣ IsAntisymmetricDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

This property is `true`

if the digraph `digraph` is antisymmetric, and `false`

if it is not.

A digraph is *antisymmetric* if whenever there is an edge with source `u`

and range `v`

, and an edge with source `v`

and range `u`

, then the vertices `u`

and `v`

are equal.

gap> gr1 := Digraph([[2], [1, 3], [2, 3]]); <digraph with 3 vertices, 5 edges> gap> IsAntisymmetricDigraph(gr1); false gap> DigraphEdges(gr1){[1, 2]}; [ [ 1, 2 ], [ 2, 1 ] ] gap> gr2 := Digraph([[1, 2], [3, 3], [1]]); <multidigraph with 3 vertices, 5 edges> gap> IsAntisymmetricDigraph(gr2); true gap> DigraphEdges(gr2); [ [ 1, 1 ], [ 1, 2 ], [ 2, 3 ], [ 2, 3 ], [ 3, 1 ] ]

`‣ IsBipartiteDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

This property is `true`

if the digraph `digraph` is bipartite, and `false`

if it is not. A digraph is bipartite if and only if the vertices of `digraph` can be partitioned into two non-empty sets such that the source and range of any edge of `digraph` lie in distinct sets. Equivalently, a digraph is bipartite if and only if it is 2-colorable; see `DigraphColouring`

(7.3-9).

See also `DigraphBicomponents`

(5.3-12).

gap> gr := ChainDigraph(4); <digraph with 4 vertices, 3 edges> gap> IsBipartiteDigraph(gr); true gap> gr := CycleDigraph(3); <digraph with 3 vertices, 3 edges> gap> IsBipartiteDigraph(gr); false

`‣ IsCompleteBipartiteDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

Returns `true`

if the digraph `digraph` is a complete bipartite digraph, and `false`

if it is not.

A digraph is a *complete bipartite digraph* if it is bipartite, see `IsBipartiteDigraph`

(6.1-3), and there exists a unique edge with source `i`

and range `j`

if and only if `i`

and `j`

lie in different bicomponents of `digraph`, see `DigraphBicomponents`

(5.3-12).

Equivalently, a bipartite digraph with bicomponents of size m and n is complete precisely when it has 2mn edges, none of which are multiple edges.

See also `CompleteBipartiteDigraph`

(3.5-3).

gap> gr := CycleDigraph(2); <digraph with 2 vertices, 2 edges> gap> IsCompleteBipartiteDigraph(gr); true gap> gr := CycleDigraph(4); <digraph with 4 vertices, 4 edges> gap> IsBipartiteDigraph(gr); true gap> IsCompleteBipartiteDigraph(gr); false

`‣ IsCompleteDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

Returns `true`

if the digraph `digraph` is complete, and `false`

if it is not.

A digraph is *complete* if it has no loops, and for all *distinct* vertices `i`

and `j`

, there is exactly one edge with source `i`

and range `j`

. Equivalently, a digraph with n vertices is complete precisely when it has n(n - 1) edges, no loops, and no multiple edges.

gap> gr := Digraph([[2, 3], [1, 3], [1, 2]]); <digraph with 3 vertices, 6 edges> gap> IsCompleteDigraph(gr); true gap> gr := Digraph([[2, 2], [1]]); <multidigraph with 2 vertices, 3 edges> gap> IsCompleteDigraph(gr); false

`‣ IsEmptyDigraph` ( digraph ) | ( property ) |

`‣ IsNullDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

Returns `true`

if the digraph `digraph` is empty, and `false`

if it is not. A digraph is *empty* if it has no edges.

`IsNullDigraph`

is a synonym for `IsEmptyDigraph`

.

gap> gr := Digraph([[], []]); <digraph with 2 vertices, 0 edges> gap> IsEmptyDigraph(gr); true gap> IsNullDigraph(gr); true gap> gr := Digraph([[], [1]]); <digraph with 2 vertices, 1 edge> gap> IsEmptyDigraph(gr); false gap> IsNullDigraph(gr); false

`‣ IsFunctionalDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

This property is `true`

if the digraph `digraph` is functional.

A digraph is *functional* if every vertex is the source of a unique edge.

gap> gr1 := Digraph([[3], [2], [2], [1], [6], [5]]); <digraph with 6 vertices, 6 edges> gap> IsFunctionalDigraph(gr1); true gap> gr2 := Digraph([[1, 2], [1]]); <digraph with 2 vertices, 3 edges> gap> IsFunctionalDigraph(gr2); false gap> gr3 := Digraph(3, [1, 2, 3], [2, 3, 1]); <digraph with 3 vertices, 3 edges> gap> IsFunctionalDigraph(gr3); true

`‣ IsMultiDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

A *multidigraph* is one that has at least two edges with equal source and range.

gap> gr := Digraph(["a", "b", "c"], ["a", "b", "b"], ["b", "c", "a"]); <digraph with 3 vertices, 3 edges> gap> IsMultiDigraph(gr); false gap> gr := DigraphFromDigraph6String("+Bug"); <digraph with 3 vertices, 6 edges> gap> IsDuplicateFree(DigraphEdges(gr)); true gap> IsMultiDigraph(gr); false gap> gr := Digraph([[1, 2, 3, 2], [2, 1], [3]]); <multidigraph with 3 vertices, 7 edges> gap> IsDuplicateFree(DigraphEdges(gr)); false gap> IsMultiDigraph(gr); true

`‣ IsReflexiveDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

This property is `true`

if the digraph `digraph` is reflexive, and `false`

if it is not. A digraph is *reflexive* if it has a loop at every vertex.

gap> gr := Digraph([[1, 2], [2]]); <digraph with 2 vertices, 3 edges> gap> IsReflexiveDigraph(gr); true gap> gr := Digraph([[3, 1], [4, 2], [3], [2, 1]]); <digraph with 4 vertices, 7 edges> gap> IsReflexiveDigraph(gr); false

`‣ IsSymmetricDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

This property is `true`

if the digraph `digraph` is symmetric, and `false`

if it is not.

A *symmetric digraph* is one where for each non-loop edge, having source `u`

and range `v`

, there is a corresponding edge with source `v`

and range `u`

. If there are `n`

edges with source `u`

and range `v`

, then there must be precisely `n`

edges with source `v`

and range `u`

. In other words, a symmetric digraph has a symmetric adjacency matrix `AdjacencyMatrix`

(5.2-1).

gap> gr1 := Digraph([[2], [1, 3], [2, 3]]); <digraph with 3 vertices, 5 edges> gap> IsSymmetricDigraph(gr1); true gap> adj1 := AdjacencyMatrix(gr1);; gap> Display(adj1); [ [ 0, 1, 0 ], [ 1, 0, 1 ], [ 0, 1, 1 ] ] gap> adj1 = TransposedMat(adj1); true gap> gr1 = DigraphReverse(gr1); true gap> gr2 := Digraph([[2, 3], [1, 3], [2, 3]]); <digraph with 3 vertices, 6 edges> gap> IsSymmetricDigraph(gr2); false gap> adj2 := AdjacencyMatrix(gr2);; gap> Display(adj2); [ [ 0, 1, 1 ], [ 1, 0, 1 ], [ 0, 1, 1 ] ] gap> adj2 = TransposedMat(adj2); false

`‣ IsTournament` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

This property is `true`

if the digraph `digraph` is a tournament, and `false`

if it is not.

A tournament is an orientation of a complete (undirected) graph. Specifically, a tournament is a digraph which has a unique directed edge (of some orientation) between any pair of distinct vertices, and no loops.

gap> gr := Digraph([[2, 3, 4], [3, 4], [4], []]); <digraph with 4 vertices, 6 edges> gap> IsTournament(gr); true gap> gr := Digraph([[2], [1], [3]]); <digraph with 3 vertices, 3 edges> gap> IsTournament(gr); false

`‣ IsTransitiveDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

This property is `true`

if the digraph `digraph` is transitive, and `false`

if it is not. A digraph is *transitive* if whenever `[ i, j ]`

and `[ j, k ]`

are edges of the digraph, then `[ i, k ]`

is also an edge of the digraph.

Let n be the number of vertices of an arbitrary digraph, and let m be the number of edges. For general digraphs, the methods used for this property use a version of the Floyd-Warshall algorithm, and have complexity O(n^3). However for digraphs which are topologically sortable [`DigraphTopologicalSort`

(5.1-7)], then methods with complexity O(m + n + m ⋅ n) will be used when appropriate.

gap> gr := Digraph([[1, 2], [3], [3]]); <digraph with 3 vertices, 4 edges> gap> IsTransitiveDigraph(gr); false gap> gr2 := Digraph([[1, 2, 3], [3], [3]]); <digraph with 3 vertices, 5 edges> gap> IsTransitiveDigraph(gr2); true gap> gr2 = DigraphTransitiveClosure(gr); true gap> gr3 := Digraph([[1, 2, 2, 3], [3, 3], [3]]); <multidigraph with 3 vertices, 7 edges> gap> IsTransitiveDigraph(gr3); true

`‣ IsPreorderDigraph` ( digraph ) | ( property ) |

`‣ IsQuasiorderDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

A digraph is a preorder digraph if and only if the digraph satisifies both `IsReflexiveDigraph`

(6.1-9) and `IsTransitiveDigraph`

(6.1-12). A preorder digraph (or quasiorder digraph) `digraph` corresponds to the preorder relation ≤ defined by x ≤ y if and only if `[x, y]`

is an edge of `digraph`.

gap> gr := Digraph([[1], [2, 3], [2, 3]]); <digraph with 3 vertices, 5 edges> gap> IsPreorderDigraph(gr); true gap> gr := Digraph([[1 .. 4], [1 .. 4], [1 .. 4], [1 .. 4]]); <digraph with 4 vertices, 16 edges> gap> IsPreorderDigraph(gr); true gap> gr := Digraph([[2], [3], [4], [5], [1]]); <digraph with 5 vertices, 5 edges> gap> IsPreorderDigraph(gr); false gap> gr := Digraph([[1], [1, 2], [2, 3]]); <digraph with 3 vertices, 5 edges> gap> IsPreorderDigraph(gr); false

`‣ IsPartialOrderDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

A digraph is a partial order digraph if and only if the digraph satisifies all of `IsReflexiveDigraph`

(6.1-9), `IsAntisymmetricDigraph`

(6.1-2) and `IsTransitiveDigraph`

(6.1-12). A partial order `digraph` corresponds to the partial order relation ≤ defined by x ≤ y if and only if `[x, y]`

is an edge of `digraph`.

gap> gr := Digraph([[1, 3], [2, 3], [3]]); <digraph with 3 vertices, 5 edges> gap> IsPartialOrderDigraph(gr); true gap> gr := CycleDigraph(5); <digraph with 5 vertices, 5 edges> gap> IsPartialOrderDigraph(gr); false gap> gr := Digraph([[1, 1], [1, 1, 2], [3], [3, 3, 4, 4]]); <multidigraph with 4 vertices, 10 edges> gap> IsPartialOrderDigraph(gr); true

`‣ IsMeetSemilatticeDigraph` ( digraph ) | ( property ) |

`‣ IsJoinSemilatticeDigraph` ( digraph ) | ( property ) |

`‣ IsLatticeDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

`IsMeetSemilatticeDigraph`

returns `true`

if the digraph `digraph` is a meet semilattice; `IsJoinSemilatticeDigraph`

returns `true`

if the digraph `digraph` is a join semilattice; and `IsLatticeDigraph`

returns `true`

if the digraph `digraph` is both a meet and a join semilattice.

For a partial order digraph `IsPartialOrderDigraph`

(6.1-14) the corresponding partial order is the relation ≤, defined by x ≤ y if and only if `[x, y]`

is an edge. A digraph is a *meet semilattice* if it is a partial order and every pair of vertices has a greatest lower bound (meet) with respect to the aforementioned relation. A *join semilattice* is a partial order where every pair of vertices has a least upper bound (join) with respect to the relation.

gap> gr := Digraph([[1, 3], [2, 3], [3]]); <digraph with 3 vertices, 5 edges> gap> IsMeetSemilatticeDigraph(gr); false gap> IsJoinSemilatticeDigraph(gr); true gap> IsLatticeDigraph(gr); false gap> gr := Digraph([[1], [2], [1 .. 3]]); <digraph with 3 vertices, 5 edges> gap> IsJoinSemilatticeDigraph(gr); false gap> IsMeetSemilatticeDigraph(gr); true gap> IsLatticeDigraph(gr); false gap> gr := Digraph([[1 .. 4], [2, 4], [3, 4], [4]]); <digraph with 4 vertices, 9 edges> gap> IsMeetSemilatticeDigraph(gr); true gap> IsJoinSemilatticeDigraph(gr); true gap> IsLatticeDigraph(gr); true gap> gr := Digraph([[1, 1, 1], [1, 1, 2, 2], > [1, 3, 3], [1, 2, 3, 3, 4]]); <multidigraph with 4 vertices, 15 edges> gap> IsMeetSemilatticeDigraph(gr); true gap> IsJoinSemilatticeDigraph(gr); true gap> IsLatticeDigraph(gr); true

`‣ IsInRegularDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

This property is `true`

if there is an integer `n`

such that for every vertex `v`

of digraph `digraph` there are exactly `n`

edges terminating in `v`

. See also `IsOutRegularDigraph`

(6.2-2) and `IsRegularDigraph`

(6.2-3).

gap> IsInRegularDigraph(CompleteDigraph(4)); true gap> IsInRegularDigraph(ChainDigraph(4)); false

`‣ IsOutRegularDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

This property is `true`

if there is an integer `n`

such that for every vertex `v`

of digraph `digraph` there are exactly `n`

edges starting at `v`

. See also `IsInRegularDigraph`

(6.2-1) and `IsRegularDigraph`

(6.2-3).

gap> IsOutRegularDigraph(CompleteDigraph(4)); true gap> IsOutRegularDigraph(ChainDigraph(4)); false

`‣ IsRegularDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

This property is `true`

if there is an integer `n`

such that for every vertex `v`

of digraph `digraph` there are exactly `n`

edges starting and terminating at `v`

. In other words, the property is `true`

if `digraph` is both in-regular and and out-regular. See also `IsInRegularDigraph`

(6.2-1) and `IsOutRegularDigraph`

(6.2-2).

gap> IsRegularDigraph(CompleteDigraph(4)); true gap> IsRegularDigraph(ChainDigraph(4)); false

`‣ IsDistanceRegularDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

If `digraph` is a connected symmetric graph, this property returns `true`

if for any two vertices `u`

and `v`

of `digraph` and any two integers `i`

and `j`

between `0`

and the diameter of `digraph`, the number of vertices at distance `i`

from `u`

and distance `j`

from `v`

depends only on `i`

, `j`

, and the distance between vertices `u`

and `v`

.

Alternatively, a distance regular graph is a graph for which there exist integers `b_i`

, `c_i`

, and `i`

such that for any two vertices `u`

, `v`

in `digraph` which are distance `i`

apart, there are exactly `b_i`

neighbors of `v`

which are at distance `i - 1`

away from `u`

, and `c_i`

neighbors of `v`

which are at distance `i + 1`

away from `u`

. This definition is used to check whether `digraph` is distance regular.

In the case where `digraph` is not symmetric or not connected, the property is `false`

.

gap> gr := DigraphSymmetricClosure(ChainDigraph(5));; gap> IsDistanceRegularDigraph(gr); false gap> gr := Digraph([[2, 3, 4], [1, 3, 4], [1, 2, 4], [1, 2, 3]]); <digraph with 4 vertices, 12 edges> gap> IsDistanceRegularDigraph(gr); true

`‣ IsAcyclicDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

This property is `true`

if the digraph `digraph` is acyclic, and `false`

if it is not. A digraph is *acyclic* if every directed cycle on the digraph is trivial. See section 1.1-1 for the definition of a directed cycle, and of a trivial directed cycle.

The method used in this operation has complexity O(m+n) where m is the number of edges (counting multiple edges as one) and n is the number of vertices in the digraph.

gap> Petersen := Graph(SymmetricGroup(5), [[1, 2]], OnSets, > function(x, y) > return IsEmpty(Intersection(x, y)); > end);; gap> gr := Digraph(Petersen); <digraph with 10 vertices, 30 edges> gap> IsAcyclicDigraph(gr); false gap> gr := DigraphFromDiSparse6String( > ".b_OGCIDBaPGkULEbQHCeRIdrHcuZMfRyDAbPhTi|zF"); <digraph with 35 vertices, 34 edges> gap> IsAcyclicDigraph(gr); true gap> IsAcyclicDigraph(ChainDigraph(10)); true gap> IsAcyclicDigraph(CycleDigraph(10)); false

`‣ IsChainDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

`IsChainDigraph`

returns `true`

if the digraph `digraph` is isomorphic to the chain digraph with the same number of vertices as `digraph`, and `false`

if it is not; see `ChainDigraph`

(3.5-1).

A digraph is a *chain* if and only if it is a directed tree, in which every vertex has out degree at most one; see `IsDirectedTree`

(6.3-7) and `OutDegrees`

(5.2-7).

gap> gr := Digraph([[1, 3], [2, 3], [3]]); <digraph with 3 vertices, 5 edges> gap> IsChainDigraph(gr); false gap> gr := ChainDigraph(5); <digraph with 5 vertices, 4 edges> gap> IsChainDigraph(gr); true gap> gr := DigraphReverse(gr); <digraph with 5 vertices, 4 edges> gap> IsChainDigraph(gr); true

`‣ IsConnectedDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

This property is `true`

if the digraph `digraph` is weakly connected and `false`

if it is not. A digraph `digraph` is *weakly connected* if it is possible to travel from any vertex to any other vertex by traversing edges in either direction (possibly against the orientation of some of them).

The method used in this function has complexity O(m) if the digraph's `DigraphSource`

(5.2-4) attribute is set, otherwise it has complexity O(m+n) (where m is the number of edges and n is the number of vertices of the digraph).

gap> gr := Digraph([[2], [3], []]);; gap> IsConnectedDigraph(gr); true gap> gr := Digraph([[1, 3], [4], [3], []]);; gap> IsConnectedDigraph(gr); false

`‣ IsBiconnectedDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

A connected digraph is *biconnected* if it is still connected (in the sense of `IsConnectedDigraph`

(6.3-3)) when any vertex is removed. `IsBiconnectedDigraph`

returns `true`

if the digraph `digraph` is biconnected, and `false`

if it is not. In particular, `IsBiconnectedDigraph`

returns `false`

if `digraph` is not connected.

Multiple edges and loops are ignored by this method.

The method used in this operation has complexity O(m+n) where m is the number of edges (counting multiple edges as one, and not counting loops) and n is the number of vertices in the digraph. See also `ArticulationPoints`

(5.3-13).

gap> IsBiconnectedDigraph(Digraph([[1, 3], [2, 3], [3]])); false gap> IsBiconnectedDigraph(CycleDigraph(5)); true gap> digraph := Digraph([[1, 1], [1, 1, 2], [3], [3, 3, 4, 4]]);; gap> IsBiconnectedDigraph(digraph); false

`‣ IsStronglyConnectedDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

This property is `true`

if the digraph `digraph` is strongly connected and `false`

if it is not.

A digraph `digraph` is *strongly connected* if there is a directed path from every vertex to every other vertex. See section 1.1-1 for the definition of a directed path.

The method used in this operation is based on Gabow's Algorithm [Gab00] and has complexity O(m+n), where m is the number of edges (counting multiple edges as one) and n is the number of vertices in the digraph.

gap> gr := CycleDigraph(250000); <digraph with 250000 vertices, 250000 edges> gap> IsStronglyConnectedDigraph(gr); true gap> gr := DigraphRemoveEdges(gr, [[250000, 1]]); <digraph with 250000 vertices, 249999 edges> gap> IsStronglyConnectedDigraph(gr); false

`‣ IsAperiodicDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

This property is `true`

if the digraph `digraph` is aperiodic, i.e. if its `DigraphPeriod`

(5.3-14) is equal to 1. Otherwise, the property is `false`

.

gap> gr := Digraph([[6], [1], [2], [3], [4, 4], [5]]); <multidigraph with 6 vertices, 7 edges> gap> IsAperiodicDigraph(gr); false gap> gr := Digraph([[2], [3, 5], [4], [5], [1, 2]]); <digraph with 5 vertices, 7 edges> gap> IsAperiodicDigraph(gr); true

`‣ IsDirectedTree` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

Returns `true`

if the digraph `digraph` is a directed tree, and `false`

if it is not.

A *directed tree* is an acyclic digraph with precisely 1 source, such that no two vertices share an out-neighbour. Note the empty digraph is not considered a directed tree as it has no source.

See also `DigraphSources`

(5.1-6).

gap> gr := Digraph([[], [2]]); <digraph with 2 vertices, 1 edge> gap> IsDirectedTree(gr); false gap> gr := Digraph([[3], [3], []]); <digraph with 3 vertices, 2 edges> gap> IsDirectedTree(gr); false gap> gr := Digraph([[2], [3], []]); <digraph with 3 vertices, 2 edges> gap> IsDirectedTree(gr); true gap> gr := Digraph([[2, 3], [6], [4, 5], [], [], []]); <digraph with 6 vertices, 5 edges> gap> IsDirectedTree(gr); true

`‣ IsUndirectedTree` ( digraph ) | ( property ) |

`‣ IsUndirectedForest` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

The property `IsUndirectedTree`

returns `true`

if the digraph `digraph` is an undirected tree, and the property `IsUndirectedForest`

returns `true`

if `digraph` is an undirected forest; otherwise, these properties return `false`

.

An *undirected tree* is a symmetric digraph without loops, in which for any pair of distinct vertices `u`

and `v`

, there is exactly one directed path from `u`

to `v`

. See `IsSymmetricDigraph`

(6.1-10) and `DigraphHasLoops`

(6.1-1), and see section 1.1-1 for the definition of directed path. This definition implies that an undirected tree has no multiple edges.

An *undirected forest* is a digraph, each of whose connected components is an undirected tree. In other words, an undirected forest is isomorphic to a disjoint union of undirected trees. See `DigraphConnectedComponents`

(5.3-8) and `DigraphDisjointUnion`

(3.3-25). In particular, every undirected tree is an undirected forest.

Please note that the digraph with zero vertices is considered to be neither an undirected tree nor an undirected forest.

gap> gr := Digraph([[3], [3], [1, 2]]); <digraph with 3 vertices, 4 edges> gap> IsUndirectedTree(gr); true gap> IsSymmetricDigraph(gr) and not DigraphHasLoops(gr); true gap> gr := Digraph([[3], [5], [1, 4], [3], [2]]); <digraph with 5 vertices, 6 edges> gap> IsConnectedDigraph(gr); false gap> IsUndirectedTree(gr); false gap> IsUndirectedForest(gr); true gap> gr := Digraph([[1, 2], [1], [2]]); <digraph with 3 vertices, 4 edges> gap> IsUndirectedTree(gr) or IsUndirectedForest(gr); false gap> IsSymmetricDigraph(gr) or not DigraphHasLoops(gr); false

`‣ IsEulerianDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

This property returns true if the digraph `digraph` is Eulerian.

A digraph is called *Eulerian* if there exists a directed circuit on the digraph which includes every edge exactly once. See section 1.1-1 for the definition of a directed circuit.

gap> gr := Digraph([[]]); <digraph with 1 vertex, 0 edges> gap> IsEulerianDigraph(gr); true gap> gr := Digraph([[2], []]); <digraph with 2 vertices, 1 edge> gap> IsEulerianDigraph(gr); false gap> gr := Digraph([[3], [], [2]]); <digraph with 3 vertices, 2 edges> gap> IsEulerianDigraph(gr); false gap> gr := Digraph([[2], [3], [1]]); <digraph with 3 vertices, 3 edges> gap> IsEulerianDigraph(gr); true

`‣ IsHamiltonianDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

If `digraph` is Hamiltonian, then this property returns `true`

, and `false`

if it is not.

A digraph with `n`

vertices is *Hamiltonian* if it has a directed cycle of length `n`

. See Section 1.1-1 for the definition of a directed cycle. Note the empty digraphs on 0 and 1 vertices are considered to be Hamiltonian.

The method used in this operation has the worst case complexity as `DigraphMonomorphism`

(7.3-4).

gap> g := Digraph([[]]); <digraph with 1 vertex, 0 edges> gap> IsHamiltonianDigraph(g); true gap> g := Digraph([[2], [1]]); <digraph with 2 vertices, 2 edges> gap> IsHamiltonianDigraph(g); true gap> g := Digraph([[3], [], [2]]); <digraph with 3 vertices, 2 edges> gap> IsHamiltonianDigraph(g); false gap> g := Digraph([[2], [3], [1]]); <digraph with 3 vertices, 3 edges> gap> IsHamiltonianDigraph(g); true

`‣ IsCycleDigraph` ( digraph ) | ( property ) |

Returns: `true`

or `false`

.

`IsCycleDigraph`

returns `true`

if the digraph `digraph` is isomorphic to the cycle digraph with the same number of vertices as `digraph`, and `false`

if it is not; see `CycleDigraph`

(3.5-5).

A digraph is a *cycle* if and only if it is strongly connected and has the same number of edges as vertices.

gap> gr := Digraph([[1, 3], [2, 3], [3]]); <digraph with 3 vertices, 5 edges> gap> IsCycleDigraph(gr); false gap> gr := CycleDigraph(5); <digraph with 5 vertices, 5 edges> gap> IsCycleDigraph(gr); true gap> gr := OnDigraphs(gr, (1, 2, 3)); <digraph with 5 vertices, 5 edges> gap> gr = CycleDigraph(5); false gap> IsCycleDigraph(gr); true

generated by GAPDoc2HTML