7 Homomorphisms

7.2 Isomorphisms and canonical labellings

7.2-1 DigraphsUseNauty

7.2-2 AutomorphismGroup

7.2-3 BlissAutomorphismGroup

7.2-4 NautyAutomorphismGroup

7.2-5 AutomorphismGroup

7.2-6 BlissCanonicalLabelling

7.2-7 BlissCanonicalLabelling

7.2-8 BlissCanonicalDigraph

7.2-9 DigraphGroup

7.2-10 DigraphOrbits

7.2-11 DigraphOrbitReps

7.2-12 DigraphSchreierVector

7.2-13 DigraphStabilizer

7.2-14 IsIsomorphicDigraph

7.2-15 IsIsomorphicDigraph

7.2-16 IsomorphismDigraphs

7.2-17 IsomorphismDigraphs

7.2-18 RepresentativeOutNeighbours

7.2-19 IsDigraphIsomorphism

7.2-1 DigraphsUseNauty

7.2-2 AutomorphismGroup

7.2-3 BlissAutomorphismGroup

7.2-4 NautyAutomorphismGroup

7.2-5 AutomorphismGroup

7.2-6 BlissCanonicalLabelling

7.2-7 BlissCanonicalLabelling

7.2-8 BlissCanonicalDigraph

7.2-9 DigraphGroup

7.2-10 DigraphOrbits

7.2-11 DigraphOrbitReps

7.2-12 DigraphSchreierVector

7.2-13 DigraphStabilizer

7.2-14 IsIsomorphicDigraph

7.2-15 IsIsomorphicDigraph

7.2-16 IsomorphismDigraphs

7.2-17 IsomorphismDigraphs

7.2-18 RepresentativeOutNeighbours

7.2-19 IsDigraphIsomorphism

7.3 Homomorphisms of digraphs

7.3-1 HomomorphismDigraphsFinder

7.3-2 DigraphHomomorphism

7.3-3 HomomorphismsDigraphs

7.3-4 DigraphMonomorphism

7.3-5 MonomorphismsDigraphs

7.3-6 DigraphEpimorphism

7.3-7 EpimorphismsDigraphs

7.3-8 GeneratorsOfEndomorphismMonoid

7.3-9 DigraphColouring

7.3-10 DigraphEmbedding

7.3-11 ChromaticNumber

7.3-12 IsDigraphHomomorphism

7.3-13 IsDigraphEmbedding

7.3-1 HomomorphismDigraphsFinder

7.3-2 DigraphHomomorphism

7.3-3 HomomorphismsDigraphs

7.3-4 DigraphMonomorphism

7.3-5 MonomorphismsDigraphs

7.3-6 DigraphEpimorphism

7.3-7 EpimorphismsDigraphs

7.3-8 GeneratorsOfEndomorphismMonoid

7.3-9 DigraphColouring

7.3-10 DigraphEmbedding

7.3-11 ChromaticNumber

7.3-12 IsDigraphHomomorphism

7.3-13 IsDigraphEmbedding

`‣ OnDigraphs` ( digraph, perm ) | ( operation ) |

`‣ OnDigraphs` ( digraph, trans ) | ( operation ) |

Returns: A digraph.

If `digraph` is a digraph, and the second argument `perm` is a *permutation* of the vertices of `digraph`, then this operation returns a digraph constructed by relabelling the vertices of `digraph` according to `perm`. Note that for an automorphism `f`

of a digraph, we have `OnDigraphs(`

`digraph`, f) = `digraph`.

If the second argument is a *transformation* `trans` of the vertices of `digraph`, then this operation returns a digraph constructed by transforming the source and range of each edge according to `trans`. Thus a vertex which does not appear in the image of `trans` will be isolated in the returned digraph, and the returned digraph may contain multiple edges, even if `digraph` does not. If `trans` is mathematically a permutation, then the result coincides with `OnDigraphs(`

.`digraph`, AsPermutation(`trans`))

The `DigraphVertexLabels`

(5.1-9) of `digraph` will not be retained in the returned digraph.

gap> gr := Digraph([[3], [1, 3, 5], [1], [1, 2, 4], [2, 3, 5]]); <digraph with 5 vertices, 11 edges> gap> new := OnDigraphs(gr, (1, 2)); <digraph with 5 vertices, 11 edges> gap> OutNeighbours(new); [ [ 2, 3, 5 ], [ 3 ], [ 2 ], [ 2, 1, 4 ], [ 1, 3, 5 ] ] gap> gr := Digraph([[2], [], [2]]); <digraph with 3 vertices, 2 edges> gap> t := Transformation([1, 2, 1]);; gap> new := OnDigraphs(gr, t); <multidigraph with 3 vertices, 2 edges> gap> OutNeighbours(new); [ [ 2, 2 ], [ ], [ ] ] gap> ForAll(DigraphEdges(gr), > e -> IsDigraphEdge(new, [e[1] ^ t, e[2] ^ t])); true

`‣ OnMultiDigraphs` ( digraph, pair ) | ( operation ) |

`‣ OnMultiDigraphs` ( digraph, perm1, perm2 ) | ( operation ) |

Returns: A digraph.

If `digraph` is a digraph, and `pair` is a pair consisting of a permutation of the vertices and a permutation of the edges of `digraph`, then this operation returns a digraph constructed by relabelling the vertices and edges of `digraph` according to `perm[1]` and `perm[2]`, respectively.

In its second form, `OnMultiDigraphs`

returns a digraph with vertices and edges permuted by `perm1` and `perm2`, respectively.

Note that `OnDigraphs(`

where `digraph`, perm)=OnMultiDigraphs(`digraph`, [perm, ()])`perm`

is a permutation of the vertices of `digraph`. If you are only interested in the action of a permutation on the vertices of a digraph, then you can use `OnDigraphs`

instead of `OnMultiDigraphs`

.

gap> gr1 := Digraph([ > [3, 6, 3], [], [3], [9, 10], [9], [], [], [10, 4, 10], [], []]); <multidigraph with 10 vertices, 10 edges> gap> p := BlissCanonicalLabelling(gr1); [ (1,9,5,3,10,6,4,7), (1,7,9,5,2,8,4,10,3,6) ] gap> gr2 := OnMultiDigraphs(gr1, p); <multidigraph with 10 vertices, 10 edges> gap> OutNeighbours(gr2); [ [ ], [ ], [ 5 ], [ ], [ ], [ ], [ 5, 6 ], [ 6, 7, 6 ], [ 10, 4, 10 ], [ 10 ] ]

From version 0.11.0 of **Digraphs** it is possible to use either bliss or nauty (via NautyTracesInterface) to calculate canonical labellings and automorphism groups of digraphs; see [JK07] and [MP14] for more details about bliss and nauty, respectively.

`‣ DigraphsUseNauty` ( ) | ( function ) |

`‣ DigraphsUseBliss` ( ) | ( function ) |

Returns: Nothing.

These functions can be used to specify whether nauty or bliss should be used by default by **Digraphs**. If NautyTracesInterface is not available, then these functions do nothing. Otherwise, by calling `DigraphsUseNauty`

subsequent computations will default to using nauty rather than bliss, where possible.

You can call these functions at any point in a **GAP** session, as many times as you like, it is guaranteed that existing digraphs remain valid, and that comparison of existing digraphs and newly created digraphs via `IsIsomorphicDigraph`

(7.2-14), `IsIsomorphicDigraph`

(7.2-15), `IsomorphismDigraphs`

(7.2-16), and `IsomorphismDigraphs`

(7.2-17) are also valid.

It is also possible to compute the automorphism group of a specific digraph using both nauty and bliss using `NautyAutomorphismGroup`

(7.2-4) and `BlissAutomorphismGroup`

(7.2-3), respectively.

`‣ AutomorphismGroup` ( digraph ) | ( attribute ) |

Returns: A permutation group.

If `digraph` is a digraph, then this attribute contains the group of automorphisms of `digraph`. An *automorphism* of `digraph` is an isomorphism from `digraph` to itself. See `IsomorphismDigraphs`

(7.2-16) for more information about isomorphisms of digraphs.

The form in which the automorphism group is returned depends on whether `digraph` has multiple edges; see `IsMultiDigraph`

(6.1-8).

**for a digraph without multiple edges**If

`digraph`has no multiple edges, then the automorphism group is returned as a group of permutations on the vertices of`digraph`.**for a multidigraph**If

