Goto Chapter: Top 1 2 3 4 5 6 7 8 9 A Bib Ind

6 Properties of digraphs

6.1 Edge properties

6.1-1 DigraphHasLoops
 ‣ 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


6.1-2 IsAntisymmetricDigraph
 ‣ 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 ] ]


6.1-3 IsBipartiteDigraph
 ‣ 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

6.1-4 IsCompleteBipartiteDigraph
 ‣ 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


6.1-5 IsCompleteDigraph
 ‣ 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


6.1-6 IsEmptyDigraph
 ‣ 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

6.1-7 IsFunctionalDigraph
 ‣ 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


6.1-8 IsMultiDigraph
 ‣ 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

6.1-9 IsReflexiveDigraph
 ‣ 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


6.1-10 IsSymmetricDigraph
 ‣ 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
[ [  0,  1,  0 ],
[  1,  0,  1 ],
[  0,  1,  1 ] ]
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
[ [  0,  1,  1 ],
[  1,  0,  1 ],
[  0,  1,  1 ] ]
false


6.1-11 IsTournament
 ‣ 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


6.1-12 IsTransitiveDigraph
 ‣ 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


6.1-13 IsPartialOrderDigraph
 ‣ IsPartialOrderDigraph( digraph ) ( property )

Returns: true or false.

This is a synonym for IsReflexiveDigraph (6.1-9) and IsAntisymmetricDigraph (6.1-2) and IsTransitiveDigraph (6.1-12). For a partial order digraph digraph, the corresponding partial order is the 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


6.1-14 IsMeetSemilatticeDigraph
 ‣ 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-13) 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


6.2 Regularity

6.2-1 IsInRegularDigraph
 ‣ 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


6.2-2 IsOutRegularDigraph
 ‣ 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


6.2-3 IsRegularDigraph
 ‣ 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


6.2-4 IsDistanceRegularDigraph
 ‣ 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


6.3 Connectivity and cycles

6.3-1 IsAcyclicDigraph
 ‣ 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

6.3-2 IsConnectedDigraph
 ‣ 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

6.3-3 IsBiconnectedDigraph
 ‣ IsBiconnectedDigraph( digraph ) ( property )

Returns: true or false.

A connected digraph is biconnected if it is still connected (in the sense of IsConnectedDigraph (6.3-2)) 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

6.3-4 IsStronglyConnectedDigraph
 ‣ 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


6.3-5 IsAperiodicDigraph
 ‣ 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


6.3-6 IsDirectedTree
 ‣ 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


6.3-7 IsUndirectedTree
 ‣ 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

6.3-8 IsEulerianDigraph
 ‣ 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


6.3-9 IsHamiltonianDigraph
 ‣ 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


6.3-10 IsCycleDigraph
 ‣ 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
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 A Bib Ind

generated by GAPDoc2HTML