Goto Chapter: Top 1 2 3 4 5 6 7 8 9 A Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

6 Properties of digraphs
 6.1 Vertex properties
 6.2 Edge properties
 6.3 Edge Weights
 6.4 Orders
 6.5 Regularity
 6.6 Connectivity and cycles
 6.7 Planarity
 6.8 Homomorphisms and transformations

6 Properties of digraphs

6.1 Vertex properties

6.1-1 DigraphHasAVertex
‣ DigraphHasAVertex( digraph )( property )

Returns: true or false.

Returns true if the digraph digraph has at least one vertex, and false if it does not.

See also DigraphHasNoVertices (6.1-2).

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> D := Digraph([]);
<immutable empty digraph with 0 vertices>
gap> DigraphHasAVertex(D);
false
gap> D := Digraph([[]]);
<immutable empty digraph with 1 vertex>
gap> DigraphHasAVertex(D);
true
gap> D := Digraph([[], [1]]);
<immutable digraph with 2 vertices, 1 edge>
gap> DigraphHasAVertex(D);
true

6.1-2 DigraphHasNoVertices
‣ DigraphHasNoVertices( digraph )( property )

Returns: true or false.

Returns true if the digraph digraph is the unique digraph with zero vertices, and false otherwise.

See also DigraphHasAVertex (6.1-1).

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> D := Digraph([]);
<immutable empty digraph with 0 vertices>
gap> DigraphHasNoVertices(D);
true
gap> D := Digraph([[]]);
<immutable empty digraph with 1 vertex>
gap> DigraphHasNoVertices(D);
false
gap> D := Digraph([[], [1]]);
<immutable digraph with 2 vertices, 1 edge>
gap> DigraphHasNoVertices(D);
false

6.2 Edge properties

6.2-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.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> D := Digraph([[1, 2], [2]]);
<immutable digraph with 2 vertices, 3 edges>
gap> DigraphEdges(D);
[ [ 1, 1 ], [ 1, 2 ], [ 2, 2 ] ]
gap> DigraphHasLoops(D);
true
gap> D := Digraph([[2, 3], [1], [2]]);
<immutable digraph with 3 vertices, 4 edges>
gap> DigraphEdges(D);
[ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 3, 2 ] ]
gap> DigraphHasLoops(D);
false
gap> D := CompleteDigraph(IsMutableDigraph, 4);
<mutable digraph with 4 vertices, 12 edges>
gap> DigraphHasLoops(D);
false

6.2-2 IsAntiSymmetricDigraph
‣ IsAntiSymmetricDigraph( digraph )( property )
‣ 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.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> gr1 := Digraph([[2], [1, 3], [2, 3]]);
<immutable 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]]);
<immutable multidigraph with 3 vertices, 5 edges>
gap> IsAntisymmetricDigraph(gr2);
true
gap> DigraphEdges(gr2);
[ [ 1, 1 ], [ 1, 2 ], [ 2, 3 ], [ 2, 3 ], [ 3, 1 ] ]

6.2-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 DigraphGreedyColouring (7.3-16).

See also DigraphBicomponents (5.4-13).

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> D := ChainDigraph(4);
<immutable chain digraph with 4 vertices>
gap> IsBipartiteDigraph(D);
true
gap> D := CycleDigraph(3);
<immutable cycle digraph with 3 vertices>
gap> IsBipartiteDigraph(D);
false
gap> D := CompleteBipartiteDigraph(IsMutableDigraph, 5, 4);
<mutable digraph with 9 vertices, 40 edges>
gap> IsBipartiteDigraph(D);
true

6.2-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.2-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.4-13).

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-12).

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> D := CycleDigraph(2);
<immutable cycle digraph with 2 vertices>
gap> IsCompleteBipartiteDigraph(D);
true
gap> D := CycleDigraph(4);
<immutable cycle digraph with 4 vertices>
gap> IsBipartiteDigraph(D);
true
gap> IsCompleteBipartiteDigraph(D);
false
gap> D := CompleteBipartiteDigraph(IsMutableDigraph, 5, 4);
<mutable digraph with 9 vertices, 40 edges>
gap> IsCompleteBipartiteDigraph(D);
true

