7 Homomorphisms

7.2 Isomorphisms, and Canonical labellings

7.2-1 AutomorphismGroup

7.2-2 AutomorphismGroup

7.2-3 DigraphCanonicalLabelling

7.2-4 DigraphCanonicalLabelling

7.2-5 DigraphGroup

7.2-6 DigraphOrbits

7.2-7 DigraphOrbitReps

7.2-8 DigraphSchreierVector

7.2-9 DigraphStabilizer

7.2-10 IsIsomorphicDigraph

7.2-11 IsIsomorphicDigraph

7.2-12 IsomorphismDigraphs

7.2-13 IsomorphismDigraphs

7.2-14 RepresentativeOutNeighbours

7.2-1 AutomorphismGroup

7.2-2 AutomorphismGroup

7.2-3 DigraphCanonicalLabelling

7.2-4 DigraphCanonicalLabelling

7.2-5 DigraphGroup

7.2-6 DigraphOrbits

7.2-7 DigraphOrbitReps

7.2-8 DigraphSchreierVector

7.2-9 DigraphStabilizer

7.2-10 IsIsomorphicDigraph

7.2-11 IsIsomorphicDigraph

7.2-12 IsomorphismDigraphs

7.2-13 IsomorphismDigraphs

7.2-14 RepresentativeOutNeighbours

`‣ 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 := DigraphCanonicalLabelling(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 ] ]

`‣ 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-12) 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`)

The automorphism group is found using bliss by Tommi Junttila and Petteri Kaski.

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> StructureDescription(G); "C2 x S4" 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> StructureDescription(G); "C9" 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) ])

`‣ 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-1), and see `IsomorphismDigraphs`

(7.2-13) 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`)

The automorphism group is found using bliss by Tommi Junttila and Petteri Kaski.

gap> cycle := CycleDigraph(9); <digraph with 9 vertices, 9 edges> gap> G := AutomorphismGroup(cycle);; gap> StructureDescription(G); "C9" gap> colours := [[1, 4, 7], [2, 5, 8], [3, 6, 9]];; gap> H := AutomorphismGroup(cycle, colours);; gap> StructureDescription(H); "C3" 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) ])

`‣ DigraphCanonicalLabelling` ( 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-12) for more information about isomorphisms of digraphs.

The attribute `DigraphCanonicalLabelling`

returns a canonical labelling of the digraph `digraph`. The form of the canonical labelling returned by `DigraphCanonicalLabelling`

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);

The canonical labelling is found using bliss by Tommi Junttila and Petteri Kaski.

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

`‣ DigraphCanonicalLabelling` ( 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-13) 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, then the operation `DigraphCanonicalLabelling`

returns a canonical labelling of the coloured digraph. The form of the canonical labelling returned by `DigraphCanonicalLabelling`

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);

The canonical labelling is found using bliss by Tommi Junttila and Petteri Kaski.

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 := DigraphCanonicalLabelling(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 := DigraphCanonicalLabelling(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 ]

`‣ 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) ]) 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-5) 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-5) 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-5) 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-5) 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-12) for more information about isomorphisms of digraphs.

This operation uses the canonical labelling of the digraphs found with bliss by Tommi Junttila and Petteri Kaski.

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-13) for more information about isomorphisms of coloured digraphs.

This operation uses the canonical labelling of the digraphs found with bliss by Tommi Junttila and Petteri Kaski.

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`

This operation uses the canonical labelling of the digraphs found with bliss by Tommi Junttila and Petteri Kaski.

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

.

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-5) 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-5) 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 ] ]

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 ) | ( 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 `HomomorphismGraphsFinder`

, 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`HomomorphismGraphsFinder`

.If

`hook`is`fail`

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

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`

.`HomomorphismGraphsFinder`

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`.`HomomorphismGraphsFinder`

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`.`HomomorphismGraphsFinder`

only finds homomorphisms extending`map`(if any).

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-1) 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 it 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

generated by GAPDoc2HTML