‣ 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-12) of digraph will not be retained in the returned digraph.
If digraph belongs to IsMutableDigraph (3.1-2), then relabelling of the vertices is performed directly on digraph. If digraph belongs to IsImmutableDigraph (3.1-3), an immutable copy of digraph with the vertices relabelled is returned.
gap> D := Digraph([[3], [1, 3, 5], [1], [1, 2, 4], [2, 3, 5]]); <immutable digraph with 5 vertices, 11 edges> gap> new := OnDigraphs(D, (1, 2)); <immutable digraph with 5 vertices, 11 edges> gap> OutNeighbours(new); [ [ 2, 3, 5 ], [ 3 ], [ 2 ], [ 2, 1, 4 ], [ 1, 3, 5 ] ] gap> D := Digraph([[2], [], [2]]); <immutable digraph with 3 vertices, 2 edges> gap> t := Transformation([1, 2, 1]);; gap> new := OnDigraphs(D, t); <immutable multidigraph with 3 vertices, 2 edges> gap> OutNeighbours(new); [ [ 2, 2 ], [ ], [ ] ] gap> ForAll(DigraphEdges(D), > 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. If digraph belongs to IsMutableDigraph (3.1-2), then relabelling of the vertices is performed directly on digraph. If digraph belongs to IsImmutableDigraph (3.1-3), an immutable copy of digraph with the vertices relabelled is returned.
gap> D1 := Digraph([ > [3, 6, 3], [], [3], [9, 10], [9], [], [], [10, 4, 10], [], []]); <immutable multidigraph with 10 vertices, 10 edges> gap> p := BlissCanonicalLabelling(D1); [ (1,7)(3,6)(4,10)(5,9), () ] gap> D2 := OnMultiDigraphs(D1, p); <immutable multidigraph with 10 vertices, 10 edges> gap> OutNeighbours(D2); [ [ ], [ ], [ ], [ ], [ ], [ 6 ], [ 6, 3, 6 ], [ 4, 10, 4 ], [ 5 ], [ 5, 4 ] ]
‣ OnTuplesDigraphs( list, perm ) | ( operation ) |
‣ OnSetsDigraphs( list, perm ) | ( operation ) |
Returns: A list or set of digraphs.
If list is a list of digraphs, and perm is a permutation of the vertices of the digraphs in list, then OnTuplesDigraphs returns a new list constructed by applying perm via OnDigraphs (7.1-1) to a copy (with the same mutability) of each entry of list in turn.
More precisely, OnTuplesDigraphs(list,perm) is a list of length Length(list), whose i-th entry is OnDigraphs(DigraphCopy(list[i]), perm).
If list is moreover a GAP set (i.e. a duplicate-free sorted list), then OnSetsDigraphs returns the sorted output of OnTuplesDigraphs, which is therefore again a set.
gap> list := [CycleDigraph(IsMutableDigraph, 6), > DigraphReverse(CycleDigraph(6))]; [ <mutable digraph with 6 vertices, 6 edges>, <immutable digraph with 6 vertices, 6 edges> ] gap> p := (1, 6)(2, 5)(3, 4);; gap> result_tuples := OnTuplesDigraphs(list, p); [ <mutable digraph with 6 vertices, 6 edges>, <immutable digraph with 6 vertices, 6 edges> ] gap> result_tuples[2] = OnDigraphs(list[2], p); true gap> result_tuples = list; false gap> result_tuples = Reversed(list); true gap> result_sets := OnSetsDigraphs(list, p); [ <immutable digraph with 6 vertices, 6 edges>, <mutable digraph with 6 vertices, 6 edges> ] gap> result_sets = list; true
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-15), IsIsomorphicDigraph (7.2-16), IsomorphismDigraphs (7.2-17), and IsomorphismDigraphs (7.2-18) 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-17) for more information about isomorphisms of digraphs.
If digraph is not a multidigraph then the automorphism group is returned as a group of permutations on the set of vertices of digraph.
If digraph is a multidigraph then the automorphism group is returned as the direct product of a group of permutations on the set of vertices of digraph with a group of permutations on the set of edges of digraph. These groups can be accessed using Projection (Reference: Projection for a domain and a positive integer) on the returned group.
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).
If the argument digraph is mutable, then the return value of this attribute is recomputed every time it is called.
gap> johnson := DigraphFromGraph6String("E}lw"); <immutable symmetric 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); <immutable cycle digraph with 9 vertices> gap> G := AutomorphismGroup(cycle); Group([ (1,2,3,4,5,6,7,8,9) ]) gap> IsCyclic(G) and Size(G) = 9; true
‣ BlissAutomorphismGroup( digraph ) | ( attribute ) |
‣ BlissAutomorphismGroup( digraph, vertex_colours ) | ( operation ) |
‣ BlissAutomorphismGroup( digraph, vertex_colours, edge_colours ) | ( operation ) |
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.
The attribute AutomorphismGroup (7.2-6) returns the value of BlissAutomorphismGroup as it is not implemented for nauty The requirements for the optional arguments vertex_colours and edge_colours are documented in AutomorphismGroup (7.2-6). See also DigraphsUseBliss (7.2-1), and DigraphsUseNauty (7.2-1).
If the argument digraph is mutable, then the return value of this attribute is recomputed every time it is called.
gap> G := BlissAutomorphismGroup(JohnsonDigraph(5, 2));; gap> IsSymmetricGroup(G); true gap> Size(G); 120
‣ NautyAutomorphismGroup( digraph[, vert_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).
If the argument digraph is mutable, then the return value of this attribute is recomputed every time it is called.
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, vert_colours ) | ( operation ) |
Returns: A permutation group.
This operation computes the automorphism group of a vertex-coloured digraph. A vertex-coloured digraph can be specified by its underlying digraph digraph and its colouring vert_colours. Let n be the number of vertices of digraph. The colouring vert_colours may have one of the following two forms:
a list of n integers, where vert_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 vert_colours[i] is the list of all vertices with colour i.
The automorphism group of a coloured digraph digraph with colouring vert_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 vert_colours. See AutomorphismGroup (7.2-2), and see IsomorphismDigraphs (7.2-18) for more information about isomorphisms of coloured digraphs.
If digraph is not a multidigraph then the automorphism group is returned as a group of permutations on the set of vertices of digraph.
If digraph is a multidigraph then the automorphism group is returned as the direct product of a group of permutations on the set of vertices of digraph with a group of permutations on the set of edges of digraph. These groups can be accessed using Projection (Reference: Projection for a domain and a positive integer) on the returned group.
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); <immutable cycle digraph with 9 vertices> 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
‣ AutomorphismGroup( digraph, vert_colours, edge_colours ) | ( operation ) |
Returns: A permutation group.
This operation computes the automorphism group of a vertex- and/or edge-coloured digraph. A coloured digraph can be specified by its underlying digraph digraph and colourings vert_colours, edge_colours. Let n be the number of vertices of digraph. The colourings must have the following forms:
vert_colours must be fail or a list of n integers, where vert_colours[i] is the colour of vertex i, using the colours [1 .. m] for some m <= n;
edge_colours must be fail or a list of n lists of integers of the same shape as OutNeighbours(digraph), where edge_colours[i][j] is the colour of the edge OutNeighbours(digraph)[i][j], using the colours [1 .. k] for some k <= n;
Giving vert_colours [edge_colours] as fail is equivalent to setting all vertices [edges] to be the same colour.
Unlike AutomorphismGroup (7.2-2), it is possible to obtain the automorphism group of an edge-coloured multidigraph (see IsMultiDigraph (6.2-11)) when no two edges share the same source, range, and colour. The automorphism group of a vertex/edge-coloured digraph digraph with colouring c is the group consisting of its vertex/edge-colour preserving automorphisms; an automorphism of digraph is an isomorphism of vertex/edge-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-18) for more information about isomorphisms of coloured digraphs.
If digraph is not a multidigraph then the automorphism group is returned as a group of permutations on the set of vertices of digraph.
If digraph is a multidigraph then the automorphism group is returned as the direct product of a group of permutations on the set of vertices of digraph with a group of permutations on the set of edges of digraph. These groups can be accessed using Projection (Reference: Projection for a domain and a positive integer) on the returned group.
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(12); <immutable cycle digraph with 12 vertices> gap> vert_colours := List([1 .. 12], x -> x mod 3 + 1);; gap> edge_colours := List([1 .. 12], x -> [x mod 2 + 1]);; gap> Size(AutomorphismGroup(cycle)); 12 gap> Size(AutomorphismGroup(cycle, vert_colours)); 4 gap> Size(AutomorphismGroup(cycle, fail, edge_colours)); 6 gap> Size(AutomorphismGroup(cycle, vert_colours, edge_colours)); 2 gap> IsTrivial(AutomorphismGroup(cycle, > vert_colours, List([1 .. 12], x -> [x mod 4 + 1]))); true
‣ BlissCanonicalLabelling( digraph ) | ( attribute ) |
‣ NautyCanonicalLabelling( digraph ) | ( attribute ) |
Returns: A permutation, or a list of two permutations.
A function \(\rho\) that maps a digraph to a digraph is a canonical representative map if the following two conditions hold for all digraphs \(G\) and \(H\):
\(\rho(G)\) and \(G\) are isomorphic as digraphs; and
\(\rho(G)=\rho(H)\) if and only if \(G\) and \(H\) are isomorphic as digraphs.
A canonical labelling of a digraph \(G\) (under \(\rho\)) is an isomorphism of \(G\) onto its canonical representative, \(\rho(G)\). See IsomorphismDigraphs (7.2-17) 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).
BlissCanonicalLabelling can only be computed if digraph has no multiple edges; see IsMultiDigraph (6.2-11).
gap> digraph1 := DigraphFromDiSparse6String(".ImNS_AiB?qRN"); <immutable digraph with 10 vertices, 8 edges> gap> BlissCanonicalLabelling(digraph1); (1,9,5,7)(3,6,4,10) gap> p := (1, 2, 7, 5)(3, 9)(6, 10, 8);; gap> digraph2 := OnDigraphs(digraph1, p); <immutable digraph with 10 vertices, 8 edges> gap> digraph1 = digraph2; false gap> OnDigraphs(digraph1, BlissCanonicalLabelling(digraph1)) = > OnDigraphs(digraph2, BlissCanonicalLabelling(digraph2)); true
‣ BlissCanonicalLabelling( digraph, colours ) | ( operation ) |
‣ NautyCanonicalLabelling( digraph, colours ) | ( operation ) |
Returns: A permutation.
A function \(\rho\) 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\):
\(\rho(G)\) and \(G\) are isomorphic as coloured digraphs; and
\(\rho(G)=\rho(H)\) if and only if \(G\) and \(H\) are isomorphic as coloured digraphs.
A canonical labelling of a coloured digraph \(G\) (under \(\rho\)) is an isomorphism of \(G\) onto its canonical representative, \(\rho(G)\). See IsomorphismDigraphs (7.2-18) 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).
BlissCanonicalLabelling can only be computed if digraph has no multiple edges; see IsMultiDigraph (6.2-11). 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 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"); <immutable digraph with 10 vertices, 8 edges> gap> colours := [[1, 2, 8, 9, 10], [3, 4, 5, 6, 7]];; gap> p := BlissCanonicalLabelling(digraph, colours); (1,5,8,4,10,3,9)(6,7) gap> OnDigraphs(digraph, p); <immutable 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); (1,6,9,7)(3,4,5,8,10) gap> OnDigraphs(digraph, p); <immutable 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-7). 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-7).
If the argument digraph is mutable, then the return value of this attribute is recomputed every time it is called.
gap> digraph := Digraph([[1], [2, 3], [3], [1, 2, 3]]); <immutable digraph with 4 vertices, 7 edges> gap> canon := BlissCanonicalDigraph(digraph); <immutable digraph with 4 vertices, 7 edges> gap> OutNeighbours(canon); [ [ 1 ], [ 2 ], [ 3, 2 ], [ 1, 3, 2 ] ]
‣ DigraphGroup( digraph ) | ( attribute ) |
Returns: A permutation group.
If digraph is immutable and was created knowing a subgroup of its automorphism group, then this group is stored in the attribute DigraphGroup. If digraph is mutable, or was not created knowing a subgroup of its automorphism group, then DigraphGroup returns the entire automorphism group of digraph. Note that if digraph is mutable, then the automorphism group is recomputed every time this function is called.
Note that certain other constructor operations such as CayleyDigraph (3.1-12), BipartiteDoubleDigraph (3.3-44), and DoubleDigraph (3.3-43), 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> D := Digraph(IsMutableDigraph, group, [1 .. n], \^, adj); <mutable digraph with 4 vertices, 8 edges> gap> HasDigraphGroup(D); false gap> DigraphGroup(D); Group([ (2,4), (1,2)(3,4) ]) gap> AutomorphismGroup(D); Group([ (2,4), (1,2)(3,4) ]) gap> D := Digraph(group, [1 .. n], \^, adj); <immutable digraph with 4 vertices, 8 edges> gap> HasDigraphGroup(D); true gap> DigraphGroup(D); Group([ (1,2,3,4) ]) gap> D := DoubleDigraph(D); <immutable digraph with 8 vertices, 32 edges> gap> HasDigraphGroup(D); true gap> DigraphGroup(D); Group([ (1,2,3,4)(5,6,7,8), (1,5)(2,6)(3,7)(4,8) ]) gap> AutomorphismGroup(D) = > Group([(6, 8), (5, 7), (4, 6), (3, 5), (2, 4), > (1, 2)(3, 4)(5, 6)(7, 8)]); true gap> D := Digraph([[2, 3], [], []]); <immutable digraph with 3 vertices, 2 edges> gap> HasDigraphGroup(D); false gap> HasAutomorphismGroup(D); false gap> DigraphGroup(D); Group([ (2,3) ]) gap> HasAutomorphismGroup(D); true gap> group := DihedralGroup(8); <pc group of size 8 with 3 generators> gap> D := CayleyDigraph(group); <immutable digraph with 8 vertices, 24 edges> gap> HasDigraphGroup(D); true gap> GeneratorsOfGroup(DigraphGroup(D)); [ (1,2)(3,5)(4,6)(7,8), (1,7,4,3)(2,5,6,8), (1,4)(2,6)(3,7)(5,8) ]
‣ DigraphOrbits( digraph ) | ( attribute ) |
Returns: An immutable list of lists of integers.
DigraphOrbits returns the orbits of the action of the DigraphGroup (7.2-10) on the set of vertices of digraph.
gap> G := Group([(2, 3)(7, 8, 9), (1, 2, 3)(4, 5, 6)(8, 9)]);; gap> D := EdgeOrbitsDigraph(G, [1, 2]); <immutable digraph with 9 vertices, 6 edges> gap> DigraphOrbits(D); [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] gap> D := DigraphMutableCopy(D); <mutable digraph with 9 vertices, 6 edges> gap> DigraphOrbits(D); [ [ 1, 2, 3 ], [ 4, 5, 6, 7, 8, 9 ] ]
‣ DigraphOrbitReps( digraph ) | ( attribute ) |
Returns: An immutable list of integers.
DigraphOrbitReps returns a list of orbit representatives of the action of the DigraphGroup (7.2-10) on the set of vertices of digraph.
gap> D := CayleyDigraph(AlternatingGroup(4)); <immutable digraph with 12 vertices, 24 edges> gap> DigraphOrbitReps(D); [ 1 ] gap> D := DigraphMutableCopy(D); <mutable digraph with 12 vertices, 24 edges> gap> DigraphOrbitReps(D); [ 1 ] gap> D := DigraphFromDigraph6String("&IGO??S?`?_@?a?CK?O"); <immutable digraph with 10 vertices, 14 edges> gap> DigraphOrbitReps(D); [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] gap> DigraphOrbitReps(DigraphMutableCopy(D)); [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
‣ DigraphSchreierVector( digraph ) | ( attribute ) |
Returns: An immutable list of integers.
DigraphSchreierVector returns the so-called Schreier vector of the action of the DigraphGroup (7.2-10) 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> 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> D := Digraph(IsMutableDigraph, group, [1 .. n], \^, adj); <mutable digraph with 4 vertices, 8 edges> gap> sch := DigraphSchreierVector(D); [ -1, 2, 2, 1 ] gap> D := CayleyDigraph(AlternatingGroup(4)); <immutable digraph with 12 vertices, 24 edges> gap> sch := DigraphSchreierVector(D); [ -1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 1, 1 ] gap> DigraphOrbitReps(D); [ 1 ] gap> gens := GeneratorsOfGroup(DigraphGroup(D)); [ (1,7,5)(2,10,9)(3,4,11)(6,8,12), (1,3,2)(4,5,6)(7,9,8)(10,11,12) ] gap> 10 / gens[sch[10]]; 2 gap> 7 / gens[sch[7]]; 1 gap> 5 / gens[sch[5]]; 7
‣ 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-10) on the set of vertices of digraph.
gap> D := DigraphFromDigraph6String("&GYHPQgWTIIPW"); <immutable digraph with 8 vertices, 24 edges> gap> DigraphStabilizer(D, 8); Group(()) gap> DigraphStabilizer(D, 2); Group(()) gap> D := DigraphMutableCopy(D); <mutable digraph with 8 vertices, 24 edges> gap> DigraphStabilizer(D, 8); Group(()) gap> DigraphStabilizer(D, 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-17) 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); <immutable cycle digraph with 4 vertices> gap> digraph2 := CycleDigraph(5); <immutable cycle digraph with 5 vertices> gap> IsIsomorphicDigraph(digraph1, digraph2); false gap> digraph2 := DigraphReverse(digraph1); <immutable digraph with 4 vertices, 4 edges> gap> IsIsomorphicDigraph(digraph1, digraph2); true gap> digraph1 := Digraph([[3], [], []]); <immutable digraph with 3 vertices, 1 edge> gap> digraph2 := Digraph([[], [], [2]]); <immutable 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-18) 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); <immutable chain digraph with 4 vertices> gap> digraph2 := ChainDigraph(3); <immutable chain digraph with 3 vertices> gap> IsIsomorphicDigraph(digraph1, digraph2, > [[1, 4], [2, 3]], [[1, 2], [3]]); false gap> digraph2 := DigraphReverse(digraph1); <immutable 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
‣ 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. 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); <immutable cycle digraph with 4 vertices> gap> digraph2 := CycleDigraph(5); <immutable cycle digraph with 5 vertices> gap> IsomorphismDigraphs(digraph1, digraph2); fail gap> digraph1 := CompleteBipartiteDigraph(10, 5); <immutable complete bipartite digraph with bicomponent sizes 10 and 5> gap> digraph2 := CompleteBipartiteDigraph(5, 10); <immutable complete bipartite digraph with bicomponent sizes 5 and 10> 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
‣ 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-17) 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); <immutable chain digraph with 4 vertices> gap> digraph2 := ChainDigraph(3); <immutable chain digraph with 3 vertices> gap> IsomorphismDigraphs(digraph1, digraph2, > [[1, 4], [2, 3]], [[1, 2], [3]]); fail gap> digraph2 := DigraphReverse(digraph1); <immutable 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
‣ RepresentativeOutNeighbours( digraph ) | ( attribute ) |
Returns: An immutable list of lists.
This function returns the list out of out-neighbours of each representative of the orbits of the action of DigraphGroup (7.2-10) 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-10) is trivial, then OutNeighbours (5.2-6) is returned.
gap> D := Digraph([ > [2, 1, 3, 4, 5], [3, 5], [2], [1, 2, 3, 5], [1, 2, 3, 4]]); <immutable digraph with 5 vertices, 16 edges> gap> DigraphGroup(D); Group(()) gap> RepresentativeOutNeighbours(D); [ [ 2, 1, 3, 4, 5 ], [ 3, 5 ], [ 2 ], [ 1, 2, 3, 5 ], [ 1, 2, 3, 4 ] ] gap> D := Digraph(IsMutableDigraph, [ > [2, 1, 3, 4, 5], [3, 5], [2], [1, 2, 3, 5], [1, 2, 3, 4]]); <mutable digraph with 5 vertices, 16 edges> gap> DigraphGroup(D); Group(()) gap> RepresentativeOutNeighbours(D); [ [ 2, 1, 3, 4, 5 ], [ 3, 5 ], [ 2 ], [ 1, 2, 3, 5 ], [ 1, 2, 3, 4 ] ] gap> D := DigraphFromDigraph6String("&GYHPQgWTIIPW"); <immutable digraph with 8 vertices, 24 edges> gap> G := DigraphGroup(D);; gap> GeneratorsOfGroup(G); [ (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> Set(RepresentativeOutNeighbours(D), Set); [ [ 2, 3, 5 ] ]
‣ IsDigraphIsomorphism( src, ran, x ) | ( operation ) |
‣ IsDigraphIsomorphism( src, ran, x, col1, col2 ) | ( operation ) |
‣ IsDigraphAutomorphism( digraph, x ) | ( operation ) |
‣ IsDigraphAutomorphism( digraph, x, col ) | ( 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).
If col1 and col2, or col, are given, then they must represent vertex colourings; see AutomorphismGroup (7.2-5) for details of the permissible values for these arguments. The homomorphism must then also have the property:
col1[i] = col2[i ^ x] for all vertices i of src, for IsDigraphIsomorphism.
col[i] = col[i ^ x] for all vertices i of digraph, for IsDigraphAutomorphism.
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]]); <immutable digraph with 3 vertices, 5 edges> gap> IsDigraphAutomorphism(src, (1, 2, 3)); false gap> IsDigraphAutomorphism(src, (2, 3)); true gap> IsDigraphAutomorphism(src, (2, 3), [2, 1, 1]); true gap> IsDigraphAutomorphism(src, (2, 3), [2, 2, 1]); false gap> IsDigraphAutomorphism(src, (2, 3)(4, 5)); true gap> IsDigraphAutomorphism(src, (1, 4)); false gap> IsDigraphAutomorphism(src, ()); true gap> ran := Digraph([[2, 1], [2], [2, 3]]); <immutable 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 gap> IsDigraphIsomorphism(src, ran, (1, 2), [1, 2, 3], [2, 1, 3]); true gap> IsDigraphIsomorphism(src, ran, (1, 2), [1, 2, 2], [2, 1, 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-10).
gap> D := JohnsonDigraph(5, 3); <immutable symmetric 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
‣ MaximalCommonSubdigraph( D1, D2 ) | ( operation ) |
Returns: A list containing a digraph and two transformations.
If D1 and D2 are digraphs without multiple edges, then MaximalCommonSubdigraph returns a maximal common subgraph M of D1 and D2 with the maximum number of vertices. So M is a digraph which embeds into both D1 and D2 and has the largest number of vertices among such digraphs. It returns a list [M, t1, t2] where M is the maximal common subdigraph and t1, t2 are transformations embedding M into D1 and D2 respectively.
gap> MaximalCommonSubdigraph(PetersenGraph(), CompleteDigraph(10)); [ <immutable digraph with 2 vertices, 2 edges>, IdentityTransformation, IdentityTransformation ] gap> MaximalCommonSubdigraph(PetersenGraph(), > DigraphSymmetricClosure(CycleDigraph(5))); [ <immutable digraph with 5 vertices, 10 edges>, IdentityTransformation, IdentityTransformation ] gap> MaximalCommonSubdigraph(NullDigraph(0), CompleteDigraph(10)); [ <immutable empty digraph with 0 vertices>, IdentityTransformation, IdentityTransformation ]
‣ MinimalCommonSuperdigraph( D1, D2 ) | ( operation ) |
Returns: A list containing a digraph and two transformations.
If D1 and D2 are digraphs without multiple edges, then MinimalCommonSuperdigraph returns a minimal common superdigraph M of D1 and D2 with the minimum number of vertices. So M is a digraph into which both D1 and D2 embed and has the smallest number of vertices among such digraphs. It returns a list [M, t1, t2] where M is the minimal common superdigraph and t1, t2 are transformations embedding D1 and D2 respectively into M.
gap> MinimalCommonSuperdigraph(PetersenGraph(), CompleteDigraph(10)); [ <immutable digraph with 18 vertices, 118 edges>, IdentityTransformation, Transformation( [ 1, 2, 11, 12, 13, 14, 15, 16, 17, 18, 11, 12, 13, 14, 15, 16, 17, 18 ] ) ] gap> MinimalCommonSuperdigraph(PetersenGraph(), > DigraphSymmetricClosure(CycleDigraph(5))); [ <immutable digraph with 10 vertices, 30 edges>, IdentityTransformation, IdentityTransformation ] gap> MinimalCommonSuperdigraph(NullDigraph(0), CompleteDigraph(10)); [ <immutable digraph with 10 vertices, 90 edges>, IdentityTransformation, IdentityTransformation ]
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( D1, D2, hook, user_param, max_results, hint, injective, image, partial_map, colors1, colors2[, order, aut_grp] ) | ( function ) |
Returns: The argument user_param.
This function finds homomorphisms from the digraph D1 to the digraph D2 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 D2 in aut_grp.
This argument should be a function or fail.
If hook is a function, then it must 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 the function returns true, then HomomorphismDigraphsFinder stops and does not find any further homomorphisms. This feature might be useful if you are searching for a homomorphism that satisfies some condition that you cannot specify via the other arguments to 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 mutable 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 of 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 mutable list.
This argument should be a positive integer or infinity. HomomorphismDigraphsFinder will return after it has found max_results homomorphisms or the search is complete, whichever happens first.
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 0, 1, or 2. If it is 2, then only embeddings are found, if it is 1, then only injective homomorphisms are found, and if it is 0 there are no restrictions imposed by this argument.
For backwards compatibility, injective can also be false or true which correspond to the values 0 and 1 described in the previous paragraph, respectively.
This argument should be a subset of the vertices of the graph D2. HomomorphismDigraphsFinder only finds homomorphisms from D1 to the subgraph of D2 induced by the vertices image.
The returned homomorphisms (if any) are still "up to the action" of the group specified by aut_grp (which is the entire automorphism group by default). This might generate unexpected results. For example, if D1 has automorphism group where one orbit consists of, say, 1 and 2, then HomomorphismDigraphsFinder will only attempt to find homomorphisms mapping 1 to 1, and if there are no such homomorphisms with image set equal to image, then no homomorphisms will be returned (even if there is a homomorphism from D1 to D2 mapping 1 to 2). To ensure that that all homomorphisms with image set equal to image are considered it is necessary for the last argument aut_grp to be the trivial permutation group.
This argument should be a partial map from D1 to D2, that is, a (not necessarily dense) list of vertices of the digraph D2 of length no greater than the number vertices in the digraph D1. HomomorphismDigraphsFinder only finds homomorphisms extending partial_map (if any).
This should be a list representing possible colours of vertices in the digraph D1; 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 D2; see AutomorphismGroup (7.2-5) for details of the permissible values for this argument.
The optional argument order specifies the order the vertices in D1 appear in the search for homomorphisms. The value of this parameter can have a large impact on the runtime of the function. It seems in many cases to be a good idea for this to be the DigraphWelshPowellOrder (7.3-17), i.e. vertices ordered from highest to lowest degree.
The optional argument aut_grp should be a subgroup of the automorphism group of D2. This function returns unique representatives of the homomorphisms found up to right multiplication by aut_grp. If this argument is not specific, it defaults to the full automorphism group of D2, which may be costly to calculate.
gap> D := ChainDigraph(10); <immutable chain digraph with 10 vertices> gap> D := DigraphSymmetricClosure(D); <immutable symmetric digraph with 10 vertices, 18 edges> gap> HomomorphismDigraphsFinder(D, D, fail, [], infinity, 2, 0, > [3, 4], [], fail, fail); #I WARNING you are trying to find homomorphisms by specifying a subset of the vertices of the target digraph. This might lead to unexpected results! If this happens, try passing Group(()) as the last argument. Please see the documentation of HomomorphismDigraphsFinder for details. [ Transformation( [ 3, 4, 3, 4, 3, 4, 3, 4, 3, 4 ] ), Transformation( [ 4, 3, 4, 3, 4, 3, 4, 3, 4, 3 ] ) ] gap> D2 := CompleteDigraph(6);; gap> HomomorphismDigraphsFinder(D, D2, fail, [], 1, fail, 0, > [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(D, D2, func, [Transformation([2, 2])], > 3, fail, 0, [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 ] ) ] gap> HomomorphismDigraphsFinder(NullDigraph(2), NullDigraph(3), fail, > [], infinity, fail, 1, [1, 2, 3], fail, fail, fail, fail, > Group(())); [ IdentityTransformation, Transformation( [ 1, 3, 3 ] ), Transformation( [ 2, 1 ] ), Transformation( [ 2, 3, 3 ] ), Transformation( [ 3, 1, 3 ] ), Transformation( [ 3, 2, 3 ] ) ] gap> HomomorphismDigraphsFinder(NullDigraph(2), NullDigraph(3), fail, > [], infinity, fail, 1, [1, 2, 3], fail, fail, fail, fail, > Group((1, 2))); [ IdentityTransformation, Transformation( [ 1, 3, 3 ] ), Transformation( [ 3, 1, 3 ] ) ]
‣ 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 to adjacent vertices.
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]]); <immutable digraph with 5 vertices, 6 edges> gap> DigraphHomomorphism(gr1, gr1); IdentityTransformation gap> map := DigraphHomomorphism(gr1, gr2); Transformation( [ 3, 1, 5, 4, 5 ] ) gap> IsDigraphHomomorphism(gr1, gr2, map); true
‣ 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]]); <immutable 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)); [ Transformation( [ 2, 1 ] ), Transformation( [ 2, 1, 2 ] ) ]
‣ 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]]); <immutable digraph with 5 vertices, 6 edges> gap> DigraphMonomorphism(gr1, gr1); IdentityTransformation gap> DigraphMonomorphism(gr1, gr2); Transformation( [ 3, 1, 5, 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), except they only return injective homomorphisms.
gap> gr1 := ChainDigraph(3);; gap> gr2 := Digraph([[3, 5], [2], [3, 1], [], [4]]); <immutable 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)); [ Transformation( [ 2, 1 ] ) ]
‣ 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)); <immutable digraph with 4 vertices, 3 edges> gap> gr2 := DigraphRemoveEdge(CompleteDigraph(3), [1, 2]); <immutable digraph with 3 vertices, 5 edges> gap> DigraphEpimorphism(gr2, gr1); fail gap> DigraphEpimorphism(gr1, gr2); Transformation( [ 3, 1, 2, 3 ] )
‣ 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), except they only return surjective homomorphisms.
gap> gr1 := DigraphReverse(ChainDigraph(4)); <immutable digraph with 4 vertices, 3 edges> gap> gr2 := DigraphSymmetricClosure(CycleDigraph(3)); <immutable symmetric digraph with 3 vertices, 6 edges> gap> EpimorphismsDigraphsRepresentatives(gr1, gr2); [ Transformation( [ 3, 1, 2, 1 ] ), Transformation( [ 3, 1, 2, 3 ] ), Transformation( [ 2, 1, 2, 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 ] ) ]
‣ 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-3) of digraph2 on the image of t.
DigraphEmbedding returns a single embedding if one exists, otherwise it returns fail.
gap> gr := ChainDigraph(3); <immutable chain digraph with 3 vertices> gap> DigraphEmbedding(gr, CompleteDigraph(4)); fail gap> DigraphEmbedding(gr, Digraph([[3], [1, 4], [1], [3]])); Transformation( [ 2, 4, 3, 4 ] )
‣ EmbeddingsDigraphs( D1, D2 ) | ( operation ) |
‣ EmbeddingsDigraphsRepresentatives( D1, D2 ) | ( operation ) |
Returns: A list of transformations.
These operations behave the same as HomomorphismsDigraphs (7.3-3) and HomomorphismsDigraphsRepresentatives (7.3-3), except they only return embeddings of D1 into D2.
See also IsDigraphEmbedding (7.3-11).
gap> D1 := NullDigraph(2); <immutable empty digraph with 2 vertices> gap> D2 := CycleDigraph(5); <immutable cycle digraph with 5 vertices> gap> EmbeddingsDigraphsRepresentatives(D1, D2); [ Transformation( [ 1, 3, 3 ] ), Transformation( [ 1, 4, 3, 4 ] ) ] gap> EmbeddingsDigraphs(D1, D2); [ Transformation( [ 1, 3, 3 ] ), Transformation( [ 1, 4, 3, 4 ] ), Transformation( [ 2, 4, 4, 5, 1 ] ), Transformation( [ 2, 5, 4, 5, 1 ] ), Transformation( [ 3, 1, 5, 1, 2 ] ), Transformation( [ 3, 5, 5, 1, 2 ] ), Transformation( [ 4, 1, 1, 2, 3 ] ), Transformation( [ 4, 2, 1, 2, 3 ] ), Transformation( [ 5, 2, 2, 3, 4 ] ), Transformation( [ 5, 3, 2, 3, 4 ] ) ]
‣ IsDigraphHomomorphism( src, ran, x ) | ( operation ) |
‣ IsDigraphHomomorphism( src, ran, x, col1, col2 ) | ( operation ) |
‣ IsDigraphEpimorphism( src, ran, x ) | ( operation ) |
‣ IsDigraphEpimorphism( src, ran, x, col1, col2 ) | ( operation ) |
‣ IsDigraphMonomorphism( src, ran, x ) | ( operation ) |
‣ IsDigraphMonomorphism( src, ran, x, col1, col2 ) | ( operation ) |
‣ IsDigraphEndomorphism( digraph, x ) | ( operation ) |
‣ IsDigraphEndomorphism( digraph, x, col ) | ( 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 maps the vertices of src to a subset of the vertices of ran, i.e. IsSubset(DigraphVertices(ran), OnSets(DigraphVertices(src), x)) is true.
Note that if i is any integer greater than DigraphNrVertice(src), then the action of x on i is ignored by this function. One consequence of this is that distinct transformations or permutations might represent the same homomorphism. For example, if src and ran are CycleDigraph(2), then both the permutations (1, 2) and (1, 2)(3, 4) represent the same automorphism of src.
See also GeneratorsOfEndomorphismMonoid (7.3-14).
If col1 and col2, or col, are given, then they must represent vertex colourings; see AutomorphismGroup (7.2-5) for details of the permissible values for these argument. The homomorphism must then also have the property:
col[i] = col[i ^ x] for all vertices i of digraph, in the case of IsDigraphEndomorphism.
col1[i] = col2[i ^ x] for all vertices i of src, in the cases of the other operations.
See also DigraphsRespectsColouring (7.3-13).
gap> src := Digraph([[1], [1, 2], [1, 3]]); <immutable digraph with 3 vertices, 5 edges> gap> ran := Digraph([[1], [1, 2]]); <immutable 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> IsDigraphHomomorphism(src, ran, Transformation([1, 2, 2]), > [1, 2, 2], [1, 2]); true gap> IsDigraphHomomorphism(src, ran, Transformation([1, 2, 2]), > [2, 1, 1], [1, 2]); false gap> IsDigraphEndomorphism(src, Transformation([3, 3, 3])); true gap> IsDigraphEndomorphism(src, Transformation([3, 3, 3]), [1, 1, 1]); true gap> IsDigraphEndomorphism(src, Transformation([3, 3, 3]), [1, 1, 2]); false 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 ) |
‣ IsDigraphEmbedding( src, ran, x, col1, col2 ) | ( 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, while respecting the colourings col1 and col2 if given.
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-10).
gap> src := Digraph([[1], [1, 2]]); <immutable digraph with 2 vertices, 3 edges> gap> ran := Digraph([[1], [1, 2], [1, 3]]); <immutable digraph with 3 vertices, 5 edges> gap> IsDigraphMonomorphism(src, ran, ()); true gap> IsDigraphEmbedding(src, ran, ()); true gap> IsDigraphEmbedding(src, ran, (), [2, 1], [2, 1, 1]); true gap> IsDigraphEmbedding(src, ran, (), [2, 1], [1, 2, 1]); false gap> ran := Digraph([[1, 2], [1, 2], [1, 3]]); <immutable digraph with 3 vertices, 6 edges> gap> IsDigraphMonomorphism(src, ran, IdentityTransformation); true gap> IsDigraphEmbedding(src, ran, IdentityTransformation); false
‣ SubdigraphsMonomorphisms( digraph1, digraph2 ) | ( operation ) |
‣ SubdigraphsMonomorphismsRepresentatives( digraph1, digraph2 ) | ( operation ) |
Returns: A list of transformations.
These operations behave the same as HomomorphismsDigraphs (7.3-3) and HomomorphismsDigraphsRepresentatives (7.3-3), except they only return injective homomorphisms with the following property: the (not necessarily induced) subdigraphs defined by the images of these monomorphisms are all of the subdigraphs of digraph2 that are isomorphic to digraph1. Note that the subdigraphs of the previous sentence are those obtained by applying the corresponding monomorphism to the vertices and the edges of digraph1, and are therefore possibly strictly contained in the induced subdigraph on the same vertex set.
gap> SubdigraphsMonomorphisms(CompleteBipartiteDigraph(2, 2), > CompleteDigraph(4)); [ Transformation( [ 1, 3, 2 ] ), Transformation( [ 2, 3, 1 ] ), Transformation( [ 3, 4, 2, 1 ] ) ] gap> SubdigraphsMonomorphismsRepresentatives( > CompleteBipartiteDigraph(2, 2), CompleteDigraph(4)); [ Transformation( [ 1, 3, 2 ] ) ]
‣ DigraphsRespectsColouring( src, ran, x, col1, col2 ) | ( operation ) |
Returns: true or false.
The operation DigraphsRespectsColouring verifies whether or not the permutation or transformation x respects the vertex colourings col1 and col2 of the digraphs src and range. That is, DigraphsRespectsColouring returns true if and only if for all vertices i of src, col1[i] = col2[i ^ x].
gap> src := Digraph([[1], [1, 2]]); <immutable digraph with 2 vertices, 3 edges> gap> ran := Digraph([[1], [1, 2], [1, 3]]); <immutable digraph with 3 vertices, 5 edges> gap> DigraphsRespectsColouring(src, ran, (1, 2), [2, 1], [1, 2, 1]); true gap> DigraphsRespectsColouring(src, ran, (1, 2), [2, 1], [2, 1, 1]); false
‣ 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 digraph belongs to IsImmutableDigraph (3.1-3), then the value of GeneratorsOfEndomorphismMonoid will not be recomputed on future calls.
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( [ 2, 3, 1 ] ), 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 ) |
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-11). Note that a digraph with loops (DigraphHasLoops (6.2-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.
See also DigraphGreedyColouring (7.3-16) and
Note that a digraph with at least two vertices has a 2-colouring if and only if it is bipartite, see IsBipartiteDigraph (6.2-3).
gap> DigraphColouring(CompleteDigraph(5), 4); fail gap> DigraphColouring(ChainDigraph(10), 1); fail gap> D := ChainDigraph(10);; gap> t := DigraphColouring(D, 2); Transformation( [ 1, 2, 1, 2, 1, 2, 1, 2, 1, 2 ] ) gap> IsDigraphColouring(D, t); true gap> DigraphGreedyColouring(D); Transformation( [ 2, 1, 2, 1, 2, 1, 2, 1, 2, 1 ] )
‣ DigraphGreedyColouring( digraph, order ) | ( operation ) |
‣ DigraphGreedyColouring( digraph, func ) | ( operation ) |
‣ DigraphGreedyColouring( 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. Note that a digraph with loops (DigraphHasLoops (6.2-1)) does not have any proper colouring.
If digraph is a digraph and order is a dense list consisting of all of the vertices of digraph (in any order), then DigraphGreedyColouring uses a greedy algorithm with the specified order to obtain some proper colouring of digraph, which may not use the minimal number of colours.
If digraph is a digraph and func is a function whose argument is a digraph, and that returns a dense list order, then DigraphGreedyColouring(digraph, func) returns DigraphGreedyColouring(digraph, func(digraph)).
If the optional second argument (either a list or a function), is not specified, then DigraphWelshPowellOrder (7.3-17) is used by default.
See also DigraphColouring (7.3-15).
gap> DigraphGreedyColouring(ChainDigraph(10)); Transformation( [ 2, 1, 2, 1, 2, 1, 2, 1, 2, 1 ] ) gap> DigraphGreedyColouring(ChainDigraph(10), [1 .. 10]); Transformation( [ 1, 2, 1, 2, 1, 2, 1, 2, 1, 2 ] )
‣ DigraphWelshPowellOrder( digraph ) | ( attribute ) |
Returns: A list of the vertices.
DigraphWelshPowellOrder returns a list of all of the vertices of the digraph digraph ordered according to the sum of the number of out- and in-neighbours, from highest to lowest.
gap> DigraphWelshPowellOrder(Digraph([[4], [9], [9], [], > [4, 6, 9], [1], [], [], > [4, 5], [4, 5]])); [ 5, 9, 4, 1, 6, 10, 2, 3, 7, 8 ]
‣ 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.2-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-15).
It is possible to select the algorithm to compute the chromatic number via the use of value options. The permitted algorithms and values to pass as options are:
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 gap> D := PetersenGraph(IsMutableDigraph); <mutable digraph with 10 vertices, 30 edges> gap> ChromaticNumber(D); 3 gap> ChromaticNumber(CompleteDigraph(10) : lawler); 10 gap> ChromaticNumber(CompleteDigraph(10) : byskov); 10
‣ DigraphCore( D ) | ( attribute ) |
Returns: A list of positive integers.
If D is a digraph, then DigraphCore returns a list of vertices corresponding to the core of D. In particular, the subdigraph of D induced by this list is isomorphic to the core of D.
The core of a digraph D is the minimal subdigraph C of D which is a homomorphic image of D. The core of a digraph is unique up to isomorphism.
gap> D := DigraphSymmetricClosure(CycleDigraph(8)); <immutable symmetric digraph with 8 vertices, 16 edges> gap> DigraphCore(D); [ 1, 2 ] gap> D := PetersenGraph(); <immutable digraph with 10 vertices, 30 edges> gap> DigraphCore(D); [ 1 .. 10 ] gap> D := Digraph(IsMutableDigraph, [[3], [3], [4], [5], [2]]); <mutable digraph with 5 vertices, 5 edges> gap> DigraphCore(D); [ 2, 3, 4, 5 ]
‣ LatticeDigraphEmbedding( L1, L2 ) | ( operation ) |
Returns: A transformation, or fail.
If L1 and L2 are lattice digraphs (IsLatticeDigraph (6.4-3) returns true, then LatticeDigraphEmbedding returns a single injective DigraphHomomorphism (7.3-2) between L1 and L2, with the property that it is a lattice homomorphism. If no such homomorphism exists, fail is returned.
A lattice homomorphism is a digraph homomorphism which respects meets and joins of every pair of vertices. Note that every injective lattice homomorphism map is an embedding, in the sense that the inverse of map is a lattice homomorphism also.
gap> D := DigraphReflexiveTransitiveClosure(ChainDigraph(5)); <immutable preorder digraph with 5 vertices, 15 edges> gap> L1 := DigraphReflexiveTransitiveClosure(ChainDigraph(5)); <immutable preorder digraph with 5 vertices, 15 edges> gap> L2 := DigraphReflexiveTransitiveClosure(ChainDigraph(6)); <immutable preorder digraph with 6 vertices, 21 edges> gap> LatticeDigraphEmbedding(L1, L2); IdentityTransformation gap> LatticeDigraphEmbedding(L2, L1); fail
‣ IsLatticeHomomorphism( L1, L2, map ) | ( operation ) |
‣ IsLatticeEpimorphism( L1, L2, map ) | ( operation ) |
‣ IsLatticeEmbedding( L1, L2, map ) | ( operation ) |
‣ IsLatticeMonomorphism( L1, L2, map ) | ( operation ) |
‣ IsLatticeEndomorphism( L, map ) | ( operation ) |
Returns: true or false.
Each of the function described in this section (except IsLatticeEndomorphism) takes a pair of digraphs L1 and L2, and a transformation map, returning true if map is a lattice homomorphism from L1 to L2, and false otherwise. If L1 or L2 is not a lattice, then false is returned.
A transformation or permutation map is a lattice homomorphism if map respects meets and joins of every pair of vertices, and map fixes every i which is not a vertex of L1.
IsLatticeHomomorphism returns true if the permutation or transformation map is a lattice homomorphism from the lattice digraph L1 to the lattice digraph L2.
IsLatticeEpimorphism returns true if the permutation or transformation map is a surjective lattice homomorphism from the lattice digraph L1 to the lattice digraph L2.
IsLatticeEmbedding returns true if the permutation or transformation map is an injective lattice homomorphism from the lattice digraph L1 to the lattice digraph L2. The function IsLatticeMonomorphism is a synonym of IsLatticeEmbedding.
IsLatticeEndomorphism returns true if the permutation or transformation map is an lattice endomorphism of the lattice digraph L.
gap> G := Digraph([[2, 4], [3, 7], [6], [5, 7], [6], [], [6]]); <immutable digraph with 7 vertices, 9 edges> gap> D := DigraphRemoveVertex(G, 7); <immutable digraph with 6 vertices, 6 edges> gap> G := DigraphReflexiveTransitiveClosure(G); <immutable preorder digraph with 7 vertices, 22 edges> gap> D := DigraphReflexiveTransitiveClosure(D); <immutable preorder digraph with 6 vertices, 17 edges> gap> IsDigraphEmbedding(D, G, IdentityTransformation); true gap> IsLatticeHomomorphism(D, G, IdentityTransformation); false gap> D := Digraph([[2, 3], [4], [4], []]); <immutable digraph with 4 vertices, 4 edges> gap> G := Digraph([[2, 3], [4], [4], [5], []]); <immutable digraph with 5 vertices, 5 edges> gap> D := DigraphReflexiveTransitiveClosure(D); <immutable preorder digraph with 4 vertices, 9 edges> gap> G := DigraphReflexiveTransitiveClosure(G); <immutable preorder digraph with 5 vertices, 14 edges> gap> IsLatticeEmbedding(D, G, IdentityTransformation); true gap> IsLatticeMonomorphism(D, G, IdentityTransformation); true gap> f := Transformation([1, 2, 3, 4, 4]); Transformation( [ 1, 2, 3, 4, 4 ] ) gap> IsLatticeEpimorphism(G, D, f); true gap> IsLatticeEndomorphism(D, (2, 3)); true
generated by GAPDoc2HTML