`digraph`is a multidigraph, then the automorphism group is a group of permutations on the vertices and edges of`digraph`.For convenience, the group is returned as the direct product

`G`

of the group of automorphisms of the vertices of`digraph`with the stabiliser of the vertices in the automorphism group of the edges. These two groups can be accessed using the operation`Projection`

(Reference: Projection for a domain and a positive integer), with the second argument being`1`

or`2`

, respectively.The permutations in the group

`Projection(G, 1)`

act on the vertices of`digraph`, and the permutations in the group`Projection(G, 2)`

act on the indices of`DigraphEdges(`

.`digraph`)

By default, the automorphism group is found using bliss by Tommi Junttila and Petteri Kaski. If NautyTracesInterface is available, then nauty by Brendan Mckay and Adolfo Piperno can be used instead; see `BlissAutomorphismGroup`

(7.2-3), `NautyAutomorphismGroup`

(7.2-4), `DigraphsUseBliss`

(7.2-1), and `DigraphsUseNauty`

(7.2-1).

gap> johnson := DigraphFromGraph6String("E}lw"); <digraph with 6 vertices, 24 edges> gap> G := AutomorphismGroup(johnson); Group([ (3,4), (2,3)(4,5), (1,2)(5,6) ]) gap> cycle := CycleDigraph(9); <digraph with 9 vertices, 9 edges> gap> G := AutomorphismGroup(cycle); Group([ (1,2,3,4,5,6,7,8,9) ]) gap> IsCyclic(G) and Size(G) = 9; true gap> gr := DigraphEdgeUnion(CycleDigraph(3), CycleDigraph(3)); <multidigraph with 3 vertices, 6 edges> gap> G := AutomorphismGroup(gr); Group([ (1,2,3), (8,9), (6,7), (4,5) ]) gap> Range(Projection(G, 1)); Group([ (1,2,3) ]) gap> Range(Projection(G, 2)); Group([ (5,6), (3,4), (1,2) ]) gap> Size(G); 24 gap> gr := Digraph([[2], [3, 3], [3], [2]]); <multidigraph with 4 vertices, 5 edges> gap> G := AutomorphismGroup(gr); Group([ (1,2), (3,4) ]) gap> P1 := Projection(G, 1); 1st projection of Group([ (1,2), (3,4) ]) gap> P2 := Projection(G, 2); 2nd projection of Group([ (1,2), (3,4) ]) gap> DigraphVertices(gr); [ 1 .. 4 ] gap> Range(P1); Group([ (1,4) ]) gap> DigraphEdges(gr); [ [ 1, 2 ], [ 2, 3 ], [ 2, 3 ], [ 3, 3 ], [ 4, 2 ] ] gap> Range(P2); Group([ (2,3) ])

`‣ BlissAutomorphismGroup` ( digraph[, colours] ) | ( attribute ) |

Returns: A permutation group.

If `digraph` is a digraph, then this attribute contains the group of automorphisms of `digraph` as calculated using bliss by Tommi Junttila and Petteri Kaski.

The attribute `AutomorphismGroup`

(7.2-2) and operation `AutomorphismGroup`

(7.2-5) returns the value of either `BlissAutomorphismGroup`

or `NautyAutomorphismGroup`

(7.2-4). These groups are, of course, equal but their generating sets may differ.

See also `DigraphsUseBliss`

(7.2-1), and `DigraphsUseNauty`

(7.2-1).

gap> BlissAutomorphismGroup(JohnsonDigraph(5, 2)); Group([ (3,4)(6,7)(8,9), (2,3)(5,6)(9,10), (2,5)(3,6)(4,7), (1,2)(6,8) (7,9) ])

`‣ NautyAutomorphismGroup` ( digraph[, colours] ) | ( attribute ) |

Returns: A permutation group.

If `digraph` is a digraph, then this attribute contains the group of automorphisms of `digraph` as calculated using nauty by Brendan Mckay and Adolfo Piperno via NautyTracesInterface. The attribute `AutomorphismGroup`

(7.2-2) and operation `AutomorphismGroup`

(7.2-5) returns the value of either `NautyAutomorphismGroup`

or `BlissAutomorphismGroup`

(7.2-3). These groups are, of course, equal but their generating sets may differ.

See also `DigraphsUseBliss`

(7.2-1), and `DigraphsUseNauty`

(7.2-1).

gap> NautyAutomorphismGroup(JohnsonDigraph(5, 2)); Group([ (3,4)(6,7)(8,9), (2,3)(5,6)(9,10), (2,5)(3,6)(4,7), (1,2)(6,8)(7,9) ])

`‣ AutomorphismGroup` ( digraph, colours ) | ( operation ) |

Returns: A permutation group.

This operation computes the automorphism group of a coloured digraph. A coloured digraph can be specified by its underlying digraph `digraph` and its colouring `colours`. Let `n`

be the number of vertices of `digraph`. The colouring `colours` may have one of the following two forms:

a list of

`n`

integers, where`colours``[i]`

is the colour of vertex`i`

, using the colours`[1 .. m]`

for some`m <= n`

; ora list of non-empty disjoint lists whose union is

`DigraphVertices(`

, such that`digraph`)`colours``[i]`

is the list of all vertices with colour`i`

.

The *automorphism group* of a coloured digraph `digraph` with colouring `colours` is the group consisting of its automorphisms; an *automorphism* of `digraph` is an isomorphism of coloured digraphs from `digraph` to itself. This group is equal to the subgroup of `AutomorphismGroup(`

consisting of those automorphisms that preserve the colouring specified by `digraph`)`colours`. See `AutomorphismGroup`

(7.2-2), and see `IsomorphismDigraphs`

(7.2-17) for more information about isomorphisms of coloured digraphs.

The form in which the automorphism group is returned depends on whether `digraph` has multiple edges; see `IsMultiDigraph`

(6.1-8).

**for a digraph without multiple edges**If

`digraph`has no multiple edges, then the automorphism group is returned as a group of permutations on the vertices of`digraph`.**for a multidigraph**If

`digraph`is a multidigraph, then the automorphism group is a group of permutations on the vertices and edges of`digraph`.For convenience, the group is returned as the direct product

`G`

of the group of automorphisms of the vertices of`digraph`with the stabiliser of the vertices in the automorphism group of the edges. These two groups can be accessed using the operation`Projection`

(Reference: Projection for a domain and a positive integer), with the second argument being`1`

or`2`

, respectively.The permutations in the group

`Projection(G, 1)`

act on the vertices of`digraph`, and the permutations in the group`Projection(G, 2)`

act on the indices of`DigraphEdges(`

.`digraph`)

By default, the automorphism group is found using bliss by Tommi Junttila and Petteri Kaski. If NautyTracesInterface is available, then nauty by Brendan Mckay and Adolfo Piperno can be used instead; see `BlissAutomorphismGroup`

(7.2-3), `NautyAutomorphismGroup`

(7.2-4), `DigraphsUseBliss`

(7.2-1), and `DigraphsUseNauty`

(7.2-1).

gap> cycle := CycleDigraph(9); <digraph with 9 vertices, 9 edges> gap> G := AutomorphismGroup(cycle);; gap> IsCyclic(G) and Size(G) = 9; true gap> colours := [[1, 4, 7], [2, 5, 8], [3, 6, 9]];; gap> H := AutomorphismGroup(cycle, colours);; gap> Size(H); 3 gap> H = AutomorphismGroup(cycle, [1, 2, 3, 1, 2, 3, 1, 2, 3]); true gap> H = SubgroupByProperty(G, p -> OnTuplesSets(colours, p) = colours); true gap> IsTrivial(AutomorphismGroup(cycle, [1, 1, 2, 2, 2, 2, 2, 2, 2])); true gap> gr := Digraph([[2], [3, 3], [3], [2], [2]]); <multidigraph with 5 vertices, 6 edges> gap> G := AutomorphismGroup(gr, [1, 1, 2, 3, 1]); Group([ (1,2), (3,4) ]) gap> P1 := Projection(G, 1); 1st projection of Group([ (1,2), (3,4) ]) gap> P2 := Projection(G, 2); 2nd projection of Group([ (1,2), (3,4) ]) gap> DigraphVertices(gr); [ 1 .. 5 ] gap> Range(P1); Group([ (1,5) ]) gap> DigraphEdges(gr); [ [ 1, 2 ], [ 2, 3 ], [ 2, 3 ], [ 3, 3 ], [ 4, 2 ], [ 5, 2 ] ] gap> Range(P2); Group([ (2,3) ])

