‣ 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(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 := 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).
If digraph has no multiple edges, then the automorphism group is returned as a group of permutations on the vertices of digraph.
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
; or
a list of non-empty disjoint lists whose union is DigraphVertices(digraph)
, such that 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(digraph)
consisting of those automorphisms that preserve the colouring specified by 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).
If digraph has no multiple edges, then the automorphism group is returned as a group of permutations on the vertices of digraph.
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).
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);
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);
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
; or
a list of non-empty disjoint lists whose union is DigraphVertices(digraph)
, such that 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).
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);
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);
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(digraph)
and digraph are isomorphic as digraphs; and
If gr
is any digraph then BlissCanonicalDigraph(gr)
and BlissCanonicalDigraph(digraph)
are equal if and only if 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(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
‣ 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
; or
a list of non-empty disjoint lists whose union is DigraphVertices(digraph)
, such that 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
.
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
.
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(digraph1)
–- such that
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:
a list of n
integers, where colours[i]
is the colour of vertex i
, using the colours [1 .. m]
for some m <= n
; or
a list of non-empty disjoint lists whose union is DigraphVertices(digraph)
, such that 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 colours1[i] = colours2[i ^ p]
for all vertices i
in digraph1.
This operation returns such an isomorphism if one exists, else it returns fail
.
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> 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 ^ x, v ^ x]
is an edge of 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
‣ IsDigraphColouring ( digraph, list ) | ( operation ) |
‣ IsDigraphColouring ( digraph, t ) | ( operation ) |
Returns: true
or false
.
The operation IsDigraphColouring
verifies whether or not the list list describes a proper colouring of the digraph digraph.
A list list describes a proper colouring of a digraph digraph if list consists of positive integers, the length of list equals the number of vertices in digraph, and for any vertices u, v
of digraph if u
and v
are adjacent, then list[u] >< list[v]
.
A transformation t describes a proper colouring of a digraph digraph, if ImageListOfTransformation(t, DigraphNrVertices(digraph))
is a proper colouring of digraph.
See also IsDigraphHomomorphism
(7.3-12).
gap> D := JohnsonDigraph(5, 3); <digraph with 10 vertices, 60 edges> gap> IsDigraphColouring(D, [1, 2, 3, 3, 2, 1, 4, 5, 6, 7]); true gap> IsDigraphColouring(D, [1, 2, 3, 3, 2, 1, 2, 5, 6, 7]); false gap> IsDigraphColouring(D, [1, 2, 3, 3, 2, 1, 2, 5, 6, -1]); false gap> IsDigraphColouring(D, [1, 2, 3]); false gap> IsDigraphColouring(D, IdentityTransformation); true
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.
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 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.
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.
This argument should be a positive integer or infinity
. HomomorphismDigraphsFinder
will return after it has found limit homomorphisms or the search is complete.
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.
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.
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.
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).
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.
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(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 ] )
‣ 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(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
‣ 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 ^ x, v ^ x]
is an edge of 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