6.2-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.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> D := Digraph([[2, 3], [1, 3], [1, 2]]);
<immutable digraph with 3 vertices, 6 edges>
gap> IsCompleteDigraph(D);
true
gap> D := Digraph([[2, 2], [1]]);
<immutable multidigraph with 2 vertices, 3 edges>
gap> IsCompleteDigraph(D);
false
gap> D := CompleteBipartiteDigraph(IsMutableDigraph, 5, 4);
<mutable digraph with 9 vertices, 40 edges>
gap> IsCompleteDigraph(D);
false

6.2-6 IsCompleteMultipartiteDigraph
‣ IsCompleteMultipartiteDigraph( digraph )( property )

Returns: true or false.

This property returns true if digraph is a complete multipartite digraph, and false if not.

A digraph is a complete multipartite digraph if and only if its vertices can be partitioned into at least two maximal independent sets, where every possible edge between these independent sets occurs in the digraph exactly once.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> D := CompleteMultipartiteDigraph([2, 4, 6]);
<immutable complete multipartite digraph with 12 vertices, 88 edges>
gap> IsCompleteMultipartiteDigraph(D);
true
gap> D := CompleteBipartiteDigraph(IsMutableDigraph, 5, 4);
<mutable digraph with 9 vertices, 40 edges>
gap> IsCompleteMultipartiteDigraph(D);
true

6.2-7 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. See also IsNonemptyDigraph (6.2-12).

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> D := Digraph([[], []]);
<immutable empty digraph with 2 vertices>
gap> IsEmptyDigraph(D);
true
gap> IsNullDigraph(D);
true
gap> D := Digraph([[], [1]]);
<immutable digraph with 2 vertices, 1 edge>
gap> IsEmptyDigraph(D);
false
gap> IsNullDigraph(D);
false

6.2-8 IsEquivalenceDigraph
‣ IsEquivalenceDigraph( digraph )( property )

Returns: true or false.

A digraph is an equivalence digraph if and only if the digraph satisfies all of IsReflexiveDigraph (6.2-13), IsSymmetricDigraph (6.2-14) and IsTransitiveDigraph (6.2-16). A partial order digraph corresponds to an equivalence relation.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> D := Digraph([[1, 3], [2], [1, 3]]);
<immutable digraph with 3 vertices, 5 edges>
gap> IsEquivalenceDigraph(D);
true

6.2-9 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.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.2-10 IsPermutationDigraph
‣ IsPermutationDigraph( digraph )( property )

Returns: true or false.

This property is true if the digraph digraph is functional and each node has only one in-neighbour.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.2-11 IsMultiDigraph
‣ IsMultiDigraph( digraph )( property )

Returns: true or false.

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

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.2-12 IsNonemptyDigraph
‣ IsNonemptyDigraph( digraph )( property )

Returns: true or false.

Returns true if the digraph digraph is nonempty, and false if it is not. A digraph is nonempty if it has at least one edge.

See also IsEmptyDigraph (6.2-7).

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> D := Digraph([[], []]);
<immutable empty digraph with 2 vertices>
gap> IsNonemptyDigraph(D);
false
gap> D := Digraph([[], [1]]);
<immutable digraph with 2 vertices, 1 edge>
gap> IsNonemptyDigraph(D);
true

6.2-13 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.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.2-14 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).

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> gr1 := Digraph([[2], [1, 3], [2, 3]]);
<immutable 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]]);
<immutable 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

6.2-15 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.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> D := Digraph([[2, 3, 4], [3, 4], [4], []]);
<immutable digraph with 4 vertices, 6 edges>
gap> IsTournament(D);
true
gap> D := Digraph([[2], [1], [3]]);
<immutable digraph with 3 vertices, 3 edges>
gap> IsTournament(D);
false
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> IsTournament(D);
true
gap> DigraphRemoveEdge(D, 1, 2);
<mutable digraph with 3 vertices, 2 edges>
gap> IsTournament(D);
false

6.2-16 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-10)], then methods with complexity O(m + n + m ⋅ n) will be used when appropriate.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.3 Edge Weights