`‣ BlissCanonicalLabelling` ( digraph ) | ( attribute ) |

`‣ NautyCanonicalLabelling` ( digraph ) | ( attribute ) |

Returns: A permutation, or a list of two permutations.

A function ρ that maps a digraph to a digraph is a *canonical representative map* if the following two conditions hold for all digraphs G and H:

ρ(G) and G are isomorphic as digraphs; and

ρ(G)=ρ(H) if and only if G and H are isomorphic as digraphs.

A *canonical labelling* of a digraph G (under ρ) is an isomorphism of G onto its *canonical representative*, ρ(G). See `IsomorphismDigraphs`

(7.2-16) for more information about isomorphisms of digraphs.

`BlissCanonicalLabelling`

returns a canonical labelling of the digraph `digraph` found using bliss by Tommi Junttila and Petteri Kaski. `NautyCanonicalLabelling`

returns a canonical labelling of the digraph `digraph` found using nauty by Brendan McKay and Adolfo Piperno. Note that the canonical labellings returned by bliss and nauty are not usually the same (and may depend of the version used).

The form of the canonical labelling returned by `BlissCanonicalLabelling`

depends on whether `digraph` has multiple edges; see `IsMultiDigraph`

(6.1-8).

**for a digraph without multiple edges**If the digraph

`digraph`has no multiple edges, then the canonical labelling of`digraph`is given as a permutation of its vertices. The canonical representative of`digraph`can be created from`digraph`and its canonical labelling`p`

by using the operation`OnDigraphs`

(7.1-1):gap> OnDigraphs(digraph, p);

**for a multidigraph**The canonical labelling of the multidigraph

`digraph`is given as a pair`P`

of permutations. The first,`P[1]`

, is a permutation of the vertices of`digraph`. The second,`P[2]`

, is a permutation of the edges of`digraph`; it acts on the indices of the list`DigraphEdges(`

. The canonical representative of`digraph`)`digraph`can be created from`digraph`and its canonical labelling`P`

by using the operation`OnMultiDigraphs`

(7.1-2):gap> OnMultiDigraphs(digraph, P);

gap> digraph1 := DigraphFromDiSparse6String(".ImNS_AiB?qRN"); <digraph with 10 vertices, 8 edges> gap> BlissCanonicalLabelling(digraph1); (1,3,4)(2,10,6,7,9,8) gap> p := (1, 2, 7, 5)(3, 9)(6, 10, 8);; gap> digraph2 := OnDigraphs(digraph1, p); <digraph with 10 vertices, 8 edges> gap> digraph1 = digraph2; false gap> OnDigraphs(digraph1, BlissCanonicalLabelling(digraph1)) = > OnDigraphs(digraph2, BlissCanonicalLabelling(digraph2)); true gap> gr := DigraphFromDiSparse6String(".ImEk|O@SK?od"); <multidigraph with 10 vertices, 10 edges> gap> BlissCanonicalLabelling(gr); [ (1,9,7,5)(2,10,3), (1,6,9)(2,5,10,4,8)(3,7) ] gap> gr := Digraph([[2], [3, 3], [3], [2], [2]]); <multidigraph with 5 vertices, 6 edges> gap> BlissCanonicalLabelling(gr, [1, 2, 2, 1, 3]); [ (1,2,4), (1,2,6,4,3,5) ]

`‣ BlissCanonicalLabelling` ( digraph, colours ) | ( operation ) |

`‣ NautyCanonicalLabelling` ( digraph, colours ) | ( operation ) |

Returns: A permutation.

A function ρ that maps a coloured digraph to a coloured digraph is a *canonical representative map* if the following two conditions hold for all coloured digraphs G and H:

ρ(G) and G are isomorphic as coloured digraphs; and

ρ(G)=ρ(H) if and only if G and H are isomorphic as coloured digraphs.

A *canonical labelling* of a coloured digraph G (under ρ) is an isomorphism of G onto its *canonical representative*, ρ(G). See `IsomorphismDigraphs`

(7.2-17) for more information about isomorphisms of coloured digraphs.

A coloured digraph can be specified by its underlying digraph `digraph` and its colouring `colours`. Let `n`

be the number of vertices of `digraph`. The colouring `colours` may have one of the following two forms:

a list of

`n`

integers, where`colours``[i]`

is the colour of vertex`i`

, using the colours`[1 .. m]`

for some`m <= n`

; ora list of non-empty disjoint lists whose union is

`DigraphVertices(`

, such that`digraph`)`colours``[i]`

is the list of all vertices with colour`i`

.

If `digraph` and `colours` together form a coloured digraph, `BlissCanonicalLabelling`

returns a canonical labelling of the digraph `digraph` found using bliss by Tommi Junttila and Petteri Kaski. Similarly, `NautyCanonicalLabelling`

returns a canonical labelling of the digraph `digraph` found using nauty by Brendan McKay and Adolfo Piperno. Note that the canonical labellings returned by bliss and nauty are not usually the same (and may depend of the version used).

The form of the canonical labelling returned by `BlissCanonicalLabelling`

depends on whether `digraph` has multiple edges; see `IsMultiDigraph`

(6.1-8).

**for a digraph without multiple edges**If the digraph

`digraph`has no multiple edges, then the canonical labelling of`digraph`is given as a permutation of its vertices. The canonical representative of`digraph`can be created from`digraph`and its canonical labelling`p`

by using the operation`OnDigraphs`

(7.1-1):gap> OnDigraphs(digraph, p);

**for a multidigraph**The canonical labelling of the multidigraph

`digraph`is given as a pair`P`

of permutations. The first,`P[1]`

, is a permutation of the vertices of`digraph`. The second,`P[2]`

, is a permutation of the edges of`digraph`; it acts on the indices of the list`DigraphEdges(`

. The canonical representative of`digraph`)`digraph`can be created from`digraph`and its canonical labelling`P`

by using the operation`OnMultiDigraphs`

(7.1-2):gap> OnMultiDigraphs(digraph, P);

In either case, the colouring of the canonical representative can easily be constructed. A vertex `v`

(in `digraph`) has colour `i`

if and only if the vertex `v ^ p`

(in the canonical representative) has colour `i`

, where `p`

is the permutation of the canonical labelling that acts on the vertices of `digraph`. In particular, if `colours` has the first form that is described above, then the colouring of the canonical representative is given by:

gap> List(DigraphVertices(digraph), i -> colours[i / p]);

On the other hand, if `colours` has the second form above, then the canonical representative has colouring:

gap> OnTuplesSets(colours, p);

gap> digraph := DigraphFromDiSparse6String(".ImNS_AiB?qRN"); <digraph with 10 vertices, 8 edges> gap> colours := [[1, 2, 8, 9, 10], [3, 4, 5, 6, 7]];; gap> p := BlissCanonicalLabelling(digraph, colours); (2,3,7,10)(4,6,9,5,8) gap> OnDigraphs(digraph, p); <digraph with 10 vertices, 8 edges> gap> OnTuplesSets(colours, p); [ [ 1, 2, 3, 4, 5 ], [ 6, 7, 8, 9, 10 ] ] gap> colours := [1, 1, 1, 1, 2, 3, 1, 3, 2, 1];; gap> p := BlissCanonicalLabelling(digraph, colours); (2,3,4,6,10,5,8,9,7) gap> OnDigraphs(digraph, p); <digraph with 10 vertices, 8 edges> gap> List(DigraphVertices(digraph), i -> colours[i / p]); [ 1, 1, 1, 1, 1, 1, 2, 2, 3, 3 ]

`‣ BlissCanonicalDigraph` ( digraph ) | ( attribute ) |

`‣ NautyCanonicalDigraph` ( digraph ) | ( attribute ) |

Returns: A digraph.

The attribute `BlissCanonicalLabelling`

returns the canonical representative found by applying `BlissCanonicalLabelling`

(7.2-6). The digraph returned is canonical in the sense that

`BlissCanonicalDigraph(`

and`digraph`)`digraph`are isomorphic as digraphs; andIf

`gr`

is any digraph then`BlissCanonicalDigraph(gr)`

and`BlissCanonicalDigraph(`

are equal if and only if`digraph`)`gr`

and`digraph`are isomorphic as digraphs.

