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

7 Homomorphisms
 7.1 Acting on digraphs
 7.2 Isomorphisms, and Canonical labellings
 7.3 Homomorphisms of digraphs

7 Homomorphisms

7.1 Acting on digraphs

7.1-1 OnDigraphs
‣ 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

7.1-2 OnMultiDigraphs
‣ 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(digraph, perm)=OnMultiDigraphs(digraph, [perm, ()]) where 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 ] ]

7.2 Isomorphisms, and Canonical labellings

7.2-1 AutomorphismGroup
‣ 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) ])

7.2-2 AutomorphismGroup
‣ 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:

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(digraph) consisting of those automorphisms that preserve the colouring specified by 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) ])

7.2-3 DigraphCanonicalLabelling
‣ 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:

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(digraph). The canonical representative of 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) ]

7.2-4 DigraphCanonicalLabelling
‣ 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:

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:

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(digraph). The canonical representative of 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 ]

7.2-5 DigraphGroup
‣ 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) ])

7.2-6 DigraphOrbits
‣ 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 ] ]

7.2-7 DigraphOrbitReps
‣ 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 ]

7.2-8 DigraphSchreierVector
‣ 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(digraph) where:

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

7.2-9 DigraphStabilizer
‣ 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(())

7.2-10 IsIsomorphicDigraph
‣ 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

7.2-11 IsIsomorphicDigraph
‣ 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:

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

7.2-12 IsomorphismDigraphs
‣ 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 kth 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(digraph1) –- such that

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), () ]

7.2-13 IsomorphismDigraphs
‣ 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:

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 colours1[i] = colours2[i ^ p] for all vertices i in digraph1.

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

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

7.2-14 RepresentativeOutNeighbours
‣ 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 ] ]

7.3 Homomorphisms of digraphs

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.

7.3-1 HomomorphismDigraphsFinder
‣ 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 hook(user_param, t) is called every time a new homomorphism 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 hook(user_param, t) might set 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 ] ) ]

7.3-2 DigraphHomomorphism
‣ 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 ] )

7.3-3 HomomorphismsDigraphs
‣ 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 ] ) ]

7.3-4 DigraphMonomorphism
‣ 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 ] )

7.3-5 MonomorphismsDigraphs
‣ 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 ]

7.3-6 DigraphEpimorphism
‣ 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 ] )

7.3-7 EpimorphismsDigraphs
‣ 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 ] ) ]

7.3-8 GeneratorsOfEndomorphismMonoid
‣ 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:

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 ]

7.3-9 DigraphColouring
‣ 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(digraph, n) returns an epimorphism from 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 ] )

7.3-10 DigraphEmbedding
‣ 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 ] )

7.3-11 ChromaticNumber
‣ 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(digraph, n) does not return 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
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 A Bib Ind

generated by GAPDoc2HTML