6.3-1 EdgeWeights
‣ EdgeWeights( digraph )( attribute )
‣ EdgeWeightsMutableCopy( digraph )( operation )

Returns: A list of lists of integers, floats or rationals.

EdgeWeights returns the list of lists of edge weights of the edges of the digraph digraph.

More specifically, weights[i][j] is the weight given to the jth edge from vertex i, according to the ordering of edges given by OutNeighbours(digraph)[i].

The function EdgeWeights returns an immutable list of immutable lists, whereas the function EdgeWeightsMutableCopy returns a copy of EdgeWeights which is a mutable list of mutable lists.

The edge weights of a digraph cannot be computed and must be set either using SetEdgeWeights or EdgeWeightedDigraph (6.3-2).

gap> gr := EdgeWeightedDigraph([[2], [3], [1]], [[5], [10], [15]]);
<immutable digraph with 3 vertices, 3 edges>
gap> EdgeWeights(gr);
[ [ 5 ], [ 10 ], [ 15 ] ]
gap> a := EdgeWeightsMutableCopy(gr);
[ [ 5 ], [ 10 ], [ 15 ] ]
gap> a[1][1] := 100;
100
gap> a;
[ [ 100 ], [ 10 ], [ 15 ] ]
gap> b := EdgeWeights(gr);
[ [ 5 ], [ 10 ], [ 15 ] ]
gap> b[1][1] := 534;
Error, List Assignment: <list> must be a mutable list

6.3-2 EdgeWeightedDigraph
‣ EdgeWeightedDigraph( digraph, weights )( function )

Returns: A digraph or fail

The argument digraph may be a digraph or a list of lists of integers, floats or rationals.

weights must be a list of lists of integers, floats or rationals of an equal size and shape to OutNeighbours(digraph), otherwise it will fail.

This will create a digraph and set the EdgeWeights to weights.

See EdgeWeights (6.3-1).

gap> g := EdgeWeightedDigraph(Digraph([[2], [1]]), [[5], [15]]);
<immutable digraph with 2 vertices, 2 edges>
gap> g := EdgeWeightedDigraph([[2], [1]], [[5], [15]]);
<immutable digraph with 2 vertices, 2 edges>
gap> EdgeWeights(g);
[ [ 5 ], [ 15 ] ]

6.3-3 EdgeWeightedDigraphTotalWeight
‣ EdgeWeightedDigraphTotalWeight( digraph )( attribute )

Returns: An integer, float or rational.

If digraph is a digraph with edge weights, then this attribute returns the sum of the weights of its edges.

If the argument digraph is mutable, then the return value of this attribute is recomputed every time it is called.

See EdgeWeights (6.3-1).

gap> D := EdgeWeightedDigraph([[2], [1], [1, 2]],
>                             [[12], [5], [6, 9]]);
<immutable digraph with 3 vertices, 4 edges>
gap> EdgeWeightedDigraphTotalWeight(D);
32

6.3-4 EdgeWeightedDigraphMinimumSpanningTree
‣ EdgeWeightedDigraphMinimumSpanningTree( digraph )( attribute )

Returns: A digraph.

If digraph is a connected digraph with edge weights, then this attribute returns a digraph which is a minimum spanning tree of digraph.

A spanning tree of a digraph is a subdigraph with the same vertices but a subset of its edges that form an undirected tree. It is minimum if it has the smallest possible total weight for a spanning tree of that digraph.

If the argument digraph is mutable, then the return value of this attribute is recomputed every time it is called.

See EdgeWeights (6.3-1), EdgeWeightedDigraphTotalWeight (6.3-3) and IsConnectedDigraph (6.6-3).

gap> D := EdgeWeightedDigraph([[2], [1], [1, 2]],
>                             [[12], [5], [6, 9]]);
<immutable digraph with 3 vertices, 4 edges>
gap> T := EdgeWeightedDigraphMinimumSpanningTree(D);
<immutable digraph with 3 vertices, 2 edges>
gap> EdgeWeights(T);
[ [  ], [ 5 ], [ 6 ] ]