Analogously, the attribute `NautyCanonicalLabelling`

returns the canonical representative found by applying `NautyCanonicalLabelling`

(7.2-6).

gap> digraph := Digraph([[1], [2, 3], [3], [1, 2, 3]]); <digraph with 4 vertices, 7 edges> gap> canon := BlissCanonicalDigraph(digraph); <digraph with 4 vertices, 7 edges> gap> OutNeighbours(canon); [ [ 1 ], [ 2, 4 ], [ 1, 2, 4 ], [ 4 ] ]

`‣ DigraphGroup` ( digraph ) | ( attribute ) |

Returns: A permutation group.

If `digraph` was created knowing a subgroup of its automorphism group, then this group is stored in the attribute `DigraphGroup`

. If `digraph` is not created knowing a subgroup of its automorphism group, then `DigraphGroup`

returns the entire automorphism group of `digraph`.

Note that certain other constructor operations such as `CayleyDigraph`

(3.1-10), `BipartiteDoubleDigraph`

(3.3-31), and `DoubleDigraph`

(3.3-30), may not require a group as one of the arguments, but use the standard constructor method using a group, and hence set the `DigraphGroup`

attribute for the resulting digraph.

gap> n := 4;; gap> adj := function(x, y) > return (((x - y) mod n) = 1) or (((x - y) mod n) = n - 1); > end;; gap> group := CyclicGroup(IsPermGroup, n); Group([ (1,2,3,4) ]) gap> digraph := Digraph(group, [1 .. n], \^, adj); <digraph with 4 vertices, 8 edges> gap> HasDigraphGroup(digraph); true gap> DigraphGroup(digraph); Group([ (1,2,3,4) ]) gap> AutomorphismGroup(digraph); Group([ (2,4), (1,2)(3,4) ]) gap> ddigraph := DoubleDigraph(digraph); <digraph with 8 vertices, 32 edges> gap> HasDigraphGroup(ddigraph); true gap> DigraphGroup(ddigraph); Group([ (1,2,3,4)(5,6,7,8), (1,5)(2,6)(3,7)(4,8) ]) gap> AutomorphismGroup(ddigraph) = > Group([(6, 8), (5, 7), (4, 6), (3, 5), (2, 4), > (1, 2)(3, 4)(5, 6)(7, 8)]); true gap> digraph := Digraph([[2, 3], [], []]); <digraph with 3 vertices, 2 edges> gap> HasDigraphGroup(digraph); false gap> HasAutomorphismGroup(digraph); false gap> DigraphGroup(digraph); Group([ (2,3) ]) gap> HasAutomorphismGroup(digraph); true gap> group := DihedralGroup(8); <pc group of size 8 with 3 generators> gap> digraph := CayleyDigraph(group); <digraph with 8 vertices, 24 edges> gap> HasDigraphGroup(digraph); true gap> DigraphGroup(digraph); Group([ (1,2)(3,8)(4,6)(5,7), (1,3,4,7)(2,5,6,8), (1,4)(2,6)(3,7) (5,8) ])

`‣ DigraphOrbits` ( digraph ) | ( attribute ) |

Returns: A list of lists of integers.

`DigraphOrbits`

returns the orbits of the action of the `DigraphGroup`

(7.2-9) on the set of vertices of `digraph`.

gap> G := Group([(2, 3)(7, 8, 9), (1, 2, 3)(4, 5, 6)(8, 9)]);; gap> gr := EdgeOrbitsDigraph(G, [1, 2]); <digraph with 9 vertices, 6 edges> gap> DigraphOrbits(gr); [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]

`‣ DigraphOrbitReps` ( digraph ) | ( attribute ) |

Returns: A list of integers.

`DigraphOrbitReps`

returns a list of orbit representatives of the action of the `DigraphGroup`

(7.2-9) on the set of vertices of `digraph`.

gap> digraph := CayleyDigraph(AlternatingGroup(4)); <digraph with 12 vertices, 24 edges> gap> DigraphOrbitReps(digraph); [ 1 ] gap> digraph := DigraphFromDigraph6String("+I?OGg????A?Ci_o_@?"); <digraph with 10 vertices, 14 edges> gap> DigraphOrbitReps(digraph); [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

`‣ DigraphSchreierVector` ( digraph ) | ( attribute ) |

Returns: A list of integers.

`DigraphSchreierVector`

returns the so-called *Schreier vector* of the action of the `DigraphGroup`

(7.2-9) on the set of vertices of `digraph`. The Schreier vector is a list `sch`

of integers with length `DigraphNrVertices(`

where:`digraph`)

`sch[i] < 0:`

implies that

`i`

is an orbit representative and`DigraphOrbitReps(`

.`digraph`)[-sch[i]] = i`sch[i] > 0:`

implies that

`i / gens[sch[i]]`

is one step closer to the root (or representative) of the tree, where`gens`

is the generators of`DigraphGroup(`

.`digraph`)

gap> digraph := CayleyDigraph(AlternatingGroup(4)); <digraph with 12 vertices, 24 edges> gap> sch := DigraphSchreierVector(digraph); [ -1, 2, 2, 1, 1, 1, 1, 1, 2, 2, 2, 1 ] gap> DigraphOrbitReps(digraph); [ 1 ] gap> gens := GeneratorsOfGroup(DigraphGroup(digraph)); [ (1,5,7)(2,4,8)(3,6,9)(10,11,12), (1,2,3)(4,7,10)(5,9,11)(6,8,12) ] gap> 10 / gens[sch[10]]; 7 gap> 7 / gens[sch[7]]; 5 gap> 5 / gens[sch[5]]; 1

`‣ DigraphStabilizer` ( digraph, v ) | ( operation ) |

Returns: A permutation group.

`DigraphStabilizer`

returns the stabilizer of the vertex `v` under of the action of the `DigraphGroup`

(7.2-9) on the set of vertices of `digraph`.

gap> digraph := DigraphFromDigraph6String("+GUIQQWWXHHPg"); <digraph with 8 vertices, 24 edges> gap> DigraphStabilizer(digraph, 8); Group(()) gap> DigraphStabilizer(digraph, 2); Group(())

`‣ IsIsomorphicDigraph` ( digraph1, digraph2 ) | ( operation ) |

Returns: `true`

or `false`

.

This operation returns `true`

if there exists an isomorphism from the digraph `digraph1` to the digraph `digraph2`. See `IsomorphismDigraphs`

(7.2-16) for more information about isomorphisms of digraphs.

By default, an isomorphism is found using the canonical labellings of the digraphs obtained from bliss by Tommi Junttila and Petteri Kaski. If NautyTracesInterface is available, then nauty by Brendan Mckay and Adolfo Piperno can be used instead; see `DigraphsUseBliss`

(7.2-1), and `DigraphsUseNauty`

(7.2-1).

gap> digraph1 := CycleDigraph(4); <digraph with 4 vertices, 4 edges> gap> digraph2 := CycleDigraph(5); <digraph with 5 vertices, 5 edges> gap> IsIsomorphicDigraph(digraph1, digraph2); false gap> digraph2 := DigraphReverse(digraph1); <digraph with 4 vertices, 4 edges> gap> IsIsomorphicDigraph(digraph1, digraph2); true gap> digraph1 := DigraphFromDiSparse6String(".IiGdqrHiogeaF"); <multidigraph with 10 vertices, 10 edges> gap> digraph2 := DigraphFromDiSparse6String(".IiK`K@FFSouF_|^"); <multidigraph with 10 vertices, 10 edges> gap> IsIsomorphicDigraph(digraph1, digraph2); false gap> digraph1 := Digraph([[3], [], []]); <digraph with 3 vertices, 1 edge> gap> digraph2 := Digraph([[], [], [2]]); <digraph with 3 vertices, 1 edge> gap> IsIsomorphicDigraph(digraph1, digraph2); true

`‣ IsIsomorphicDigraph` ( digraph1, digraph2, colours1, colours2 ) | ( operation ) |

Returns: `true`

or `false`

.

This operation tests for isomorphism of coloured digraphs. A coloured digraph can be specified by its underlying digraph `digraph1` and its colouring `colours1`. Let `n`

be the number of vertices of `digraph1`. The colouring `colours1` may have one of the following two forms:

a list of

`n`

integers, where`colours``[i]`

is the colour of vertex`i`

, using the colours`[1 .. m]`

for some`m <= n`

; ora list of non-empty disjoint lists whose union is

`DigraphVertices(`

, such that`digraph`)`colours``[i]`

is the list of all vertices with colour`i`

.

If `digraph1` and `digraph2` are digraphs without multiple edges, and `colours1` and `colours2` are colourings of `digraph1` and `digraph2`, respectively, then this operation returns `true`

if there exists an isomorphism between these two coloured digraphs. See `IsomorphismDigraphs`

(7.2-17) for more information about isomorphisms of coloured digraphs.

By default, an isomorphism is found using the canonical labellings of the digraphs obtained from bliss by Tommi Junttila and Petteri Kaski. If NautyTracesInterface is available, then nauty by Brendan Mckay and Adolfo Piperno can be used instead; see `DigraphsUseBliss`

(7.2-1), and `DigraphsUseNauty`

(7.2-1).

gap> digraph1 := ChainDigraph(4); <digraph with 4 vertices, 3 edges> gap> digraph2 := ChainDigraph(3); <digraph with 3 vertices, 2 edges> gap> IsIsomorphicDigraph(digraph1, digraph2, > [[1, 4], [2, 3]], [[1, 2], [3]]); false gap> digraph2 := DigraphReverse(digraph1); <digraph with 4 vertices, 3 edges> gap> IsIsomorphicDigraph(digraph1, digraph2, > [1, 1, 1, 1], [1, 1, 1, 1]); true gap> IsIsomorphicDigraph(digraph1, digraph2, > [1, 2, 2, 1], [1, 2, 2, 1]); true gap> IsIsomorphicDigraph(digraph1, digraph2, > [1, 1, 2, 2], [1, 1, 2, 2]); false gap> digraph1 := Digraph([[2, 1, 2], [1, 2, 1]]); <multidigraph with 2 vertices, 6 edges> gap> IsIsomorphicDigraph(digraph1, digraph1, [2, 1], [1, 2]); true gap> IsIsomorphicDigraph(digraph1, digraph1, [1, 1], [1, 2]); false

`‣ IsomorphismDigraphs` ( digraph1, digraph2 ) | ( operation ) |

Returns: A permutation, or a pair of permutations, or `fail`

.

This operation returns an isomorphism between the digraphs `digraph1` and `digraph2` if one exists, else this operation returns `fail`

.

**for digraphs without multiple edges**An

*isomorphism*from a digraph`digraph1`to a digraph`digraph2`is a bijection`p`

from the vertices of`digraph1`to the vertices of`digraph2`with the following property: for all vertices`i`

and`j`

of`digraph1`,`[i, j]`

is an edge of`digraph1`if and only if`[i ^ p, j ^ p]`

is an edge of`digraph2`.If there exists such an isomorphism, then this operation returns one. The form of this isomorphism is a permutation

`p`

of the vertices of`digraph1`such that`OnDigraphs(`

.`digraph1`, p) = digraph2**for multidigraphs**An

*isomorphism*from a multidigraph`digraph1`to a multidigraph`digraph2`is a bijection`P[1]`

from the vertices of`digraph1`to the vertices of`digraph2`and a bijection`P[2]`

from the indices of edges of`digraph1`to the indices of edges of`digraph2`with the following property:`[i, j]`

is the`k`

th edge of`digraph1`if and only if`[i ^ P[1], j ^ P[1]]`

is the`(k ^ P[2])`

th edge of`digraph2`.If there exists such an isomorphism, then this operation returns one. The form of this isomorphism is a pair of permutations

`P`

-– where the first is a permutation of the vertices of`digraph1`and the second is a permutation of the indices of`DigraphEdges(`

–- such that`digraph1`)`OnMultiDigraphs(`

.`digraph1`, P) =`digraph2`

By default, an isomorphism is found using the canonical labellings of the digraphs obtained from bliss by Tommi Junttila and Petteri Kaski. If NautyTracesInterface is available, then nauty by Brendan Mckay and Adolfo Piperno can be used instead; see `DigraphsUseBliss`

(7.2-1), and `DigraphsUseNauty`

(7.2-1).

gap> digraph1 := CycleDigraph(4); <digraph with 4 vertices, 4 edges> gap> digraph2 := CycleDigraph(5); <digraph with 5 vertices, 5 edges> gap> IsomorphismDigraphs(digraph1, digraph2); fail gap> digraph1 := CompleteBipartiteDigraph(10, 5); <digraph with 15 vertices, 100 edges> gap> digraph2 := CompleteBipartiteDigraph(5, 10); <digraph with 15 vertices, 100 edges> gap> p := IsomorphismDigraphs(digraph1, digraph2); (1,6,11)(2,7,12)(3,8,13)(4,9,14)(5,10,15) gap> OnDigraphs(digraph1, p) = digraph2; true gap> digraph1 := DigraphFromDiSparse6String(".ImNS_?DSE@ce[~"); <multidigraph with 10 vertices, 10 edges> gap> digraph2 := DigraphFromDiSparse6String(".IkOlQefi_kgOf"); <multidigraph with 10 vertices, 10 edges> gap> IsomorphismDigraphs(digraph1, digraph2); [ (1,9,5,3,10,6,4,7,2), (1,8,6,3,7)(2,9,4,10,5) ] gap> digraph1 := DigraphByEdges([[7, 10], [7, 10]], 10); <multidigraph with 10 vertices, 2 edges> gap> digraph2 := DigraphByEdges([[2, 3], [2, 3]], 10); <multidigraph with 10 vertices, 2 edges> gap> IsomorphismDigraphs(digraph1, digraph2); [ (2,4,6,8,9,10,3,5,7), () ]

`‣ IsomorphismDigraphs` ( digraph1, digraph2, colours1, colours2 ) | ( operation ) |

Returns: A permutation, or `fail`

.

This operation searches for an isomorphism between coloured digraphs. A coloured digraph can be specified by its underlying digraph `digraph1` and its colouring `colours1`. Let `n`

be the number of vertices of `digraph1`. The colouring `colours1` may have one of the following two forms:

`n`

integers, where`colours``[i]`

is the colour of vertex`i`

, using the colours`[1 .. m]`

for some`m <= n`

; or`DigraphVertices(`

, such that`digraph`)`colours``[i]`

is the list of all vertices with colour`i`

.

An *isomorphism* between coloured digraphs is an isomorphism between the underlying digraphs that preserves the colourings. See `IsomorphismDigraphs`

(7.2-16) for more information about isomorphisms of digraphs. More precisely, let `f`

be an isomorphism of digraphs from the digraph `digraph1` (with colouring `colours1`) to the digraph `digraph2` (with colouring `colours2`), and let `p`

be the permutation of the vertices of `digraph1` that corresponds to `f`

. Then `f`

preserves the colourings of `digraph1` and `digraph2` – and hence is an isomorphism of coloured digraphs – if

for all vertices `colours1`[i] = `colours2`[i ^ p]`i`

in `digraph1`.

This operation returns such an isomorphism if one exists, else it returns `fail`

.

`DigraphsUseBliss`

(7.2-1), and `DigraphsUseNauty`

(7.2-1).

gap> digraph1 := ChainDigraph(4); <digraph with 4 vertices, 3 edges> gap> digraph2 := ChainDigraph(3); <digraph with 3 vertices, 2 edges> gap> IsomorphismDigraphs(digraph1, digraph2, > [[1, 4], [2, 3]], [[1, 2], [3]]); fail gap> digraph2 := DigraphReverse(digraph1); <digraph with 4 vertices, 3 edges> gap> colours1 := [1, 1, 1, 1];; gap> colours2 := [1, 1, 1, 1];; gap> p := IsomorphismDigraphs(digraph1, digraph2, colours1, colours2); (1,4)(2,3) gap> OnDigraphs(digraph1, p) = digraph2; true gap> List(DigraphVertices(digraph1), i -> colours1[i ^ p]) = colours2; true gap> colours1 := [1, 1, 2, 2];; gap> colours2 := [2, 2, 1, 1];; gap> p := IsomorphismDigraphs(digraph1, digraph2, colours1, colours2); (1,4)(2,3) gap> OnDigraphs(digraph1, p) = digraph2; true gap> List(DigraphVertices(digraph1), i -> colours1[i ^ p]) = colours2; true gap> IsomorphismDigraphs(digraph1, digraph2, > [1, 1, 2, 2], [1, 1, 2, 2]); fail gap> digraph1 := Digraph([[2, 2], [2], [1]]); <multidigraph with 3 vertices, 4 edges> gap> digraph2 := Digraph([[1], [1, 1], [2]]); <multidigraph with 3 vertices, 4 edges> gap> IsomorphismDigraphs(digraph1, digraph2, [1, 2, 2], [2, 1, 2]); [ (1,2), (1,2,3) ]