6.4 Orders

6.4-1 IsPreorderDigraph
‣ IsPreorderDigraph( digraph )( property )
‣ IsQuasiorderDigraph( digraph )( property )

Returns: true or false.

A digraph is a preorder digraph if and only if the digraph satisfies both IsReflexiveDigraph (6.2-13) and IsTransitiveDigraph (6.2-16). 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.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.4-2 IsPartialOrderDigraph
‣ IsPartialOrderDigraph( digraph )( property )

Returns: true or false.

A digraph is a partial order digraph if and only if the digraph satisfies all of IsReflexiveDigraph (6.2-13), IsAntisymmetricDigraph (6.2-2) and IsTransitiveDigraph (6.2-16). 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.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.4-3 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.4-2) 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.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.4-4 DigraphMeetTable
‣ DigraphMeetTable( digraph )( attribute )
‣ DigraphJoinTable( digraph )( attribute )

Returns: A matrix or fail.

DigraphMeetTable returns the meet table of digraph if digraph is a meet semilattice digraph IsMeetSemilatticeDigraph (6.4-3). Similarly, DigraphJoinTable returns the join table of digraph if digraph is a join semilattice digraph. IsJoinSemilatticeDigraph (6.4-3).

When digraph is a meet semilattice digraph with n vertices, the meet table of digraph is the matrix A such that the (i, j) entry of A is the meet of vertices i and j.

Similarly, when digraph is a join semilattice digraph with n vertices, the join table of digraph is the matrix A such that the (i, j) entry of A is the join of vertices i and j. Otherwise, each function returns fail.

gap> D := Digraph([[1, 2, 3, 4], [2, 4], [3, 4], [4]]);
<immutable digraph with 4 vertices, 9 edges>
gap> IsJoinSemilatticeDigraph(D);
true
gap> Display(DigraphJoinTable(D));
[ [  1,  2,  3,  4 ],
  [  2,  2,  4,  4 ],
  [  3,  4,  3,  4 ],
  [  4,  4,  4,  4 ] ]
gap> D := CycleDigraph(5);
<immutable cycle digraph with 5 vertices>
gap> DigraphJoinTable(D);
fail

6.4-5 IsUpperSemimodularDigraph
‣ IsUpperSemimodularDigraph( D )( property )
‣ IsLowerSemimodularDigraph( D )( property )

Returns: true or false.

IsUpperSemimodularDigraph returns true if the digraph D represents an upper semimodular lattice and false if it does not. Similarly, IsLowerSemimodularDigraph returns true if D represents a lower semimodular lattice and false if it does not.

In a lattice we say that a vertex a covers a vertex b if a is greater than b, and there are no further vertices between a and b. A lattice is upper semimodular if whenever the meet of a and b is covered by a, the join of a and b covers b. Lower semimodularity is defined analogously.

See also IsLatticeDigraph (6.4-3), NonUpperSemimodularPair (5.3-2), and NonLowerSemimodularPair (5.3-2). If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> D := DigraphFromDigraph6String(
> "&M~~sc`lYUZO__KIBboC_@h?U_?_GL?A_?c");
<immutable digraph with 14 vertices, 66 edges>
gap> IsUpperSemimodularDigraph(D);
true
gap> IsLowerSemimodularDigraph(D);
false

6.4-6 IsDistributiveLatticeDigraph
‣ IsDistributiveLatticeDigraph( digraph )( property )

Returns: true or false.

IsDistributiveLatticeDigraph returns true if the digraph digraph is a distributive lattice digraph.

A distributive lattice digraph is a lattice digraph (IsLatticeDigraph (6.4-3)) which is distributive. That is to say, the functions PartialOrderDigraphMeetOfVertices (5.3-1) and PartialOrderDigraphJoinOfVertices (5.3-1) distribute over each other.