`‣ RepresentativeOutNeighbours` ( digraph ) | ( attribute ) |

Returns: An immutable list of immutable lists.

This function returns the list `out`

of *out-neighbours* of each representative of the orbits of the action of `DigraphGroup`

(7.2-9) on the vertex set of the digraph `digraph`.

More specifically, if `reps`

is the list of orbit representatives, then a vertex `j`

appears in `out[i]`

each time there exists an edge with source `reps[i]`

and range `j`

in `digraph`.

If `DigraphGroup`

(7.2-9) is trivial, then `OutNeighbours`

(5.2-5) is returned.

gap> digraph := Digraph([ > [2, 1, 3, 4, 5], [3, 5], [2], [1, 2, 3, 5], [1, 2, 3, 4]]); <digraph with 5 vertices, 16 edges> gap> DigraphGroup(digraph); Group(()) gap> RepresentativeOutNeighbours(digraph); [ [ 2, 1, 3, 4, 5 ], [ 3, 5 ], [ 2 ], [ 1, 2, 3, 5 ], [ 1, 2, 3, 4 ] ] gap> digraph := DigraphFromDigraph6String("+GUIQQWWXHHPg"); <digraph with 8 vertices, 24 edges> gap> DigraphGroup(digraph); Group([ (1,2)(3,4)(5,6)(7,8), (1,3,2,4)(5,7,6,8), (1,5)(2,6)(3,8) (4,7) ]) gap> RepresentativeOutNeighbours(digraph); [ [ 2, 3, 5 ] ]

`‣ IsDigraphIsomorphism` ( src, ran, x ) | ( operation ) |

`‣ IsDigraphAutomorphism` ( digraph, x ) | ( operation ) |

Returns: `true`

or `false`

.

`IsDigraphIsomorphism`

returns `true`

if the permutation or transformation `x` is an isomorphism from the digraph `src` to the digraph `ran`.

`IsDigraphAutomorphism`

returns `true`

if the permutation or transformation `x` is an automorphism of the digraph `digraph`.

A permutation or transformation `x` is an *isomorphism* from a digraph `src` to a digraph `ran` if the following hold:

`x`is a bijection from the vertices of`src`to those of`ran`;`[u ^`

is an edge of`x`, v ^`x`]`ran`if and only if`[u, v]`

is an edge of`src`; and`x`fixes every`i`

which is not a vertex of`src`.

See also `AutomorphismGroup`

(7.2-2).

For some digraphs, it can be faster to use `IsDigraphAutomorphism`

than to test membership in the automorphism group of `digraph`.

gap> src := Digraph([[1], [1, 2], [1, 3]]); <digraph with 3 vertices, 5 edges> gap> IsDigraphAutomorphism(src, (1, 2, 3)); false gap> IsDigraphAutomorphism(src, (2, 3)); true gap> IsDigraphAutomorphism(src, (2, 3)(4, 5)); false gap> IsDigraphAutomorphism(src, (1, 4)); false gap> IsDigraphAutomorphism(src, ()); true gap> ran := Digraph([[2, 1], [2], [2, 3]]); <digraph with 3 vertices, 5 edges> gap> IsDigraphIsomorphism(src, ran, (1, 2)); true gap> IsDigraphIsomorphism(ran, src, (1, 2)); true gap> IsDigraphIsomorphism(ran, src, (1, 2)); true gap> IsDigraphIsomorphism(src, Digraph([[3], [1, 3], [2]]), (1, 2, 3)); false

The following methods exist to find homomorphisms between digraphs. If an argument to one of these methods is a digraph with multiple edges, then the multiplicity of edges will be ignored in order to perform the calculation; the digraph will be treated as if it has no multiple edges.

`‣ HomomorphismDigraphsFinder` ( gr1, gr2, hook, user_param, limit, hint, injective, image, map, list1, list2 ) | ( function ) |

Returns: The argument `user_param`.

This function finds homomorphisms from the graph `gr1` to the graph `gr2` subject to the conditions imposed by the other arguments as described below.

If `f`

and `g`

are homomorphisms found by `HomomorphismDigraphsFinder`

, then `f`

cannot be obtained from `g`

by right multiplying by an automorphism of `gr2`.

`hook`This argument should be a function or

`fail`

.If

`hook`is a function, then it should have two arguments`user_param`(see below) and a transformation`t`

. The function

is called every time a new homomorphism`hook`(`user_param`, t)`t`

is found by`HomomorphismDigraphsFinder`

.If

`hook`is`fail`

, then a default function is used which simply adds every new homomorphism found by`HomomorphismDigraphsFinder`

to`user_param`, which must be a list in this case.`user_param`If

`hook`is a function, then`user_param`can be any**GAP**object. The object`user_param`is used as the first argument for the function`hook`. For example,`user_param`might be a transformation semigroup, and

might set`hook`(`user_param`, t)`user_param`to be the closure of`user_param`and`t`

.If the value of

`hook`is`fail`

, then the value of`user_param`must be a list.`limit`This argument should be a positive integer or

`infinity`

.`HomomorphismDigraphsFinder`

will return after it has found`limit`homomorphisms or the search is complete.`hint`This argument should be a positive integer or

`fail`

.If

`hint`is a positive integer, then only homorphisms of rank`hint`are found.If

`hint`is`fail`

, then no restriction is put on the rank of homomorphisms found.`injective`This argument should be

`true`

or`false`

. If it is`true`

, then only injective homomorphisms are found, and if it is`false`

there are no restrictions imposed by this argument.`image`This argument should be a subset of the vertices of the graph

`gr2`.`HomomorphismDigraphsFinder`

only finds homomorphisms from`gr1`to the subgraph of`gr2`induced by the vertices`image`.`map`This argument should be a partial map from

`gr1`to`gr2`, that is, a (not necessarily dense) list of vertices of the graph`gr2`of length no greater than the number vertices in the graph`gr1`.`HomomorphismDigraphsFinder`

only finds homomorphisms extending`map`(if any).`list1`This should be a list representing possible colours of vertices in the digraph

`gr1`; see`AutomorphismGroup`

(7.2-5) for details of the permissible values for this argument.`list2`This should be a list representing possible colours of vertices in the digraph

`gr2`; see`AutomorphismGroup`

(7.2-5) for details of the permissible values for this argument.

gap> gr := ChainDigraph(10); <digraph with 10 vertices, 9 edges> gap> gr := DigraphSymmetricClosure(gr); <digraph with 10 vertices, 18 edges> gap> HomomorphismDigraphsFinder(gr, gr, fail, [], infinity, 2, false, > [3, 4], [], fail, fail); [ Transformation( [ 3, 4, 3, 4, 3, 4, 3, 4, 3, 4 ] ), Transformation( [ 4, 3, 4, 3, 4, 3, 4, 3, 4, 3 ] ) ] gap> gr2 := CompleteDigraph(6);; gap> HomomorphismDigraphsFinder(gr, gr2, fail, [], 1, fail, false, > [1 .. 6], [1, 2, 1], fail, fail); [ Transformation( [ 1, 2, 1, 3, 4, 5, 6, 1, 2, 1 ] ) ] gap> func := function(user_param, t) > Add(user_param, t * user_param[1]); > end;; gap> HomomorphismDigraphsFinder(gr, gr2, func, [Transformation([2, 2])], > 3, fail, false, [1 .. 6], [1, 2, 1], fail, fail); [ Transformation( [ 2, 2 ] ), Transformation( [ 2, 2, 2, 3, 4, 5, 6, 2, 2, 2 ] ), Transformation( [ 2, 2, 2, 3, 4, 5, 6, 2, 2, 3 ] ), Transformation( [ 2, 2, 2, 3, 4, 5, 6, 2, 2, 4 ] ) ]

`‣ DigraphHomomorphism` ( digraph1, digraph2 ) | ( operation ) |

Returns: A transformation, or `fail`

.

A homomorphism from `digraph1` to `digraph2` is a mapping from the vertex set of `digraph1` to a subset of the vertices of `digraph2`, such that every pair of vertices `[i,j]`