Equivalently, a distributive lattice digraph is a lattice digraph in which the lattice digraphs representing M3 and N5 are not embeddable as lattices (see https://en.wikipedia.org/wiki/Distributive_lattice and IsLatticeEmbedding (7.3-21)).

    
The lattices M3 and N5.
If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> D := Digraph([[2, 3], [4], [4], []]);
<immutable digraph with 4 vertices, 4 edges>
gap> D := DigraphReflexiveTransitiveClosure(D);
<immutable preorder digraph with 4 vertices, 9 edges>
gap> IsDistributiveLatticeDigraph(D);
true
gap> N5 := Digraph([[2, 4], [3], [5], [5], []]);
<immutable digraph with 5 vertices, 5 edges>
gap> N5 := DigraphReflexiveTransitiveClosure(N5);
<immutable preorder digraph with 5 vertices, 13 edges>
gap> IsDistributiveLatticeDigraph(N5);
false

6.4-7 IsModularLatticeDigraph
‣ IsModularLatticeDigraph( digraph )( property )

Returns: true or false.

IsModularLatticeDigraph returns true if the digraph digraph is a modular lattice digraph.

A modular lattice digraph is a lattice digraph (IsLatticeDigraph (6.4-3)) which is modular. That is to say, the lattice digraph representing N5 is not embeddable as a lattice (see https://en.wikipedia.org/wiki/Modular_lattice and IsLatticeEmbedding (7.3-21)).

The lattice N5.
If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> D := ChainDigraph(5);
<immutable chain digraph with 5 vertices>
gap> D := DigraphReflexiveTransitiveClosure(D);
<immutable preorder digraph with 5 vertices, 15 edges>
gap> IsModularLatticeDigraph(D);
true
gap> N5 := Digraph([[2, 3], [4], [4], []]);
<immutable digraph with 4 vertices, 4 edges>
gap> DigraphReflexiveTransitiveClosure(N5);
<immutable preorder digraph with 4 vertices, 9 edges>
gap> IsModularLatticeDigraph(N5);
false

6.5 Regularity

6.5-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.5-2) and IsRegularDigraph (6.5-3).

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.5-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.5-1) and IsRegularDigraph (6.5-3).

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.5-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.5-1) and IsOutRegularDigraph (6.5-2).

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.5-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.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.6 Connectivity and cycles

6.6-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.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.6-2 IsChainDigraph
‣ 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-9).

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.6-8) and OutDegrees (5.2-8).

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.6-3 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-5) 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).

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.6-4 IsBiconnectedDigraph
‣ IsBiconnectedDigraph( digraph )( property )

Returns: true or false.

A connected digraph is biconnected if it is still connected (in the sense of IsConnectedDigraph (6.6-3)) when any vertex is removed. If D has at least 3 vertices, then IsBiconnectedDigraph implies IsBridgelessDigraph (6.6-5); see ArticulationPoints (5.4-14) or Bridges (5.4-15) for a more detailed explanation.

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 are ignored by this method.

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

See also Bridges (5.4-15), ArticulationPoints (5.4-14), and IsBridgelessDigraph (6.6-5).

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> IsBiconnectedDigraph(Digraph([[1, 3], [2, 3], [3]]));
false
gap> IsBiconnectedDigraph(CycleDigraph(5));
true
gap> D := Digraph([[1, 1], [1, 1, 2], [3], [3, 3, 4, 4]]);;
gap> IsBiconnectedDigraph(D);
false
gap> D := CompleteBipartiteDigraph(IsMutableDigraph, 5, 4);
<mutable digraph with 9 vertices, 40 edges>
gap> IsBiconnectedDigraph(D);
true

6.6-5 IsBridgelessDigraph
‣ IsBridgelessDigraph( digraph )( property )

Returns: true or false.

A connected digraph is bridgeless if it is still connected (in the sense of IsConnectedDigraph (6.6-3)) when any edge is removed. If digraph has at least 3 vertices, then IsBiconnectedDigraph (6.6-4) implies IsBridgelessDigraph; see ArticulationPoints (5.4-14) or Bridges (5.4-15) for a more detailed explanation.

IsBridgelessDigraph returns true if the digraph digraph is bridgeless, and false if it is not. In particular, IsBridgelessDigraph returns false if digraph is not connected.

Multiple edges are ignored by this method.

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