which has an edge `i->j`

is mapped to a pair of vertices `[a,b]`

which has an edge `a->b`

. Note that non adjacent vertices can still be mapped onto adjacent ones.

`DigraphHomomorphism`

returns a single homomorphism between `digraph1` and `digraph2` if it exists, otherwise it returns `fail`

.

gap> gr1 := ChainDigraph(3);; gap> gr2 := Digraph([[3, 5], [2], [3, 1], [], [4]]); <digraph with 5 vertices, 6 edges> gap> DigraphHomomorphism(gr1, gr1); IdentityTransformation gap> DigraphHomomorphism(gr1, gr2); Transformation( [ 1, 3, 1 ] )

`‣ HomomorphismsDigraphs` ( digraph1, digraph2 ) | ( operation ) |

`‣ HomomorphismsDigraphsRepresentatives` ( digraph1, digraph2 ) | ( operation ) |

Returns: A list of transformations.

`HomomorphismsDigraphsRepresentatives`

finds every `DigraphHomomorphism`

(7.3-2) between `digraph1` and `digraph2`, up to right multiplication by an element of the `AutomorphismGroup`

(7.2-2) of `digraph2`. In other words, every homomorphism `f`

between `digraph1` and `digraph2` can be written as the composition `f = g * x`

, where `g`

is one of the `HomomorphismsDigraphsRepresentatives`

and `x`

is an automorphism of `digraph2`.

`HomomorphismsDigraphs`

returns all homomorphisms between `digraph1` and `digraph2`.

gap> gr1 := ChainDigraph(3);; gap> gr2 := Digraph([[3, 5], [2], [3, 1], [], [4]]); <digraph with 5 vertices, 6 edges> gap> HomomorphismsDigraphs(gr1, gr2); [ Transformation( [ 1, 3, 1 ] ), Transformation( [ 1, 3, 3 ] ), Transformation( [ 1, 5, 4, 4, 5 ] ), Transformation( [ 2, 2, 2 ] ), Transformation( [ 3, 1, 3 ] ), Transformation( [ 3, 1, 5, 4, 5 ] ), Transformation( [ 3, 3, 1 ] ), Transformation( [ 3, 3, 3 ] ) ] gap> HomomorphismsDigraphsRepresentatives(gr1, CompleteDigraph(3)); [ IdentityTransformation, Transformation( [ 1, 2, 1 ] ) ]

`‣ DigraphMonomorphism` ( digraph1, digraph2 ) | ( operation ) |

Returns: A transformation, or `fail`

.

`DigraphMonomorphism`

returns a single *injective* `DigraphHomomorphism`

(7.3-2) between `digraph1` and `digraph2` if one exists, otherwise it returns `fail`

.

gap> gr1 := ChainDigraph(3);; gap> gr2 := Digraph([[3, 5], [2], [3, 1], [], [4]]); <digraph with 5 vertices, 6 edges> gap> DigraphMonomorphism(gr1, gr1); IdentityTransformation gap> DigraphMonomorphism(gr1, gr2); Transformation( [ 1, 5, 4, 4, 5 ] )

`‣ MonomorphismsDigraphs` ( digraph1, digraph2 ) | ( operation ) |

`‣ MonomorphismsDigraphsRepresentatives` ( digraph1, digraph2 ) | ( operation ) |

Returns: A list of transformations.

These operations behave the same as `HomomorphismsDigraphs`

(7.3-3) and `HomomorphismsDigraphsRepresentatives`

(7.3-3), expect they only return *injective* homomorphisms.

gap> gr1 := ChainDigraph(3);; gap> gr2 := Digraph([[3, 5], [2], [3, 1], [], [4]]); <digraph with 5 vertices, 6 edges> gap> MonomorphismsDigraphs(gr1, gr2); [ Transformation( [ 1, 5, 4, 4, 5 ] ), Transformation( [ 3, 1, 5, 4, 5 ] ) ] gap> MonomorphismsDigraphsRepresentatives(gr1, CompleteDigraph(3)); [ IdentityTransformation ]

`‣ DigraphEpimorphism` ( digraph1, digraph2 ) | ( operation ) |

Returns: A transformation, or `fail`

.

`DigraphEpimorphism`

returns a single *surjective* `DigraphHomomorphism`

(7.3-2) between `digraph1` and `digraph2` if one exists, otherwise it returns `fail`

.

gap> gr1 := DigraphReverse(ChainDigraph(4)); <digraph with 4 vertices, 3 edges> gap> gr2 := DigraphRemoveEdge(CompleteDigraph(3), [1, 2]); <digraph with 3 vertices, 5 edges> gap> DigraphEpimorphism(gr2, gr1); fail gap> DigraphEpimorphism(gr1, gr2); Transformation( [ 1, 2, 3, 1 ] )

`‣ EpimorphismsDigraphs` ( digraph1, digraph2 ) | ( operation ) |

`‣ EpimorphismsDigraphsRepresentatives` ( digraph1, digraph2 ) | ( operation ) |

Returns: A list of transformations.

These operations behave the same as `HomomorphismsDigraphs`

(7.3-3) and `HomomorphismsDigraphsRepresentatives`

(7.3-3), expect they only return *surjective* homomorphisms.

gap> gr1 := DigraphReverse(ChainDigraph(4)); <digraph with 4 vertices, 3 edges> gap> gr2 := DigraphSymmetricClosure(CycleDigraph(3)); <digraph with 3 vertices, 6 edges> gap> EpimorphismsDigraphsRepresentatives(gr1, gr2); [ Transformation( [ 1, 2, 3, 1 ] ), Transformation( [ 1, 2, 3, 2 ] ), Transformation( [ 1, 2, 1, 3 ] ) ] gap> EpimorphismsDigraphs(gr1, gr2); [ Transformation( [ 1, 2, 1, 3 ] ), Transformation( [ 1, 2, 3, 1 ] ), Transformation( [ 1, 2, 3, 2 ] ), Transformation( [ 1, 3, 1, 2 ] ), Transformation( [ 1, 3, 2, 1 ] ), Transformation( [ 1, 3, 2, 3 ] ), Transformation( [ 2, 1, 2, 3 ] ), Transformation( [ 2, 1, 3, 1 ] ), Transformation( [ 2, 1, 3, 2 ] ), Transformation( [ 2, 3, 1, 2 ] ), Transformation( [ 2, 3, 1, 3 ] ), Transformation( [ 2, 3, 2, 1 ] ), Transformation( [ 3, 1, 2, 1 ] ), Transformation( [ 3, 1, 2, 3 ] ), Transformation( [ 3, 1, 3, 2 ] ), Transformation( [ 3, 2, 1, 2 ] ), Transformation( [ 3, 2, 1, 3 ] ), Transformation( [ 3, 2, 3, 1 ] ) ]

`‣ GeneratorsOfEndomorphismMonoid` ( digraph[, colors][, limit] ) | ( function ) |

`‣ GeneratorsOfEndomorphismMonoidAttr` ( digraph ) | ( attribute ) |

Returns: A list of transformations.

An endomorphism of `digraph` is a homomorphism `DigraphHomomorphism`

(7.3-2) from `digraph` back to itself. `GeneratorsOfEndomorphismMonoid`

, called with a single argument, returns a generating set for the monoid of all endomorphisms of `digraph`.

If the `colors` argument is specified, then `GeneratorsOfEndomorphismMonoid`

will return a generating set for the monoid of endomorphisms which respect the given colouring. The colouring `colors` can be in one of two forms:

A list of positive integers of size the number of vertices of

`digraph`, where`colors``[i]`

is the colour of vertex`i`

.A list of lists, such that

`colors``[i]`

is a list of all vertices with colour`i`

.

If the `limit` argument is specified, then it will return only the first `limit` homomorphisms, where `limit` must be a positive integer or `infinity`

.

gap> gr := Digraph(List([1 .. 3], x -> [1 .. 3]));; gap> GeneratorsOfEndomorphismMonoid(gr); [ Transformation( [ 1, 3, 2 ] ), Transformation( [ 2, 1 ] ), IdentityTransformation, Transformation( [ 1, 2, 1 ] ), Transformation( [ 1, 2, 2 ] ), Transformation( [ 1, 1, 2 ] ), Transformation( [ 1, 1, 1 ] ) ] gap> GeneratorsOfEndomorphismMonoid(gr, 3); [ Transformation( [ 1, 3, 2 ] ), Transformation( [ 2, 1 ] ), IdentityTransformation ] gap> gr := CompleteDigraph(3);; gap> GeneratorsOfEndomorphismMonoid(gr); [ Transformation( [ 1, 3, 2 ] ), Transformation( [ 2, 1 ] ), IdentityTransformation ] gap> GeneratorsOfEndomorphismMonoid(gr, [1, 2, 2]); [ Transformation( [ 1, 3, 2 ] ), IdentityTransformation ] gap> GeneratorsOfEndomorphismMonoid(gr, [[1], [2, 3]]); [ Transformation( [ 1, 3, 2 ] ), IdentityTransformation ]

`‣ DigraphColouring` ( digraph, n ) | ( operation ) |

`‣ DigraphColoring` ( digraph, n ) | ( operation ) |

`‣ DigraphColouring` ( digraph ) | ( attribute ) |

`‣ DigraphColoring` ( digraph ) | ( attribute ) |

Returns: A transformation, or `fail`

.

A *proper colouring* of a digraph is a labelling of its vertices in such a way that adjacent vertices have different labels. A *proper n-colouring* is a proper colouring that uses exactly

`n`

colours. Equivalently, a proper (`n`

-)colouring of a digraph can be defined to be a `DigraphEpimorphism`

(7.3-6) from a digraph onto the complete digraph (with `n`

vertices); see `CompleteDigraph`

(3.5-2). Note that a digraph with loops (`DigraphHasLoops`

(6.1-1)) does not have a proper `n`

-colouring for any value `n`

.If `digraph` is a digraph and `n` is a non-negative integer, then `DigraphColouring(`

returns an epimorphism from `digraph`, `n`)`digraph` onto the complete digraph with `n` vertices if one exists, else it returns `fail`

.

If the optional second argument `n` is not provided, then `DigraphColouring`

uses a greedy algorithm to obtain some proper colouring of `digraph`, which may not use the minimal number of colours.

Note that a digraph with at least two vertices has a 2-colouring if and only if it is bipartite, see `IsBipartiteDigraph`

(6.1-3).

gap> DigraphColouring(CompleteDigraph(5), 4); fail gap> DigraphColouring(ChainDigraph(10), 1); fail gap> gr := ChainDigraph(10);; gap> t := DigraphColouring(gr, 2); Transformation( [ 1, 2, 1, 2, 1, 2, 1, 2, 1, 2 ] ) gap> ForAll(DigraphEdges(gr), e -> e[1] ^ t <> e[2] ^ t); true gap> DigraphColouring(gr); Transformation( [ 1, 2, 1, 2, 1, 2, 1, 2, 1, 2 ] )

`‣ DigraphEmbedding` ( digraph1, digraph2 ) | ( operation ) |

Returns: A transformation, or `fail`

.

An embedding of a digraph `digraph1` into another digraph `digraph2` is a `DigraphMonomorphism`

(7.3-4) from `digraph1` to `digraph2` which has the additional property that a pair of vertices `[i, j]`

which have no edge `i -> j`

in `digraph1` are mapped to a pair of vertices `[a, b]`

which have no edge `a->b`

in `digraph2`.

In other words, an embedding `t`

is an isomorphism from `digraph1` to the `InducedSubdigraph`

(3.3-2) of `digraph2` on the image of `t`

.

`DigraphEmbedding`

returns a single embedding if one exists, otherwise it returns `fail`

.

gap> gr := ChainDigraph(3); <digraph with 3 vertices, 2 edges> gap> DigraphEmbedding(gr, CompleteDigraph(4)); fail gap> DigraphEmbedding(gr, Digraph([[3], [1, 4], [1], [3]])); Transformation( [ 2, 4, 3, 4 ] )

`‣ ChromaticNumber` ( digraph ) | ( attribute ) |

Returns: A non-negative integer.

A *proper colouring* of a digraph is a labelling of its vertices in such a way that adjacent vertices have different labels. Equivalently, a proper digraph colouring can be defined to be a `DigraphEpimorphism`

(7.3-6) from a digraph onto a complete digraph.

If `digraph` is a digraph without loops (see `DigraphHasLoops`

(6.1-1), then `ChromaticNumber`

returns the least non-negative integer `n`

such that there is a proper colouring of `digraph` with `n`

colours. In other words, for a digraph with at least one vertex, `ChromaticNumber`

returns the least number `n`

such that `DigraphColouring(`

does not return `digraph`, n)`fail`

. See `DigraphColouring`

(7.3-9).

gap> ChromaticNumber(NullDigraph(10)); 1 gap> ChromaticNumber(CompleteDigraph(10)); 10 gap> ChromaticNumber(CompleteBipartiteDigraph(5, 5)); 2 gap> ChromaticNumber(Digraph([[], [3], [5], [2, 3], [4]])); 3 gap> ChromaticNumber(NullDigraph(0)); 0

`‣ IsDigraphHomomorphism` ( src, ran, x ) | ( operation ) |

`‣ IsDigraphEpimorphism` ( src, ran, x ) | ( operation ) |

`‣ IsDigraphMonomorphism` ( src, ran, x ) | ( operation ) |

`‣ IsDigraphEndomorphism` ( digraph, x ) | ( operation ) |

Returns: `true`

or `false`

.

`IsDigraphHomomorphism`

returns `true`

if the permutation or transformation `x` is a homomorphism from the digraph `src` to the digraph `ran`.

`IsDigraphEpimorphism`

returns `true`

if the permutation or transformation `x` is a surjective homomorphism from the digraph `src` to the digraph `ran`.

`IsDigraphMonomorphism`

returns `true`

if the permutation or transformation `x` is an injective homomorphism from the digraph `src` to the digraph `ran`.

`IsDigraphEndomorphism`

returns `true`

if the permutation or transformation `x` is an endomorphism of the digraph `digraph`.

A permutation or transformation `x` is a *homomorphism* from a digraph `src` to a digraph `ran` if the following hold:

`[u ^`

is an edge of`x`, v ^`x`]`ran`whenever`[u, v]`

is an edge of`src`; and`x`fixes every`i`

which is not a vertex of`src`.

See also `GeneratorsOfEndomorphismMonoid`

(7.3-8).

gap> src := Digraph([[1], [1, 2], [1, 3]]); <digraph with 3 vertices, 5 edges> gap> ran := Digraph([[1], [1, 2]]); <digraph with 2 vertices, 3 edges> gap> IsDigraphHomomorphism(src, ran, Transformation([1, 2, 2])); true gap> IsDigraphHomomorphism(src, ran, Transformation([2, 1, 2])); false gap> IsDigraphHomomorphism(src, ran, Transformation([3, 3, 3])); false gap> IsDigraphHomomorphism(src, src, Transformation([3, 3, 3])); true gap> IsDigraphEndomorphism(src, Transformation([3, 3, 3])); true gap> IsDigraphEpimorphism(src, ran, Transformation([3, 3, 3])); false gap> IsDigraphMonomorphism(src, ran, Transformation([1, 2, 2])); false gap> IsDigraphEpimorphism(src, ran, Transformation([1, 2, 2])); true gap> IsDigraphMonomorphism(ran, src, ()); true

`‣ IsDigraphEmbedding` ( src, ran, x ) | ( operation ) |

Returns: `true`

or `false`

.

`IsDigraphEmbedding`

returns `true`

if the permutation or transformation `x` is a embedding of the digraph `src` into the digraph `ran`.

A permutation or transformation `x` is a *embedding* of a digraph `src` into a digraph `ran` if `x` is a monomorphism from `src` to `ran` and the inverse of `x` is a monomorphism from the subdigraph of `ran` induced by the image of `x` to `src`. See also `IsDigraphHomomorphism`

(7.3-12).

gap> src := Digraph([[1], [1, 2]]); <digraph with 2 vertices, 3 edges> gap> ran := Digraph([[1], [1, 2], [1, 3]]); <digraph with 3 vertices, 5 edges> gap> IsDigraphMonomorphism(src, ran, ()); true gap> IsDigraphEmbedding(src, ran, ()); true gap> ran := Digraph([[1, 2], [1, 2], [1, 3]]); <digraph with 3 vertices, 6 edges> gap> IsDigraphMonomorphism(src, ran, IdentityTransformation); true gap> IsDigraphEmbedding(src, ran, IdentityTransformation); false

generated by GAPDoc2HTML