See also Bridges (5.4-15), ArticulationPoints (5.4-14), and IsBiconnectedDigraph (6.6-4).

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> IsBridgelessDigraph(Digraph([[1, 3], [2, 3], [3]]));
false
gap> IsBridgelessDigraph(CycleDigraph(5));
true
gap> D := Digraph([[1, 1], [1, 1, 2], [3], [3, 3, 4, 4]]);;
gap> IsBridgelessDigraph(D);
false
gap> D := CompleteBipartiteDigraph(IsMutableDigraph, 5, 4);
<mutable digraph with 9 vertices, 40 edges>
gap> IsBridgelessDigraph(D);
true
gap> D := Digraph([[2, 5], [1, 3, 4, 5], [2, 4], [2, 3], [1, 2]]);
<immutable digraph with 5 vertices, 12 edges>
gap> IsBridgelessDigraph(D);
true
gap> IsBiconnectedDigraph(D);
false
gap> D := Digraph([[2], [3], [4], [2]]);
<immutable digraph with 4 vertices, 4 edges>
gap> IsBridgelessDigraph(D);
false
gap> IsBiconnectedDigraph(D);
false
gap> IsBridgelessDigraph(ChainDigraph(2));
false
gap> IsBiconnectedDigraph(ChainDigraph(2));
true

6.6-6 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.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> D := CycleDigraph(250000);
<immutable cycle digraph with 250000 vertices>
gap> IsStronglyConnectedDigraph(D);
true
gap> D := DigraphRemoveEdges(D, [[250000, 1]]);
<immutable digraph with 250000 vertices, 249999 edges>
gap> IsStronglyConnectedDigraph(D);
false
gap> D := CycleDigraph(IsMutableDigraph, 250000);
<mutable digraph with 250000 vertices, 250000 edges>
gap> IsStronglyConnectedDigraph(D);
true
gap> DigraphRemoveEdge(D, [250000, 1]);
<mutable digraph with 250000 vertices, 249999 edges>
gap> IsStronglyConnectedDigraph(D);
false

6.6-7 IsAperiodicDigraph
‣ IsAperiodicDigraph( digraph )( property )

Returns: true or false.

This property is true if the digraph digraph is aperiodic, i.e. if its DigraphPeriod (5.4-17) is equal to 1. Otherwise, the property is false.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.6-8 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 that the empty digraph with zero vertices is not considered to be a directed tree, because it has no source.

See also DigraphSources (5.1-9).

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.6-9 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.2-14) and DigraphHasLoops (6.2-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.4-9) and DigraphDisjointUnion (3.3-29). 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.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.6-10 IsEulerianDigraph
‣ IsEulerianDigraph( digraph )( property )

Returns: true or false.

This property returns true if the digraph digraph is Eulerian.

A connected 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. Note that the empty digraph with at most one vertex is considered to be Eulerian.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.6-11 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).

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.6-12 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-14).

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

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

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

6.7 Planarity

6.7-1 IsPlanarDigraph
‣ IsPlanarDigraph( digraph )( property )

Returns: true or false.

A planar digraph is a digraph that can be embedded in the plane in such a way that its edges do not intersect. A digraph is planar if and only if it does not have a subdigraph that is homeomorphic to either the complete graph on 5 vertices or the complete bipartite graph with vertex sets of sizes 3 and 3.

IsPlanarDigraph returns true if the digraph digraph is planar and false if it is not. The directions and multiplicities of any edges in digraph are ignored by IsPlanarDigraph.

See also IsOuterPlanarDigraph (6.7-2).

This method uses the reference implementation in edge-addition-planarity-suite by John Boyer of the algorithms described in [BM06].

gap> IsPlanarDigraph(CompleteDigraph(4));
true
gap> IsPlanarDigraph(CompleteDigraph(5));
false
gap> IsPlanarDigraph(CompleteBipartiteDigraph(2, 3));
true
gap> IsPlanarDigraph(CompleteBipartiteDigraph(3, 3));
false
gap> IsPlanarDigraph(CompleteDigraph(IsMutableDigraph, 4));
true
gap> IsPlanarDigraph(CompleteDigraph(IsMutableDigraph, 5));
false
gap> IsPlanarDigraph(CompleteBipartiteDigraph(IsMutableDigraph, 2, 3));
true
gap> IsPlanarDigraph(CompleteBipartiteDigraph(IsMutableDigraph, 3, 3));
false

6.7-2 IsOuterPlanarDigraph
‣ IsOuterPlanarDigraph( digraph )( property )

Returns: true or false.

An outer planar digraph is a digraph that can be embedded in the plane in such a way that its edges do not intersect, and all vertices belong to the unbounded face of the embedding. A digraph is outer planar if and only if it does not have a subdigraph that is homeomorphic to either the complete graph on 4 vertices or the complete bipartite graph with vertex sets of sizes 2 and 3.

IsOuterPlanarDigraph returns true if the digraph digraph is outer planar and false if it is not. The directions and multiplicities of any edges in digraph are ignored by IsPlanarDigraph.

See also IsPlanarDigraph (6.7-1). This method uses the reference implementation in edge-addition-planarity-suite by John Boyer of the algorithms described in [BM06].

gap> IsOuterPlanarDigraph(CompleteDigraph(4));
false
gap> IsOuterPlanarDigraph(CompleteDigraph(5));
false
gap> IsOuterPlanarDigraph(CompleteBipartiteDigraph(2, 3));
false
gap> IsOuterPlanarDigraph(CompleteBipartiteDigraph(3, 3));
false
gap> IsOuterPlanarDigraph(CycleDigraph(10));
true
gap> IsOuterPlanarDigraph(CompleteDigraph(IsMutableDigraph, 4));
false
gap> IsOuterPlanarDigraph(CompleteDigraph(IsMutableDigraph, 5));
false
gap> IsOuterPlanarDigraph(CompleteBipartiteDigraph(IsMutableDigraph,
>                                                  2, 3));
false
gap> IsOuterPlanarDigraph(CompleteBipartiteDigraph(IsMutableDigraph,
>                                                  3, 3));
false
gap> IsOuterPlanarDigraph(CycleDigraph(IsMutableDigraph, 10));
true

6.8 Homomorphisms and transformations

6.8-1 IsDigraphCore
‣ IsDigraphCore( digraph )( property )

Returns: true or false.

This property returns true if digraph is a core, and false if it is not.

A digraph D is a core if and only if it has no proper subdigraphs A such that there exists a homomorphism from D to A. In other words, a digraph D is a core if and only if every endomorphism on D is an automorphism on D.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> D := CompleteDigraph(6);
<immutable complete digraph with 6 vertices>
gap> IsDigraphCore(D);
true
gap> D := DigraphSymmetricClosure(CycleDigraph(6));
<immutable symmetric digraph with 6 vertices, 12 edges>
gap> DigraphHomomorphism(D, CompleteDigraph(2));
Transformation( [ 1, 2, 1, 2, 1, 2 ] )
gap> IsDigraphCore(D);
false

6.8-2 IsEdgeTransitive
‣ IsEdgeTransitive( digraph )( property )

Returns: true or false.

If digraph is a digraph without multiple edges, then IsEdgeTransitive returns true if digraph is edge transitive, and false otherwise. A digraph is edge transitive if its automorphism group acts transitively on its edges (via the action OnPairs (Reference: OnPairs)).

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> IsEdgeTransitive(CompleteDigraph(2));
true
gap> IsEdgeTransitive(ChainDigraph(3));
false
gap> IsEdgeTransitive(Digraph([[2], [3, 3, 3], []]));
Error, the argument <D> must be a digraph with no multiple edges,

6.8-3 IsVertexTransitive
‣ IsVertexTransitive( digraph )( property )

Returns: true or false.

If digraph is a digraph, then IsVertexTransitive returns true if digraph is vertex transitive, and false otherwise. A digraph is vertex transitive if its automorphism group acts transitively on its vertices.

If the argument digraph is mutable, then the return value of this property is recomputed every time it is called.

gap> IsVertexTransitive(CompleteDigraph(2));
true
gap> IsVertexTransitive(ChainDigraph(3));
false
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 A Bib Ind

generated by GAPDoc2HTML