Quelle chap7.html

Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/digraphs/doc/chap7.html

<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (Digraphs) - Chapter 7: Homomorphisms</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap7" onload="jscontent()">

<div class="chlinktop">Goto Chapter: <a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chapA.html">A</a> <a href="chapB.html">B</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap6.html">[Previous Chapter]</a> <a href="chap8.html">[Next Chapter]</a> </div>

<a href="chap7_mj.html">[MathJax on]</a>
<a id="X84975388859F203D" name="X84975388859F203D"></a>
<div class="ChapSects"><a href="chap7.html#X84975388859F203D">7 Homomorphisms</a>
<div class="ContSect"> <a href="chap7.html#X8200192B80AD2071">7.1 Acting on digraphs</a>

<div class="ContSSBlock">
 <a href="chap7.html#X808972017C486F1F">7.1-1 OnDigraphs</a>
 <a href="chap7.html#X7AFBA7608498F9CE">7.1-2 OnMultiDigraphs</a>
 <a href="chap7.html#X7F6A97E6870CDDA3">7.1-3 OnTuplesDigraphs</a>
</div></div>
<div class="ContSect"> <a href="chap7.html#X7E48B9F87A0F22D4">7.2 Isomorphisms and canonical labellings</a>

<div class="ContSSBlock">
 <a href="chap7.html#X83E593F3855B122E">7.2-1 DigraphsUseNauty</a>
 <a href="chap7.html#X858C32127A190175">7.2-2 AutomorphismGroup</a>
 <a href="chap7.html#X7E7B0D88865A89F6">7.2-3 BlissAutomorphismGroup</a>
 <a href="chap7.html#X857758B18144C0CD">7.2-4 NautyAutomorphismGroup</a>
 <a href="chap7.html#X877732B1783C391B">7.2-5 AutomorphismGroup</a>
 <a href="chap7.html#X7DA2C4FE837FFE01">7.2-6 AutomorphismGroup</a>
 <a href="chap7.html#X7D676FE67A6684FF">7.2-7 BlissCanonicalLabelling</a>
 <a href="chap7.html#X87DA265D803DB337">7.2-8 BlissCanonicalLabelling</a>
 <a href="chap7.html#X877B1D377EC197D7">7.2-9 BlissCanonicalDigraph</a>
 <a href="chap7.html#X803ACEDA7BBAC5B3">7.2-10 DigraphGroup</a>
 <a href="chap7.html#X8096C5287E459279">7.2-11 DigraphOrbits</a>
 <a href="chap7.html#X8386028782F2D3FF">7.2-12 DigraphOrbitReps</a>
 <a href="chap7.html#X8657604E87A25E5F">7.2-13 DigraphSchreierVector</a>
 <a href="chap7.html#X78913684795FB256">7.2-14 DigraphStabilizer</a>
 <a href="chap7.html#X7B4F24B283C9EE28">7.2-15 IsIsomorphicDigraph</a>
 <a href="chap7.html#X7D4A1FA8868DA930">7.2-16 IsIsomorphicDigraph</a>
 <a href="chap7.html#X8219FE6C839D9457">7.2-17 IsomorphismDigraphs</a>
 <a href="chap7.html#X7ED93C0F86D9D34F">7.2-18 IsomorphismDigraphs</a>
 <a href="chap7.html#X7E1C806D81DFE15E">7.2-19 RepresentativeOutNeighbours</a>
 <a href="chap7.html#X80183D4A7C51365A">7.2-20 IsDigraphIsomorphism</a>
 <a href="chap7.html#X7F16B8B3825A627A">7.2-21 IsDigraphColouring</a>
 <a href="chap7.html#X7D4378F27B49C9AC">7.2-22 MaximalCommonSubdigraph</a>
 <a href="chap7.html#X7B99C75B8021FCDA">7.2-23 MinimalCommonSuperdigraph</a>
</div></div>
<div class="ContSect"> <a href="chap7.html#X7E1A02FE8384C03C">7.3 Homomorphisms of digraphs</a>

<div class="ContSSBlock">
 <a href="chap7.html#X79ABF0E783FD67C7">7.3-1 HomomorphismDigraphsFinder</a>
 <a href="chap7.html#X85E9B019877AD7FE">7.3-2 DigraphHomomorphism</a>
 <a href="chap7.html#X8653EDA183E06D05">7.3-3 HomomorphismsDigraphs</a>
 <a href="chap7.html#X82D0FCD87D47ACA8">7.3-4 DigraphMonomorphism</a>
 <a href="chap7.html#X84B4BDB984C2A9A8">7.3-5 MonomorphismsDigraphs</a>
 <a href="chap7.html#X7CB5AD9F861684FD">7.3-6 DigraphEpimorphism</a>
 <a href="chap7.html#X7DFB1F5D873937B3">7.3-7 EpimorphismsDigraphs</a>
 <a href="chap7.html#X7AD04CC186E86CCA">7.3-8 DigraphEmbedding</a>
 <a href="chap7.html#X82EBDF137EEDC5FD">7.3-9 EmbeddingsDigraphs</a>
 <a href="chap7.html#X80FE9FCB79718A61">7.3-10 IsDigraphHomomorphism</a>
 <a href="chap7.html#X7D6B5A0887903810">7.3-11 IsDigraphEmbedding</a>
 <a href="chap7.html#X87E60FB17BC444EF">7.3-12 SubdigraphsMonomorphisms</a>
 <a href="chap7.html#X7F80709A80CBFA98">7.3-13 DigraphsRespectsColouring</a>
 <a href="chap7.html#X7E93B268823F6478">7.3-14 GeneratorsOfEndomorphismMonoid</a>
 <a href="chap7.html#X86D0A74B83D6B9A7">7.3-15 DigraphColouring</a>
 <a href="chap7.html#X7AB7200D831013C1">7.3-16 DigraphGreedyColouring</a>
 <a href="chap7.html#X7F9CB3B27B9590DB">7.3-17 DigraphWelshPowellOrder</a>
 <a href="chap7.html#X807D49358529A37C">7.3-18 ChromaticNumber</a>
 <a href="chap7.html#X863487EF7D64EF56">7.3-19 DigraphCore</a>
 <a href="chap7.html#X7EEA340C81FCA52D">7.3-20 LatticeDigraphEmbedding</a>
 <a href="chap7.html#X7E183D4979D324EF">7.3-21 IsLatticeHomomorphism</a>
</div></div>
</div>

<h3>7 Homomorphisms</h3>

<a id="X8200192B80AD2071" name="X8200192B80AD2071"></a>

<h4>7.1 Acting on digraphs</h4>

<a id="X808972017C486F1F" name="X808972017C486F1F"></a>

<h5>7.1-1 OnDigraphs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnDigraphs</code>( <var class="Arg">digraph</var>, <var class="Arg">perm</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnDigraphs</code>( <var class="Arg">digraph</var>, <var class="Arg">trans</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A digraph.

If <var class="Arg">digraph</var> is a digraph, and the second argument <var class="Arg">perm</var> is a permutation of the vertices of <var class="Arg">digraph</var>, then this operation returns a digraph constructed by relabelling the vertices of <var class="Arg">digraph</var> according to <var class="Arg">perm</var>. Note that for an automorphism <code class="code">f</code> of a digraph, we have <code class="code">OnDigraphs(<var class="Arg">digraph</var>, f) = </code><var class="Arg">digraph</var>.

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

The <code class="func">DigraphVertexLabels</code> (<a href="chap5.html#X7E51F2FE87140B32">5.1-12</a>) of <var class="Arg">digraph</var> will not be retained in the returned digraph.

If <var class="Arg">digraph</var> belongs to <code class="func">IsMutableDigraph</code> (<a href="chap3.html#X7D7EDF83820ED6F5">3.1-2</a>), then relabelling of the vertices is performed directly on <var class="Arg">digraph</var>. If <var class="Arg">digraph</var> belongs to <code class="func">IsImmutableDigraph</code> (<a href="chap3.html#X7CAFAA89804F80BD">3.1-3</a>), an immutable copy of <var class="Arg">digraph</var> with the vertices relabelled is returned.

<div class="example"><pre>
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
</pre></div>

<a id="X7AFBA7608498F9CE" name="X7AFBA7608498F9CE"></a>

<h5>7.1-2 OnMultiDigraphs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnMultiDigraphs</code>( <var class="Arg">digraph</var>, <var class="Arg">pair</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnMultiDigraphs</code>( <var class="Arg">digraph</var>, <var class="Arg">perm1</var>, <var class="Arg">perm2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A digraph.

If <var class="Arg">digraph</var> is a digraph, and <var class="Arg">pair</var> is a pair consisting of a permutation of the vertices and a permutation of the edges of <var class="Arg">digraph</var>, then this operation returns a digraph constructed by relabelling the vertices and edges of <var class="Arg">digraph</var> according to <var class="Arg">perm[1]</var> and <var class="Arg">perm[2]</var>, respectively.

In its second form, <code class="code">OnMultiDigraphs</code> returns a digraph with vertices and edges permuted by <var class="Arg">perm1</var> and <var class="Arg">perm2</var>, respectively.

Note that <code class="code">OnDigraphs(<var class="Arg">digraph</var>, perm)=OnMultiDigraphs(<var class="Arg">digraph</var>, [perm, ()])</code> where <code class="code">perm</code> is a permutation of the vertices of <var class="Arg">digraph</var>. If you are only interested in the action of a permutation on the vertices of a digraph, then you can use <code class="code">OnDigraphs</code> instead of <code class="code">OnMultiDigraphs</code>. If <var class="Arg">digraph</var> belongs to <code class="func">IsMutableDigraph</code> (<a href="chap3.html#X7D7EDF83820ED6F5">3.1-2</a>), then relabelling of the vertices is performed directly on <var class="Arg">digraph</var>. If <var class="Arg">digraph</var> belongs to <code class="func">IsImmutableDigraph</code> (<a href="chap3.html#X7CAFAA89804F80BD">3.1-3</a>), an immutable copy of <var class="Arg">digraph</var> with the vertices relabelled is returned.

<div class="example"><pre>
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 ] ]</pre></div>

<a id="X7F6A97E6870CDDA3" name="X7F6A97E6870CDDA3"></a>

<h5>7.1-3 OnTuplesDigraphs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnTuplesDigraphs</code>( <var class="Arg">list</var>, <var class="Arg">perm</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnSetsDigraphs</code>( <var class="Arg">list</var>, <var class="Arg">perm</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list or set of digraphs.

If <var class="Arg">list</var> is a list of digraphs, and <var class="Arg">perm</var> is a permutation of the vertices of the digraphs in <var class="Arg">list</var>, then <code class="func">OnTuplesDigraphs</code> returns a new list constructed by applying <var class="Arg">perm</var> via <code class="func">OnDigraphs</code> (<a href="chap7.html#X808972017C486F1F">7.1-1</a>) to a copy (with the same mutability) of each entry of <var class="Arg">list</var> in turn.

More precisely, <code class="code">OnTuplesDigraphs(<var class="Arg">list</var>,<var class="Arg">perm</var>)</code> is a list of length <code class="code">Length(<var class="Arg">list</var>)</code>, whose <code class="code">i</code>-th entry is <code class="code">OnDigraphs(DigraphCopy(<var class="Arg">list</var>[i]), <var class="Arg">perm</var>)</code>.

If <var class="Arg">list</var> is moreover a GAP set (i.e. a duplicate-free sorted list), then <code class="func">OnSetsDigraphs</code> returns the sorted output of <code class="func">OnTuplesDigraphs</code>, which is therefore again a set.

<div class="example"><pre>
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</pre></div>

<a id="X7E48B9F87A0F22D4" name="X7E48B9F87A0F22D4"></a>

<h4>7.2 Isomorphisms and canonical labellings</h4>

From version 0.11.0 of Digraphs it is possible to use either <a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a> or <a href="https://pallini.di.uniroma1.it">nauty</a> (via <a href="https://github.com/gap-packages/NautyTracesInterface">NautyTracesInterface</a> ) to calculate canonical labellings and automorphism groups of digraphs; see <a href="chapBib.html#biBJK07">[JK07]</a> and <a href="chapBib.html#biBMP14">[MP14]</a> for more details about <a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a> and <a href="https://pallini.di.uniroma1.it">nauty</a> , respectively.

<a id="X83E593F3855B122E" name="X83E593F3855B122E"></a>

<h5>7.2-1 DigraphsUseNauty</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphsUseNauty</code>( )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphsUseBliss</code>( )</td><td class="tdright">( function )</td></tr></table></div>
Returns: Nothing.

These functions can be used to specify whether <a href="https://pallini.di.uniroma1.it">nauty</a> or <a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a> should be used by default by Digraphs. If <a href="https://github.com/gap-packages/NautyTracesInterface">NautyTracesInterface</a> is not available, then these functions do nothing. Otherwise, by calling <code class="code">DigraphsUseNauty</code> subsequent computations will default to using <a href="https://pallini.di.uniroma1.it">nauty</a> rather than <a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a> , 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 <code class="func">IsIsomorphicDigraph</code> (<a href="chap7.html#X7B4F24B283C9EE28">7.2-15</a>), <code class="func">IsIsomorphicDigraph</code> (<a href="chap7.html#X7D4A1FA8868DA930">7.2-16</a>), <code class="func">IsomorphismDigraphs</code> (<a href="chap7.html#X8219FE6C839D9457">7.2-17</a>), and <code class="func">IsomorphismDigraphs</code> (<a href="chap7.html#X7ED93C0F86D9D34F">7.2-18</a>) are also valid.

It is also possible to compute the automorphism group of a specific digraph using both <a href="https://pallini.di.uniroma1.it">nauty</a> and <a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a> using <code class="func">NautyAutomorphismGroup</code> (<a href="chap7.html#X857758B18144C0CD">7.2-4</a>) and <code class="func">BlissAutomorphismGroup</code> (<a href="chap7.html#X7E7B0D88865A89F6">7.2-3</a>), respectively.

<a id="X858C32127A190175" name="X858C32127A190175"></a>

<h5>7.2-2 AutomorphismGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AutomorphismGroup</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A permutation group.

If <var class="Arg">digraph</var> is a digraph, then this attribute contains the group of automorphisms of <var class="Arg">digraph</var>. An automorphism of <var class="Arg">digraph</var> is an isomorphism from <var class="Arg">digraph</var> to itself. See <code class="func">IsomorphismDigraphs</code> (<a href="chap7.html#X8219FE6C839D9457">7.2-17</a>) for more information about isomorphisms of digraphs.

If <var class="Arg">digraph</var> is not a multidigraph then the automorphism group is returned as a group of permutations on the set of vertices of <var class="Arg">digraph</var>.

If <var class="Arg">digraph</var> is a multidigraph then the automorphism group is returned as the direct product of a group of permutations on the set of vertices of <var class="Arg">digraph</var> with a group of permutations on the set of edges of <var class="Arg">digraph</var>. These groups can be accessed using <code class="func">Projection</code> (<a href="/home/runner/gap/doc/ref/chap32.html#X8769E8DA80BC96C1">Reference: Projection for a domain and a positive integer</a>) on the returned group.

By default, the automorphism group is found using <a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a> by Tommi Junttila and Petteri Kaski. If <a href="https://github.com/gap-packages/NautyTracesInterface">NautyTracesInterface</a> is available, then <a href="https://pallini.di.uniroma1.it">nauty</a> by Brendan Mckay and Adolfo Piperno can be used instead; see <code class="func">BlissAutomorphismGroup</code> (<a href="chap7.html#X7E7B0D88865A89F6">7.2-3</a>), <code class="func">NautyAutomorphismGroup</code> (<a href="chap7.html#X857758B18144C0CD">7.2-4</a>), <code class="func">DigraphsUseBliss</code> (<a href="chap7.html#X83E593F3855B122E">7.2-1</a>), and <code class="func">DigraphsUseNauty</code> (<a href="chap7.html#X83E593F3855B122E">7.2-1</a>).

If the argument <var class="Arg">digraph</var> is mutable, then the return value of this attribute is recomputed every time it is called.

<div class="example"><pre>
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</pre></div>

<a id="X7E7B0D88865A89F6" name="X7E7B0D88865A89F6"></a>

<h5>7.2-3 BlissAutomorphismGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BlissAutomorphismGroup</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BlissAutomorphismGroup</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex_colours</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BlissAutomorphismGroup</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex_colours</var>, <var class="Arg">edge_colours</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A permutation group.

If <var class="Arg">digraph</var> is a digraph, then this attribute contains the group of automorphisms of <var class="Arg">digraph</var> as calculated using <a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a> by Tommi Junttila and Petteri Kaski.

The attribute <code class="func">AutomorphismGroup</code> (<a href="chap7.html#X858C32127A190175">7.2-2</a>) and operation <code class="func">AutomorphismGroup</code> (<a href="chap7.html#X877732B1783C391B">7.2-5</a>) returns the value of either <code class="code">BlissAutomorphismGroup</code> or <code class="func">NautyAutomorphismGroup</code> (<a href="chap7.html#X857758B18144C0CD">7.2-4</a>). These groups are, of course, equal but their generating sets may differ.

The attribute <code class="func">AutomorphismGroup</code> (<a href="chap7.html#X7DA2C4FE837FFE01">7.2-6</a>) returns the value of <code class="code">BlissAutomorphismGroup</code> as it is not implemented for <a href="https://pallini.di.uniroma1.it">nauty</a> The requirements for the optional arguments <var class="Arg">vertex_colours</var> and <var class="Arg">edge_colours</var> are documented in <code class="func">AutomorphismGroup</code> (<a href="chap7.html#X7DA2C4FE837FFE01">7.2-6</a>). See also <code class="func">DigraphsUseBliss</code> (<a href="chap7.html#X83E593F3855B122E">7.2-1</a>), and <code class="func">DigraphsUseNauty</code> (<a href="chap7.html#X83E593F3855B122E">7.2-1</a>).

If the argument <var class="Arg">digraph</var> is mutable, then the return value of this attribute is recomputed every time it is called.

<div class="example"><pre>
gap> G := BlissAutomorphismGroup(JohnsonDigraph(5, 2));;
gap> IsSymmetricGroup(G);
true
gap> Size(G);
120</pre></div>

<a id="X857758B18144C0CD" name="X857758B18144C0CD"></a>

<h5>7.2-4 NautyAutomorphismGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NautyAutomorphismGroup</code>( <var class="Arg">digraph</var>[, <var class="Arg">vert_colours</var>] )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A permutation group.

If <var class="Arg">digraph</var> is a digraph, then this attribute contains the group of automorphisms of <var class="Arg">digraph</var> as calculated using <a href="https://pallini.di.uniroma1.it">nauty</a> by Brendan Mckay and Adolfo Piperno via <a href="https://github.com/gap-packages/NautyTracesInterface">NautyTracesInterface</a> . The attribute <code class="func">AutomorphismGroup</code> (<a href="chap7.html#X858C32127A190175">7.2-2</a>) and operation <code class="func">AutomorphismGroup</code> (<a href="chap7.html#X877732B1783C391B">7.2-5</a>) returns the value of either <code class="code">NautyAutomorphismGroup</code> or <code class="func">BlissAutomorphismGroup</code> (<a href="chap7.html#X7E7B0D88865A89F6">7.2-3</a>). These groups are, of course, equal but their generating sets may differ.

See also <code class="func">DigraphsUseBliss</code> (<a href="chap7.html#X83E593F3855B122E">7.2-1</a>), and <code class="func">DigraphsUseNauty</code> (<a href="chap7.html#X83E593F3855B122E">7.2-1</a>).

If the argument <var class="Arg">digraph</var> is mutable, then the return value of this attribute is recomputed every time it is called.

<div class="example"><pre>
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) ])</pre></div>

<a id="X877732B1783C391B" name="X877732B1783C391B"></a>

<h5>7.2-5 AutomorphismGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AutomorphismGroup</code>( <var class="Arg">digraph</var>, <var class="Arg">vert_colours</var> )</td><td class="tdright">( operation )</td></tr></table></div>
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 <var class="Arg">digraph</var> and its colouring <var class="Arg">vert_colours</var>. Let <code class="code">n</code> be the number of vertices of <var class="Arg">digraph</var>. The colouring <var class="Arg">vert_colours</var> may have one of the following two forms:

<ul>
<li>a list of <code class="code">n</code> integers, where <var class="Arg">vert_colours</var><code class="code">[i]</code> is the colour of vertex <code class="code">i</code>, using the colours <code class="code">[1 .. m]</code> for some <code class="code">m <= n</code>; or

</li>
<li>a list of non-empty disjoint lists whose union is <code class="code">DigraphVertices(<var class="Arg">digraph</var>)</code>, such that <var class="Arg">vert_colours</var><code class="code">[i]</code> is the list of all vertices with colour <code class="code">i</code>.

</li>
</ul>
The automorphism group of a coloured digraph <var class="Arg">digraph</var> with colouring <var class="Arg">vert_colours</var> is the group consisting of its automorphisms; an automorphism of <var class="Arg">digraph</var> is an isomorphism of coloured digraphs from <var class="Arg">digraph</var> to itself. This group is equal to the subgroup of <code class="code">AutomorphismGroup(<var class="Arg">digraph</var>)</code> consisting of those automorphisms that preserve the colouring specified by <var class="Arg">vert_colours</var>. See <code class="func">AutomorphismGroup</code> (<a href="chap7.html#X858C32127A190175">7.2-2</a>), and see <code class="func">IsomorphismDigraphs</code> (<a href="chap7.html#X7ED93C0F86D9D34F">7.2-18</a>) for more information about isomorphisms of coloured digraphs.

If <var class="Arg">digraph</var> is not a multidigraph then the automorphism group is returned as a group of permutations on the set of vertices of <var class="Arg">digraph</var>.

If <var class="Arg">digraph</var> is a multidigraph then the automorphism group is returned as the direct product of a group of permutations on the set of vertices of <var class="Arg">digraph</var> with a group of permutations on the set of edges of <var class="Arg">digraph</var>. These groups can be accessed using <code class="func">Projection</code> (<a href="/home/runner/gap/doc/ref/chap32.html#X8769E8DA80BC96C1">Reference: Projection for a domain and a positive integer</a>) on the returned group.

By default, the automorphism group is found using <a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a> by Tommi Junttila and Petteri Kaski. If <a href="https://github.com/gap-packages/NautyTracesInterface">NautyTracesInterface</a> is available, then <a href="https://pallini.di.uniroma1.it">nauty</a> by Brendan Mckay and Adolfo Piperno can be used instead; see <code class="func">BlissAutomorphismGroup</code> (<a href="chap7.html#X7E7B0D88865A89F6">7.2-3</a>), <code class="func">NautyAutomorphismGroup</code> (<a href="chap7.html#X857758B18144C0CD">7.2-4</a>), <code class="func">DigraphsUseBliss</code> (<a href="chap7.html#X83E593F3855B122E">7.2-1</a>), and <code class="func">DigraphsUseNauty</code> (<a href="chap7.html#X83E593F3855B122E">7.2-1</a>).

<div class="example"><pre>
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</pre></div>

<a id="X7DA2C4FE837FFE01" name="X7DA2C4FE837FFE01"></a>

<h5>7.2-6 AutomorphismGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AutomorphismGroup</code>( <var class="Arg">digraph</var>, <var class="Arg">vert_colours</var>, <var class="Arg">edge_colours</var> )</td><td class="tdright">( operation )</td></tr></table></div>
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 <var class="Arg">digraph</var> and colourings <var class="Arg">vert_colours</var>, <var class="Arg">edge_colours</var>. Let <code class="code">n</code> be the number of vertices of <var class="Arg">digraph</var>. The colourings must have the following forms:

<ul>
<li><var class="Arg">vert_colours</var> must be <code class="keyw">fail</code> or a list of <code class="code">n</code> integers, where <var class="Arg">vert_colours</var><code class="code">[i]</code> is the colour of vertex <code class="code">i</code>, using the colours <code class="code">[1 .. m]</code> for some <code class="code">m <= n</code>;

</li>
<li><var class="Arg">edge_colours</var> must be <code class="keyw">fail</code> or a list of <code class="code">n</code> lists of integers of the same shape as <code class="code">OutNeighbours(digraph)</code>, where <var class="Arg">edge_colours</var><code class="code">[i][j]</code> is the colour of the edge <code class="code">OutNeighbours(digraph)[i][j]</code>, using the colours <code class="code">[1 .. k]</code> for some <code class="code">k <= n</code>;

</li>
</ul>
Giving <var class="Arg">vert_colours</var> [<var class="Arg">edge_colours</var>] as <code class="code">fail</code> is equivalent to setting all vertices [edges] to be the same colour.

Unlike <code class="func">AutomorphismGroup</code> (<a href="chap7.html#X858C32127A190175">7.2-2</a>), it is possible to obtain the automorphism group of an edge-coloured multidigraph (see <code class="func">IsMultiDigraph</code> (<a href="chap6.html#X7BB84CFC7E8B2B26">6.2-11</a>)) when no two edges share the same source, range, and colour. The automorphism group of a vertex/edge-coloured digraph <var class="Arg">digraph</var> with colouring <var class="Arg">c</var> is the group consisting of its vertex/edge-colour preserving automorphisms; an automorphism of <var class="Arg">digraph</var> is an isomorphism of vertex/edge-coloured digraphs from <var class="Arg">digraph</var> to itself. This group is equal to the subgroup of <code class="code">AutomorphismGroup(<var class="Arg">digraph</var>)</code> consisting of those automorphisms that preserve the colouring specified by <var class="Arg">colours</var>. See <code class="func">AutomorphismGroup</code> (<a href="chap7.html#X858C32127A190175">7.2-2</a>), and see <code class="func">IsomorphismDigraphs</code> (<a href="chap7.html#X7ED93C0F86D9D34F">7.2-18</a>) for more information about isomorphisms of coloured digraphs.

If <var class="Arg">digraph</var> is not a multidigraph then the automorphism group is returned as a group of permutations on the set of vertices of <var class="Arg">digraph</var>.

If <var class="Arg">digraph</var> is a multidigraph then the automorphism group is returned as the direct product of a group of permutations on the set of vertices of <var class="Arg">digraph</var> with a group of permutations on the set of edges of <var class="Arg">digraph</var>. These groups can be accessed using <code class="func">Projection</code> (<a href="/home/runner/gap/doc/ref/chap32.html#X8769E8DA80BC96C1">Reference: Projection for a domain and a positive integer</a>) on the returned group.

By default, the automorphism group is found using <a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a> by Tommi Junttila and Petteri Kaski. If <a href="https://github.com/gap-packages/NautyTracesInterface">NautyTracesInterface</a> is available, then <a href="https://pallini.di.uniroma1.it">nauty</a> by Brendan Mckay and Adolfo Piperno can be used instead; see <code class="func">BlissAutomorphismGroup</code> (<a href="chap7.html#X7E7B0D88865A89F6">7.2-3</a>), <code class="func">NautyAutomorphismGroup</code> (<a href="chap7.html#X857758B18144C0CD">7.2-4</a>), <code class="func">DigraphsUseBliss</code> (<a href="chap7.html#X83E593F3855B122E">7.2-1</a>), and <code class="func">DigraphsUseNauty</code> (<a href="chap7.html#X83E593F3855B122E">7.2-1</a>).

<div class="example"><pre>
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
</pre></div>

<a id="X7D676FE67A6684FF" name="X7D676FE67A6684FF"></a>

<h5>7.2-7 BlissCanonicalLabelling</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BlissCanonicalLabelling</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NautyCanonicalLabelling</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
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:

<ul>
<li>ρ(G) and G are isomorphic as digraphs; and

</li>
<li>ρ(G)=ρ(H) if and only if G and H are isomorphic as digraphs.

</li>
</ul>
A canonical labelling of a digraph G (under ρ) is an isomorphism of G onto its canonical representative, ρ(G). See <code class="func">IsomorphismDigraphs</code> (<a href="chap7.html#X8219FE6C839D9457">7.2-17</a>) for more information about isomorphisms of digraphs.

<code class="code">BlissCanonicalLabelling</code> returns a canonical labelling of the digraph <var class="Arg">digraph</var> found using <a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a> by Tommi Junttila and Petteri Kaski. <code class="code">NautyCanonicalLabelling</code> returns a canonical labelling of the digraph <var class="Arg">digraph</var> found using <a href="https://pallini.di.uniroma1.it">nauty</a> by Brendan McKay and Adolfo Piperno. Note that the canonical labellings returned by <a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a> and <a href="https://pallini.di.uniroma1.it">nauty</a> are not usually the same (and may depend of the version used).

<code class="code">BlissCanonicalLabelling</code> can only be computed if <var class="Arg">digraph</var> has no multiple edges; see <code class="func">IsMultiDigraph</code> (<a href="chap6.html#X7BB84CFC7E8B2B26">6.2-11</a>).

<div class="example"><pre>
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</pre></div>

<a id="X87DA265D803DB337" name="X87DA265D803DB337"></a>

<h5>7.2-8 BlissCanonicalLabelling</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BlissCanonicalLabelling</code>( <var class="Arg">digraph</var>, <var class="Arg">colours</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NautyCanonicalLabelling</code>( <var class="Arg">digraph</var>, <var class="Arg">colours</var> )</td><td class="tdright">( operation )</td></tr></table></div>
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:

<ul>
<li>ρ(G) and G are isomorphic as coloured digraphs; and

</li>
<li>ρ(G)=ρ(H) if and only if G and H are isomorphic as coloured digraphs.

</li>
</ul>
A canonical labelling of a coloured digraph G (under ρ) is an isomorphism of G onto its canonical representative, ρ(G). See <code class="func">IsomorphismDigraphs</code> (<a href="chap7.html#X7ED93C0F86D9D34F">7.2-18</a>) for more information about isomorphisms of coloured digraphs.

A coloured digraph can be specified by its underlying digraph <var class="Arg">digraph</var> and its colouring <var class="Arg">colours</var>. Let <code class="code">n</code> be the number of vertices of <var class="Arg">digraph</var>. The colouring <var class="Arg">colours</var> may have one of the following two forms:

<ul>
<li>a list of <code class="code">n</code> integers, where <var class="Arg">colours</var><code class="code">[i]</code> is the colour of vertex <code class="code">i</code>, using the colours <code class="code">[1 .. m]</code> for some <code class="code">m <= n</code>; or

</li>
<li>a list of non-empty disjoint lists whose union is <code class="code">DigraphVertices(<var class="Arg">digraph</var>)</code>, such that <var class="Arg">colours</var><code class="code">[i]</code> is the list of all vertices with colour <code class="code">i</code>.

</li>
</ul>
If <var class="Arg">digraph</var> and <var class="Arg">colours</var> together form a coloured digraph, <code class="code">BlissCanonicalLabelling</code> returns a canonical labelling of the digraph <var class="Arg">digraph</var> found using <a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a> by Tommi Junttila and Petteri Kaski. Similarly, <code class="code">NautyCanonicalLabelling</code> returns a canonical labelling of the digraph <var class="Arg">digraph</var> found using <a href="https://pallini.di.uniroma1.it">nauty</a> by Brendan McKay and Adolfo Piperno. Note that the canonical labellings returned by <a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a> and <a href="https://pallini.di.uniroma1.it">nauty</a> are not usually the same (and may depend of the version used).

<code class="code">BlissCanonicalLabelling</code> can only be computed if <var class="Arg">digraph</var> has no multiple edges; see <code class="func">IsMultiDigraph</code> (<a href="chap6.html#X7BB84CFC7E8B2B26">6.2-11</a>). The canonical labelling of <var class="Arg">digraph</var> is given as a permutation of its vertices. The canonical representative of <var class="Arg">digraph</var> can be created from <var class="Arg">digraph</var> and its canonical labelling <code class="code">p</code> by using the operation <code class="func">OnDigraphs</code> (<a href="chap7.html#X808972017C486F1F">7.1-1</a>):

<div class="example"><pre>gap> OnDigraphs(digraph, p);</pre></div>

The colouring of the canonical representative can easily be constructed. A vertex <code class="code">v</code> (in <var class="Arg">digraph</var>) has colour <code class="code">i</code> if and only if the vertex <code class="code">v ^ p</code> (in the canonical representative) has colour <code class="code">i</code>, where <code class="code">p</code> is the permutation of the canonical labelling that acts on the vertices of <var class="Arg">digraph</var>. In particular, if <var class="Arg">colours</var> has the first form that is described above, then the colouring of the canonical representative is given by:

<div class="example"><pre>gap> List(DigraphVertices(digraph), i -> colours[i / p]);</pre></div>

On the other hand, if <var class="Arg">colours</var> has the second form above, then the canonical representative has colouring:

<div class="example"><pre>gap> OnTuplesSets(colours, p);</pre></div>

<div class="example"><pre>
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 ]</pre></div>

<a id="X877B1D377EC197D7" name="X877B1D377EC197D7"></a>

<h5>7.2-9 BlissCanonicalDigraph</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BlissCanonicalDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NautyCanonicalDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A digraph.

The attribute <code class="code">BlissCanonicalLabelling</code> returns the canonical representative found by applying <code class="func">BlissCanonicalLabelling</code> (<a href="chap7.html#X7D676FE67A6684FF">7.2-7</a>). The digraph returned is canonical in the sense that

<ul>
<li><code class="code">BlissCanonicalDigraph(<var class="Arg">digraph</var>)</code> and <var class="Arg">digraph</var> are isomorphic as digraphs; and

</li>
<li>If <code class="code">gr</code> is any digraph then <code class="code">BlissCanonicalDigraph(gr)</code> and <code class="code">BlissCanonicalDigraph(<var class="Arg">digraph</var>)</code> are equal if and only if <code class="code">gr</code> and <var class="Arg">digraph</var> are isomorphic as digraphs.

</li>
</ul>
Analogously, the attribute <code class="code">NautyCanonicalLabelling</code> returns the canonical representative found by applying <code class="func">NautyCanonicalLabelling</code> (<a href="chap7.html#X7D676FE67A6684FF">7.2-7</a>).

If the argument <var class="Arg">digraph</var> is mutable, then the return value of this attribute is recomputed every time it is called.

<div class="example"><pre>
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 ] ]
</pre></div>

<a id="X803ACEDA7BBAC5B3" name="X803ACEDA7BBAC5B3"></a>

<h5>7.2-10 DigraphGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphGroup</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A permutation group.

If <var class="Arg">digraph</var> is immutable and was created knowing a subgroup of its automorphism group, then this group is stored in the attribute <code class="code">DigraphGroup</code>. If <var class="Arg">digraph</var> is mutable, or was not created knowing a subgroup of its automorphism group, then <code class="code">DigraphGroup</code> returns the entire automorphism group of <var class="Arg">digraph</var>. Note that if <var class="Arg">digraph</var> is mutable, then the automorphism group is recomputed every time this function is called.

Note that certain other constructor operations such as <code class="func">CayleyDigraph</code> (<a href="chap3.html#X7FCADADC7EC28478">3.1-12</a>), <code class="func">BipartiteDoubleDigraph</code> (<a href="chap3.html#X7C6E6CB284982C7A">3.3-44</a>), and <code class="func">DoubleDigraph</code> (<a href="chap3.html#X7FB8B48C87C0ED16">3.3-43</a>), may not require a group as one of the arguments, but use the standard constructor method using a group, and hence set the <code class="code">DigraphGroup</code> attribute for the resulting digraph.

<div class="example"><pre>
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) ]</pre></div>

<a id="X8096C5287E459279" name="X8096C5287E459279"></a>

<h5>7.2-11 DigraphOrbits</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphOrbits</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An immutable list of lists of integers.

<code class="code">DigraphOrbits</code> returns the orbits of the action of the <code class="func">DigraphGroup</code> (<a href="chap7.html#X803ACEDA7BBAC5B3">7.2-10</a>) on the set of vertices of <var class="Arg">digraph</var>.

<div class="example"><pre>
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 ] ]
</pre></div>

<a id="X8386028782F2D3FF" name="X8386028782F2D3FF"></a>

<h5>7.2-12 DigraphOrbitReps</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphOrbitReps</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An immutable list of integers.

<code class="code">DigraphOrbitReps</code> returns a list of orbit representatives of the action of the <code class="func">DigraphGroup</code> (<a href="chap7.html#X803ACEDA7BBAC5B3">7.2-10</a>) on the set of vertices of <var class="Arg">digraph</var>.

<div class="example"><pre>
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 ]
</pre></div>

<a id="X8657604E87A25E5F" name="X8657604E87A25E5F"></a>

<h5>7.2-13 DigraphSchreierVector</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphSchreierVector</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An immutable list of integers.

<code class="code">DigraphSchreierVector</code> returns the so-called Schreier vector of the action of the <code class="func">DigraphGroup</code> (<a href="chap7.html#X803ACEDA7BBAC5B3">7.2-10</a>) on the set of vertices of <var class="Arg">digraph</var>. The Schreier vector is a list <code class="code">sch</code> of integers with length <code class="code">DigraphNrVertices(<var class="Arg">digraph</var>)</code> where:

<dl>
<dt><code class="code">sch[i] < 0:</code></dt>
<dd>implies that <code class="code">i</code> is an orbit representative and <code class="code">DigraphOrbitReps(<var class="Arg">digraph</var>)[-sch[i]] = i</code>.

</dd>
<dt><code class="code">sch[i] > 0:</code></dt>
<dd>implies that <code class="code">i / gens[sch[i]]</code> is one step closer to the root (or representative) of the tree, where <code class="code">gens</code> is the generators of <code class="code">DigraphGroup(<var class="Arg">digraph</var>)</code>.

</dd>
</dl>

<div class="example"><pre>
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</pre></div>

<a id="X78913684795FB256" name="X78913684795FB256"></a>

<h5>7.2-14 DigraphStabilizer</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphStabilizer</code>( <var class="Arg">digraph</var>, <var class="Arg">v</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A permutation group.

<code class="code">DigraphStabilizer</code> returns the stabilizer of the vertex <var class="Arg">v</var> under of the action of the <code class="func">DigraphGroup</code> (<a href="chap7.html#X803ACEDA7BBAC5B3">7.2-10</a>) on the set of vertices of <var class="Arg">digraph</var>.

<div class="example"><pre>
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(())
</pre></div>

<a id="X7B4F24B283C9EE28" name="X7B4F24B283C9EE28"></a>

<h5>7.2-15 IsIsomorphicDigraph</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsIsomorphicDigraph</code>( <var class="Arg">digraph1</var>, <var class="Arg">digraph2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.

This operation returns <code class="keyw">true</code> if there exists an isomorphism from the digraph <var class="Arg">digraph1</var> to the digraph <var class="Arg">digraph2</var>. See <code class="func">IsomorphismDigraphs</code> (<a href="chap7.html#X8219FE6C839D9457">7.2-17</a>) for more information about isomorphisms of digraphs.

By default, an isomorphism is found using the canonical labellings of the digraphs obtained from <a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a> by Tommi Junttila and Petteri Kaski. If <a href="https://github.com/gap-packages/NautyTracesInterface">NautyTracesInterface</a> is available, then <a href="https://pallini.di.uniroma1.it">nauty</a> by Brendan Mckay and Adolfo Piperno can be used instead; see <code class="func">DigraphsUseBliss</code> (<a href="chap7.html#X83E593F3855B122E">7.2-1</a>), and <code class="func">DigraphsUseNauty</code> (<a href="chap7.html#X83E593F3855B122E">7.2-1</a>).

<div class="example"><pre>
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</pre></div>

<a id="X7D4A1FA8868DA930" name="X7D4A1FA8868DA930"></a>

<h5>7.2-16 IsIsomorphicDigraph</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsIsomorphicDigraph</code>( <var class="Arg">digraph1</var>, <var class="Arg">digraph2</var>, <var class="Arg">colours1</var>, <var class="Arg">colours2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.

This operation tests for isomorphism of coloured digraphs. A coloured digraph can be specified by its underlying digraph <var class="Arg">digraph1</var> and its colouring <var class="Arg">colours1</var>. Let <code class="code">n</code> be the number of vertices of <var class="Arg">digraph1</var>. The colouring <var class="Arg">colours1</var> may have one of the following two forms:

<ul>
<li>a list of <code class="code">n</code> integers, where <var class="Arg">colours</var><code class="code">[i]</code> is the colour of vertex <code class="code">i</code>, using the colours <code class="code">[1 .. m]</code> for some <code class="code">m <= n</code>; or

</li>
<li>a list of non-empty disjoint lists whose union is <code class="code">DigraphVertices(<var class="Arg">digraph</var>)</code>, such that <var class="Arg">colours</var><code class="code">[i]</code> is the list of all vertices with colour <code class="code">i</code>.

</li>
</ul>
If <var class="Arg">digraph1</var> and <var class="Arg">digraph2</var> are digraphs without multiple edges, and <var class="Arg">colours1</var> and <var class="Arg">colours2</var> are colourings of <var class="Arg">digraph1</var> and <var class="Arg">digraph2</var>, respectively, then this operation returns <code class="keyw">true</code> if there exists an isomorphism between these two coloured digraphs. See <code class="func">IsomorphismDigraphs</code> (<a href="chap7.html#X7ED93C0F86D9D34F">7.2-18</a>) for more information about isomorphisms of coloured digraphs.

By default, an isomorphism is found using the canonical labellings of the digraphs obtained from <a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a> by Tommi Junttila and Petteri Kaski. If <a href="https://github.com/gap-packages/NautyTracesInterface">NautyTracesInterface</a> is available, then <a href="https://pallini.di.uniroma1.it">nauty</a> by Brendan Mckay and Adolfo Piperno can be used instead; see <code class="func">DigraphsUseBliss</code> (<a href="chap7.html#X83E593F3855B122E">7.2-1</a>), and <code class="func">DigraphsUseNauty</code> (<a href="chap7.html#X83E593F3855B122E">7.2-1</a>).

<div class="example"><pre>
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</pre></div>

<a id="X8219FE6C839D9457" name="X8219FE6C839D9457"></a>

<h5>7.2-17 IsomorphismDigraphs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsomorphismDigraphs</code>( <var class="Arg">digraph1</var>, <var class="Arg">digraph2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A permutation, or a pair of permutations, or <code class="keyw">fail</code>.

This operation returns an isomorphism between the digraphs <var class="Arg">digraph1</var> and <var class="Arg">digraph2</var> if one exists, else this operation returns <code class="keyw">fail</code>.

An isomorphism from a digraph <var class="Arg">digraph1</var> to a digraph <var class="Arg">digraph2</var> is a bijection <code class="code">p</code> from the vertices of <var class="Arg">digraph1</var> to the vertices of <var class="Arg">digraph2</var> with the following property: for all vertices <code class="code">i</code> and <code class="code">j</code> of <var class="Arg">digraph1</var>, <code class="code">[i, j]</code> is an edge of <var class="Arg">digraph1</var> if and only if <code class="code">[i ^ p, j ^ p]</code> is an edge of <var class="Arg">digraph2</var>.

If there exists such an isomorphism, then this operation returns one. The form of this isomorphism is a permutation <code class="code">p</code> of the vertices of <var class="Arg">digraph1</var> such that

<code class="code">OnDigraphs(<var class="Arg">digraph1</var>, p) = digraph2</code>. By default, an isomorphism is found using the canonical labellings of the digraphs obtained from <a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a> by Tommi Junttila and Petteri Kaski. If <a href="https://github.com/gap-packages/NautyTracesInterface">NautyTracesInterface</a> is available, then <a href="https://pallini.di.uniroma1.it">nauty</a> by Brendan Mckay and Adolfo Piperno can be used instead; see <code class="func">DigraphsUseBliss</code> (<a href="chap7.html#X83E593F3855B122E">7.2-1</a>), and <code class="func">DigraphsUseNauty</code> (<a href="chap7.html#X83E593F3855B122E">7.2-1</a>).

<div class="example"><pre>
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
</pre></div>

<a id="X7ED93C0F86D9D34F" name="X7ED93C0F86D9D34F"></a>

<h5>7.2-18 IsomorphismDigraphs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsomorphismDigraphs</code>( <var class="Arg">digraph1</var>, <var class="Arg">digraph2</var>, <var class="Arg">colours1</var>, <var class="Arg">colours2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A permutation, or <code class="keyw">fail</code>.

This operation searches for an isomorphism between coloured digraphs. A coloured digraph can be specified by its underlying digraph <var class="Arg">digraph1</var> and its colouring <var class="Arg">colours1</var>. Let <code class="code">n</code> be the number of vertices of <var class="Arg">digraph1</var>. The colouring <var class="Arg">colours1</var> may have one of the following two forms:

<ul>
<li>a list of <code class="code">n</code> integers, where <var class="Arg">colours</var><code class="code">[i]</code> is the colour of vertex <code class="code">i</code>, using the colours <code class="code">[1 .. m]</code> for some <code class="code">m <= n</code>; or

</li>
<li>a list of non-empty disjoint lists whose union is <code class="code">DigraphVertices(<var class="Arg">digraph</var>)</code>, such that <var class="Arg">colours</var><code class="code">[i]</code> is the list of all vertices with colour <code class="code">i</code>.

</li>
</ul>
An isomorphism between coloured digraphs is an isomorphism between the underlying digraphs that preserves the colourings. See <code class="func">IsomorphismDigraphs</code> (<a href="chap7.html#X8219FE6C839D9457">7.2-17</a>) for more information about isomorphisms of digraphs. More precisely, let <code class="code">f</code> be an isomorphism of digraphs from the digraph <var class="Arg">digraph1</var> (with colouring <var class="Arg">colours1</var>) to the digraph <var class="Arg">digraph2</var> (with colouring <var class="Arg">colours2</var>), and let <code class="code">p</code> be the permutation of the vertices of <var class="Arg">digraph1</var> that corresponds to <code class="code">f</code>. Then <code class="code">f</code> preserves the colourings of <var class="Arg">digraph1</var> and <var class="Arg">digraph2</var> – and hence is an isomorphism of coloured digraphs – if <code class="code"><var class="Arg">colours1</var>[i] = <var class="Arg">colours2</var>[i ^ p]</code> for all vertices <code class="code">i</code> in <var class="Arg">digraph1</var>.

This operation returns such an isomorphism if one exists, else it returns <code class="keyw">fail</code>.

By default, an isomorphism is found using the canonical labellings of the digraphs obtained from <a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a> by Tommi Junttila and Petteri Kaski. If <a href="https://github.com/gap-packages/NautyTracesInterface">NautyTracesInterface</a> is available, then <a href="https://pallini.di.uniroma1.it">nauty</a> by Brendan Mckay and Adolfo Piperno can be used instead; see <code class="func">DigraphsUseBliss</code> (<a href="chap7.html#X83E593F3855B122E">7.2-1</a>), and <code class="func">DigraphsUseNauty</code> (<a href="chap7.html#X83E593F3855B122E">7.2-1</a>).

<div class="example"><pre>
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</pre></div>

<a id="X7E1C806D81DFE15E" name="X7E1C806D81DFE15E"></a>

<h5>7.2-19 RepresentativeOutNeighbours</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RepresentativeOutNeighbours</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An immutable list of lists.

This function returns the list <code class="code">out</code> of out-neighbours of each representative of the orbits of the action of <code class="func">DigraphGroup</code> (<a href="chap7.html#X803ACEDA7BBAC5B3">7.2-10</a>) on the vertex set of the digraph <var class="Arg">digraph</var>.

More specifically, if <code class="code">reps</code> is the list of orbit representatives, then a vertex <code class="code">j</code> appears in <code class="code">out[i]</code> each time there exists an edge with source <code class="code">reps[i]</code> and range <code class="code">j</code> in <var class="Arg">digraph</var>.

If <code class="func">DigraphGroup</code> (<a href="chap7.html#X803ACEDA7BBAC5B3">7.2-10</a>) is trivial, then <code class="func">OutNeighbours</code> (<a href="chap5.html#X7E9880767AE68E00">5.2-6</a>) is returned.

<div class="example"><pre>
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 ] ]</pre></div>

<a id="X80183D4A7C51365A" name="X80183D4A7C51365A"></a>

<h5>7.2-20 IsDigraphIsomorphism</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphIsomorphism</code>( <var class="Arg">src</var>, <var class="Arg">ran</var>, <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphIsomorphism</code>( <var class="Arg">src</var>, <var class="Arg">ran</var>, <var class="Arg">x</var>, <var class="Arg">col1</var>, <var class="Arg">col2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphAutomorphism</code>( <var class="Arg">digraph</var>, <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphAutomorphism</code>( <var class="Arg">digraph</var>, <var class="Arg">x</var>, <var class="Arg">col</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.

<code class="code">IsDigraphIsomorphism</code> returns <code class="keyw">true</code> if the permutation or transformation <var class="Arg">x</var> is an isomorphism from the digraph <var class="Arg">src</var> to the digraph <var class="Arg">ran</var>.

<code class="code">IsDigraphAutomorphism</code> returns <code class="keyw">true</code> if the permutation or transformation <var class="Arg">x</var> is an automorphism of the digraph <var class="Arg">digraph</var>.

A permutation or transformation <var class="Arg">x</var> is an isomorphism from a digraph <var class="Arg">src</var> to a digraph <var class="Arg">ran</var> if the following hold:

<ul>
<li><var class="Arg">x</var> is a bijection from the vertices of <var class="Arg">src</var> to those of <var class="Arg">ran</var>;

</li>
<li><code class="code">[u ^ <var class="Arg">x</var>, v ^ <var class="Arg">x</var>]</code> is an edge of <var class="Arg">ran</var> if and only if <code class="code">[u, v]</code> is an edge of <var class="Arg">src</var>; and

</li>
<li><var class="Arg">x</var> fixes every <code class="code">i</code> which is not a vertex of <var class="Arg">src</var>.

</li>
</ul>
See also <code class="func">AutomorphismGroup</code> (<a href="chap7.html#X858C32127A190175">7.2-2</a>).

If <var class="Arg">col1</var> and <var class="Arg">col2</var>, or <var class="Arg">col</var>, are given, then they must represent vertex colourings; see <code class="func">AutomorphismGroup</code> (<a href="chap7.html#X877732B1783C391B">7.2-5</a>) for details of the permissible values for these arguments. The homomorphism must then also have the property:

<ul>
<li><code class="code">col1[i] = col2[i ^ x]</code> for all vertices <code class="code">i</code> of <var class="Arg">src</var>, for <code class="code">IsDigraphIsomorphism</code>.

</li>
<li><code class="code">col[i] = col[i ^ x]</code> for all vertices <code class="code">i</code> of <var class="Arg">digraph</var>, for <code class="code">IsDigraphAutomorphism</code>.

</li>
</ul>
For some digraphs, it can be faster to use <code class="code">IsDigraphAutomorphism</code> than to test membership in the automorphism group of <var class="Arg">digraph</var>.

<div class="example"><pre>
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
</pre></div>

<a id="X7F16B8B3825A627A" name="X7F16B8B3825A627A"></a>

<h5>7.2-21 IsDigraphColouring</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphColouring</code>( <var class="Arg">digraph</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphColouring</code>( <var class="Arg">digraph</var>, <var class="Arg">t</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.

The operation <code class="code">IsDigraphColouring</code> verifies whether or not the list <var class="Arg">list</var> describes a proper colouring of the digraph <var class="Arg">digraph</var>.

A list <var class="Arg">list</var> describes a proper colouring of a digraph <var class="Arg">digraph</var> if <var class="Arg">list</var> consists of positive integers, the length of <var class="Arg">list</var> equals the number of vertices in <var class="Arg">digraph</var>, and for any vertices <code class="code">u, v</code> of <var class="Arg">digraph</var> if <code class="code">u</code> and <code class="code">v</code> are adjacent, then <code class="code"><var class="Arg">list</var>[u] >< <var class="Arg">list</var>[v]</code>.

A transformation <var class="Arg">t</var> describes a proper colouring of a digraph <var class="Arg">digraph</var>, if <code class="code">ImageListOfTransformation(<var class="Arg">t</var>, DigraphNrVertices(<var class="Arg">digraph</var>))</code> is a proper colouring of <var class="Arg">digraph</var>.

See also <code class="func">IsDigraphHomomorphism</code> (<a href="chap7.html#X80FE9FCB79718A61">7.3-10</a>).

<div class="example"><pre>
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
</pre></div>

<a id="X7D4378F27B49C9AC" name="X7D4378F27B49C9AC"></a>

<h5>7.2-22 MaximalCommonSubdigraph</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MaximalCommonSubdigraph</code>( <var class="Arg">D1</var>, <var class="Arg">D2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list containing a digraph and two transformations.

If <var class="Arg">D1</var> and <var class="Arg">D2</var> are digraphs without multiple edges, then <code class="code">MaximalCommonSubdigraph</code> returns a maximal common subgraph <code class="code">M</code> of <var class="Arg">D1</var> and <var class="Arg">D2</var> with the maximum number of vertices. So <code class="code">M</code> is a digraph which embeds into both <var class="Arg">D1</var> and <var class="Arg">D2</var> and has the largest number of vertices among such digraphs. It returns a list <code class="code">[M, t1, t2]</code> where <code class="code">M</code> is the maximal common subdigraph and <code class="code">t1, t2</code> are transformations embedding <code class="code">M</code> into <var class="Arg">D1</var> and <var class="Arg">D2</var> respectively.

<div class="example"><pre>
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 ]
</pre></div>

<a id="X7B99C75B8021FCDA" name="X7B99C75B8021FCDA"></a>

<h5>7.2-23 MinimalCommonSuperdigraph</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalCommonSuperdigraph</code>( <var class="Arg">D1</var>, <var class="Arg">D2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list containing a digraph and two transformations.

If <var class="Arg">D1</var> and <var class="Arg">D2</var> are digraphs without multiple edges, then <code class="code">MinimalCommonSuperdigraph</code> returns a minimal common superdigraph <code class="code">M</code> of <var class="Arg">D1</var> and <var class="Arg">D2</var> with the minimum number of vertices. So <code class="code">M</code> is a digraph into which both <var class="Arg">D1</var> and <var class="Arg">D2</var> embed and has the smallest number of vertices among such digraphs. It returns a list <code class="code">[M, t1, t2]</code> where <code class="code">M</code> is the minimal common superdigraph and <code class="code">t1, t2</code> are transformations embedding <var class="Arg">D1</var> and <var class="Arg">D2</var> respectively into <code class="code">M</code>.

<div class="example"><pre>
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 ]
</pre></div>

<a id="X7E1A02FE8384C03C" name="X7E1A02FE8384C03C"></a>

<h4>7.3 Homomorphisms of digraphs</h4>

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.

<a id="X79ABF0E783FD67C7" name="X79ABF0E783FD67C7"></a>

<h5>7.3-1 HomomorphismDigraphsFinder</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ HomomorphismDigraphsFinder</code>( <var class="Arg">D1</var>, <var class="Arg">D2</var>, <var class="Arg">hook</var>, <var class="Arg">user_param</var>, <var class="Arg">max_results</var>, <var class="Arg">hint</var>, <var class="Arg">injective</var>, <var class="Arg">image</var>, <var class="Arg">partial_map</var>, <var class="Arg">colors1</var>, <var class="Arg">colors2</var>[, <var class="Arg">order</var>, <var class="Arg">aut_grp</var>] )</td><td class="tdright">( function )</td></tr></table></div>
Returns: The argument <var class="Arg">user_param</var>.

This function finds homomorphisms from the digraph <var class="Arg">D1</var> to the digraph <var class="Arg">D2</var> subject to the conditions imposed by the other arguments as described below.

If <code class="code">f</code> and <code class="code">g</code> are homomorphisms found by <code class="code">HomomorphismDigraphsFinder</code>, then <code class="code">f</code> cannot be obtained from <code class="code">g</code> by right multiplying by an automorphism of <var class="Arg">D2</var> in <var class="Arg">aut_grp</var>.

<dl>
<dt><var class="Arg">hook</var></dt>
<dd>This argument should be a function or <code class="keyw">fail</code>.

If <var class="Arg">hook</var> is a function, then it must have two arguments <var class="Arg">user_param</var> (see below) and a transformation <code class="code">t</code>. The function <code class="code"><var class="Arg">hook</var>(<var class="Arg">user_param</var>, t)</code> is called every time a new homomorphism <code class="code">t</code> is found by <code class="code">HomomorphismDigraphsFinder</code>. If the function returns <code class="keyw">true</code>, then <code class="code">HomomorphismDigraphsFinder</code> 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 <code class="code">HomomorphismDigraphsFinder</code>.

If <var class="Arg">hook</var> is <code class="keyw">fail</code>, then a default function is used which simply adds every new homomorphism found by <code class="code">HomomorphismDigraphsFinder</code> to <var class="Arg">user_param</var>, which must be a mutable list in this case.

</dd>
<dt><var class="Arg">user_param</var></dt>
<dd>If <var class="Arg">hook</var> is a function, then <var class="Arg">user_param</var> can be any GAP object. The object <var class="Arg">user_param</var> is used as the first argument of the function <var class="Arg">hook</var>. For example, <var class="Arg">user_param</var> might be a transformation semigroup, and <code class="code"><var class="Arg">hook</var>(<var class="Arg">user_param</var>, t)</code> might set <var class="Arg">user_param</var> to be the closure of <var class="Arg">user_param</var> and <code class="code">t</code>.

If the value of <var class="Arg">hook</var> is <code class="keyw">fail</code>, then the value of <var class="Arg">user_param</var> must be a mutable list.

</dd>
<dt><var class="Arg">max_results</var></dt>
<dd>This argument should be a positive integer or <code class="keyw">infinity</code>. <code class="code">HomomorphismDigraphsFinder</code> will return after it has found <var class="Arg">max_results</var> homomorphisms or the search is complete, whichever happens first.

</dd>
<dt><var class="Arg">hint</var></dt>
<dd>This argument should be a positive integer or <code class="keyw">fail</code>.

If <var class="Arg">hint</var> is a positive integer, then only homorphisms of rank <var class="Arg">hint</var> are found.

If <var class="Arg">hint</var> is <code class="keyw">fail</code>, then no restriction is put on the rank of homomorphisms found.

</dd>
<dt><var class="Arg">injective</var></dt>
<dd>This argument should be <code class="code">0</code>, <code class="code">1</code>, or <code class="code">2</code>. If it is <code class="code">2</code>, then only embeddings are found, if it is <code class="code">1</code>, then only injective homomorphisms are found, and if it is <code class="code">0</code> there are no restrictions imposed by this argument.

For backwards compatibility, <var class="Arg">injective</var> can also be <code class="keyw">false</code> or <code class="keyw">true</code> which correspond to the values <code class="code">0</code> and <code class="code">1</code> described in the previous paragraph, respectively.

</dd>
<dt><var class="Arg">image</var></dt>
<dd>This argument should be a subset of the vertices of the graph <var class="Arg">D2</var>. <code class="code">HomomorphismDigraphsFinder</code> only finds homomorphisms from <var class="Arg">D1</var> to the subgraph of <var class="Arg">D2</var> induced by the vertices <var class="Arg">image</var>.

The returned homomorphisms (if any) are still "up to the action" of the group specified by <var class="Arg">aut_grp</var> (which is the entire automorphism group by default). This might generate unexpected results. For example, if <var class="Arg">D1</var> has automorphism group where one orbit consists of, say, <code class="code">1</code> and <code class="code">2</code>, then <code class="code">HomomorphismDigraphsFinder</code> will only attempt to find homomorphisms mapping <code class="code">1</code> to <code class="code">1</code>, and if there are no such homomorphisms with image set equal to <var class="Arg">image</var>, then no homomorphisms will be returned (even if there is a homomorphism from <var class="Arg">D1</var> to <var class="Arg">D2</var> mapping <code class="code">1</code> to <code class="code">2</code>). To ensure that that all homomorphisms with image set equal to <var class="Arg">image</var> are considered it is necessary for the last argument <var class="Arg">aut_grp</var> to be the trivial permutation group.

</dd>
<dt><var class="Arg">partial_map</var></dt>
<dd>This argument should be a partial map from <var class="Arg">D1</var> to <var class="Arg">D2</var>, that is, a (not necessarily dense) list of vertices of the digraph <var class="Arg">D2</var> of length no greater than the number vertices in the digraph <var class="Arg">D1</var>. <code class="code">HomomorphismDigraphsFinder</code> only finds homomorphisms extending <var class="Arg">partial_map</var> (if any).

</dd>
<dt><var class="Arg">colors1</var></dt>
<dd>This should be a list representing possible colours of vertices in the digraph <var class="Arg">D1</var>; see <code class="func">AutomorphismGroup</code> (<a href="chap7.html#X877732B1783C391B">7.2-5</a>) for details of the permissible values for this argument.

</dd>
<dt><var class="Arg">colors2</var></dt>
<dd>This should be a list representing possible colours of vertices in the digraph <var class="Arg">D2</var>; see <code class="func">AutomorphismGroup</code> (<a href="chap7.html#X877732B1783C391B">7.2-5</a>) for details of the permissible values for this argument.

</dd>
<dt><var class="Arg">order</var></dt>
<dd>The optional argument <var class="Arg">order</var> specifies the order the vertices in <var class="Arg">D1</var> 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 <code class="func">DigraphWelshPowellOrder</code> (<a href="chap7.html#X7F9CB3B27B9590DB">7.3-17</a>), i.e. vertices ordered from highest to lowest degree.

</dd>
<dt><var class="Arg">aut_grp</var></dt>
<dd>The optional argument <var class="Arg">aut_grp</var> should be a subgroup of the automorphism group of <var class="Arg">D2</var>. This function returns unique representatives of the homomorphisms found up to right multiplication by <var class="Arg">aut_grp</var>. If this argument is not specific, it defaults to the full automorphism group of <var class="Arg">D2</var>, which may be costly to calculate.

</dd>
</dl>

<div class="example"><pre>
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 ] ) ]</pre></div>

<a id="X85E9B019877AD7FE" name="X85E9B019877AD7FE"></a>

<h5>7.3-2 DigraphHomomorphism</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphHomomorphism</code>( <var class="Arg">digraph1</var>, <var class="Arg">digraph2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A transformation, or <code class="keyw">fail</code>.

A homomorphism from <var class="Arg">digraph1</var> to <var class="Arg">digraph2</var> is a mapping from the vertex set of <var class="Arg">digraph1</var> to a subset of the vertices of <var class="Arg">digraph2</var>, such that every pair of vertices <code class="code">[i,j]</code> which has an edge <code class="code">i->j</code> is mapped to a pair of vertices <code class="code">[a,b]</code> which has an edge <code class="code">a->b</code>. Note that non-adjacent vertices can still be mapped to adjacent vertices.

<code class="code">DigraphHomomorphism</code> returns a single homomorphism between <var class="Arg">digraph1</var> and <var class="Arg">digraph2</var> if it exists, otherwise it returns <code class="keyw">fail</code>.

<div class="example"><pre>
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
</pre></div>

<a id="X8653EDA183E06D05" name="X8653EDA183E06D05"></a>

<h5>7.3-3 HomomorphismsDigraphs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ HomomorphismsDigraphs</code>( <var class="Arg">digraph1</var>, <var class="Arg">digraph2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ HomomorphismsDigraphsRepresentatives</code>( <var class="Arg">digraph1</var>, <var class="Arg">digraph2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of transformations.

<code class="code">HomomorphismsDigraphsRepresentatives</code> finds every <code class="func">DigraphHomomorphism</code> (<a href="chap7.html#X85E9B019877AD7FE">7.3-2</a>) between <var class="Arg">digraph1</var> and <var class="Arg">digraph2</var>, up to right multiplication by an element of the <code class="func">AutomorphismGroup</code> (<a href="chap7.html#X858C32127A190175">7.2-2</a>) of <var class="Arg">digraph2</var>. In other words, every homomorphism <code class="code">f</code> between <var class="Arg">digraph1</var> and <var class="Arg">digraph2</var> can be written as the composition <code class="code">f = g * x</code>, where <code class="code">g</code> is one of the <code class="code">HomomorphismsDigraphsRepresentatives</code> and <code class="code">x</code> is an automorphism of <var class="Arg">digraph2</var>.

<code class="code">HomomorphismsDigraphs</code> returns all homomorphisms between <var class="Arg">digraph1</var> and <var class="Arg">digraph2</var>.

<div class="example"><pre>
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 ] ) ]
</pre></div>

<a id="X82D0FCD87D47ACA8" name="X82D0FCD87D47ACA8"></a>

<h5>7.3-4 DigraphMonomorphism</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphMonomorphism</code>( <var class="Arg">digraph1</var>, <var class="Arg">digraph2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A transformation, or <code class="keyw">fail</code>.

<code class="code">DigraphMonomorphism</code> returns a single injective <code class="func">DigraphHomomorphism</code> (<a href="chap7.html#X85E9B019877AD7FE">7.3-2</a>) between <var class="Arg">digraph1</var> and <var class="Arg">digraph2</var> if one exists, otherwise it returns <code class="keyw">fail</code>.

<div class="example"><pre>
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 ] )
</pre></div>

<a id="X84B4BDB984C2A9A8" name="X84B4BDB984C2A9A8"></a>

<h5>7.3-5 MonomorphismsDigraphs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MonomorphismsDigraphs</code>( <var class="Arg">digraph1</var>, <var class="Arg">digraph2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MonomorphismsDigraphsRepresentatives</code>( <var class="Arg">digraph1</var>, <var class="Arg">digraph2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of transformations.

These operations behave the same as <code class="func">HomomorphismsDigraphs</code> (<a href="chap7.html#X8653EDA183E06D05">7.3-3</a>) and <code class="func">HomomorphismsDigraphsRepresentatives</code> (<a href="chap7.html#X8653EDA183E06D05">7.3-3</a>), except they only return injective homomorphisms.

<div class="example"><pre>
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 ] ) ]
</pre></div>

<a id="X7CB5AD9F861684FD" name="X7CB5AD9F861684FD"></a>

<h5>7.3-6 DigraphEpimorphism</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphEpimorphism</code>( <var class="Arg">digraph1</var>, <var class="Arg">digraph2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A transformation, or <code class="keyw">fail</code>.

<code class="code">DigraphEpimorphism</code> returns a single surjective <code class="func">DigraphHomomorphism</code> (<a href="chap7.html#X85E9B019877AD7FE">7.3-2</a>) between <var class="Arg">digraph1</var> and <var class="Arg">digraph2</var> if one exists, otherwise it returns <code class="keyw">fail</code>.

<div class="example"><pre>
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 ] )
</pre></div>

<a id="X7DFB1F5D873937B3" name="X7DFB1F5D873937B3"></a>

<h5>7.3-7 EpimorphismsDigraphs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EpimorphismsDigraphs</code>( <var class="Arg">digraph1</var>, <var class="Arg">digraph2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EpimorphismsDigraphsRepresentatives</code>( <var class="Arg">digraph1</var>, <var class="Arg">digraph2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of transformations.

These operations behave the same as <code class="func">HomomorphismsDigraphs</code> (<a href="chap7.html#X8653EDA183E06D05">7.3-3</a>) and <code class="func">HomomorphismsDigraphsRepresentatives</code> (<a href="chap7.html#X8653EDA183E06D05">7.3-3</a>), except they only return surjective homomorphisms.

<div class="example"><pre>
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 ] ) ]
</pre></div>

<a id="X7AD04CC186E86CCA" name="X7AD04CC186E86CCA"></a>

<h5>7.3-8 DigraphEmbedding</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphEmbedding</code>( <var class="Arg">digraph1</var>, <var class="Arg">digraph2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A transformation, or <code class="keyw">fail</code>.

An embedding of a digraph <var class="Arg">digraph1</var> into another digraph <var class="Arg">digraph2</var> is a <code class="func">DigraphMonomorphism</code> (<a href="chap7.html#X82D0FCD87D47ACA8">7.3-4</a>) from <var class="Arg">digraph1</var> to <var class="Arg">digraph2</var> which has the additional property that a pair of vertices <code class="code">[i, j]</code> which have no edge <code class="code">i -> j</code> in <var class="Arg">digraph1</var> are mapped to a pair of vertices <code class="code">[a, b]</code> which have no edge <code class="code">a->b</code> in <var class="Arg">digraph2</var>.

In other words, an embedding <code class="code">t</code> is an isomorphism from <var class="Arg">digraph1</var> to the <code class="func">InducedSubdigraph</code> (<a href="chap3.html#X83C51DA182CCEA2F">3.3-3</a>) of <var class="Arg">digraph2</var> on the image of <code class="code">t</code>.

<code class="code">DigraphEmbedding</code> returns a single embedding if one exists, otherwise it returns <code class="keyw">fail</code>.

<div class="example"><pre>
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 ] )
</pre></div>

<a id="X82EBDF137EEDC5FD" name="X82EBDF137EEDC5FD"></a>

<h5>7.3-9 EmbeddingsDigraphs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EmbeddingsDigraphs</code>( <var class="Arg">D1</var>, <var class="Arg">D2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EmbeddingsDigraphsRepresentatives</code>( <var class="Arg">D1</var>, <var class="Arg">D2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of transformations.

These operations behave the same as <code class="func">HomomorphismsDigraphs</code> (<a href="chap7.html#X8653EDA183E06D05">7.3-3</a>) and <code class="func">HomomorphismsDigraphsRepresentatives</code> (<a href="chap7.html#X8653EDA183E06D05">7.3-3</a>), except they only return embeddings of <var class="Arg">D1</var> into <var class="Arg">D2</var>.

See also <code class="func">IsDigraphEmbedding</code> (<a href="chap7.html#X7D6B5A0887903810">7.3-11</a>).

<div class="example"><pre>
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 ] ) ]
</pre></div>

<a id="X80FE9FCB79718A61" name="X80FE9FCB79718A61"></a>

<h5>7.3-10 IsDigraphHomomorphism</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphHomomorphism</code>( <var class="Arg">src</var>, <var class="Arg">ran</var>, <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphHomomorphism</code>( <var class="Arg">src</var>, <var class="Arg">ran</var>, <var class="Arg">x</var>, <var class="Arg">col1</var>, <var class="Arg">col2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphEpimorphism</code>( <var class="Arg">src</var>, <var class="Arg">ran</var>, <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphEpimorphism</code>( <var class="Arg">src</var>, <var class="Arg">ran</var>, <var class="Arg">x</var>, <var class="Arg">col1</var>, <var class="Arg">col2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphMonomorphism</code>( <var class="Arg">src</var>, <var class="Arg">ran</var>, <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphMonomorphism</code>( <var class="Arg">src</var>, <var class="Arg">ran</var>, <var class="Arg">x</var>, <var class="Arg">col1</var>, <var class="Arg">col2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphEndomorphism</code>( <var class="Arg">digraph</var>, <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphEndomorphism</code>( <var class="Arg">digraph</var>, <var class="Arg">x</var>, <var class="Arg">col</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.

<code class="code">IsDigraphHomomorphism</code> returns <code class="keyw">true</code> if the permutation or transformation <var class="Arg">x</var> is a homomorphism from the digraph <var class="Arg">src</var> to the digraph <var class="Arg">ran</var>.

<code class="code">IsDigraphEpimorphism</code> returns <code class="keyw">true</code> if the permutation or transformation <var class="Arg">x</var> is a surjective homomorphism from the digraph <var class="Arg">src</var> to the digraph <var class="Arg">ran</var>.

<code class="code">IsDigraphMonomorphism</code> returns <code class="keyw">true</code> if the permutation or transformation <var class="Arg">x</var> is an injective homomorphism from the digraph <var class="Arg">src</var> to the digraph <var class="Arg">ran</var>.

<code class="code">IsDigraphEndomorphism</code> returns <code class="keyw">true</code> if the permutation or transformation <var class="Arg">x</var> is an endomorphism of the digraph <var class="Arg">digraph</var>.

A permutation or transformation <var class="Arg">x</var> is a homomorphism from a digraph <var class="Arg">src</var> to a digraph <var class="Arg">ran</var> if the following hold:

<ul>
<li><code class="code">[u ^ <var class="Arg">x</var>, v ^ <var class="Arg">x</var>]</code> is an edge of <var class="Arg">ran</var> whenever <code class="code">[u, v]</code> is an edge of <var class="Arg">src</var>; and

</li>
<li><var class="Arg">x</var> maps the vertices of <var class="Arg">src</var> to a subset of the vertices of <var class="Arg">ran</var>, i.e. <code class="code">IsSubset(DigraphVertices(<var class="Arg">ran</var>), OnSets(DigraphVertices(<var class="Arg">src</var>), <var class="Arg">x</var>))</code> is <code class="keyw">true</code>.

</li>
</ul>
Note that if <code class="code">i</code> is any integer greater than <code class="code">DigraphNrVertice(<var class="Arg">src</var>)</code>, then the action of <var class="Arg">x</var> on <code class="code">i</code> is ignored by this function. One consequence of this is that distinct transformations or permutations might represent the same homomorphism. For example, if <var class="Arg">src</var> and <var class="Arg">ran</var> are <code class="code">CycleDigraph(2)</code>, then both the permutations <code class="code">(1, 2)</code> and <code class="code">(1, 2)(3, 4)</code> represent the same automorphism of <var class="Arg">src</var>.

See also <code class="func">GeneratorsOfEndomorphismMonoid</code> (<a href="chap7.html#X7E93B268823F6478">7.3-14</a>).

If <var class="Arg">col1</var> and <var class="Arg">col2</var>, or <var class="Arg">col</var>, are given, then they must represent vertex colourings; see <code class="func">AutomorphismGroup</code> (<a href="chap7.html#X877732B1783C391B">7.2-5</a>) for details of the permissible values for these argument. The homomorphism must then also have the property:

<ul>
<li><code class="code">col[i] = col[i ^ x]</code> for all vertices <code class="code">i</code> of <var class="Arg">digraph</var>, in the case of <code class="code">IsDigraphEndomorphism</code>.

</li>
<li><code class="code">col1[i] = col2[i ^ x]</code> for all vertices <code class="code">i</code> of <var class="Arg">src</var>, in the cases of the other operations.

</li>
</ul>
See also <code class="func">DigraphsRespectsColouring</code> (<a href="chap7.html#X7F80709A80CBFA98">7.3-13</a>).

<div class="example"><pre>
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</pre></div>

<a id="X7D6B5A0887903810" name="X7D6B5A0887903810"></a>

<h5>7.3-11 IsDigraphEmbedding</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphEmbedding</code>( <var class="Arg">src</var>, <var class="Arg">ran</var>, <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphEmbedding</code>( <var class="Arg">src</var>, <var class="Arg">ran</var>, <var class="Arg">x</var>, <var class="Arg">col1</var>, <var class="Arg">col2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.

<code class="code">IsDigraphEmbedding</code> returns <code class="keyw">true</code> if the permutation or transformation <var class="Arg">x</var> is a embedding of the digraph <var class="Arg">src</var> into the digraph <var class="Arg">ran</var>, while respecting the colourings <var class="Arg">col1</var> and <var class="Arg">col2</var> if given.

A permutation or transformation <var class="Arg">x</var> is a embedding of a digraph <var class="Arg">src</var> into a digraph <var class="Arg">ran</var> if <var class="Arg">x</var> is a monomorphism from <var class="Arg">src</var> to <var class="Arg">ran</var> and the inverse of <var class="Arg">x</var> is a monomorphism from the subdigraph of <var class="Arg">ran</var> induced by the image of <var class="Arg">x</var> to <var class="Arg">src</var>. See also <code class="func">IsDigraphHomomorphism</code> (<a href="chap7.html#X80FE9FCB79718A61">7.3-10</a>).

<div class="example"><pre>
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</pre></div>

<a id="X87E60FB17BC444EF" name="X87E60FB17BC444EF"></a>

<h5>7.3-12 SubdigraphsMonomorphisms</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SubdigraphsMonomorphisms</code>( <var class="Arg">digraph1</var>, <var class="Arg">digraph2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SubdigraphsMonomorphismsRepresentatives</code>( <var class="Arg">digraph1</var>, <var class="Arg">digraph2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of transformations.

These operations behave the same as <code class="func">HomomorphismsDigraphs</code> (<a href="chap7.html#X8653EDA183E06D05">7.3-3</a>) and <code class="func">HomomorphismsDigraphsRepresentatives</code> (<a href="chap7.html#X8653EDA183E06D05">7.3-3</a>), 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 <var class="Arg">digraph2</var> that are isomorphic to <var class="Arg">digraph1</var>. Note that the subdigraphs of the previous sentence are those obtained by applying the corresponding monomorphism to the vertices and the edges of <var class="Arg">digraph1</var>, and are therefore possibly strictly contained in the induced subdigraph on the same vertex set.

<div class="example"><pre>
gap> Set(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 ] ) ]
</pre></div>

<a id="X7F80709A80CBFA98" name="X7F80709A80CBFA98"></a>

<h5>7.3-13 DigraphsRespectsColouring</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphsRespectsColouring</code>( <var class="Arg">src</var>, <var class="Arg">ran</var>, <var class="Arg">x</var>, <var class="Arg">col1</var>, <var class="Arg">col2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.

The operation <code class="code">DigraphsRespectsColouring</code> verifies whether or not the permutation or transformation <var class="Arg">x</var> respects the vertex colourings <var class="Arg">col1</var> and <var class="Arg">col2</var> of the digraphs <var class="Arg">src</var> and <var class="Arg">range</var>. That is, <code class="code">DigraphsRespectsColouring</code> returns <code class="keyw">true</code> if and only if for all vertices <code class="code">i</code> of <var class="Arg">src</var>, <code class="code">col1[i] = col2[i ^ x]</code>.

<div class="example"><pre>
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
</pre></div>

<a id="X7E93B268823F6478" name="X7E93B268823F6478"></a>

<h5>7.3-14 GeneratorsOfEndomorphismMonoid</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneratorsOfEndomorphismMonoid</code>( <var class="Arg">digraph</var>[, <var class="Arg">colors</var>][, <var class="Arg">limit</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneratorsOfEndomorphismMonoidAttr</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of transformations.

An endomorphism of <var class="Arg">digraph</var> is a homomorphism <code class="func">DigraphHomomorphism</code> (<a href="chap7.html#X85E9B019877AD7FE">7.3-2</a>) from <var class="Arg">digraph</var> back to itself. <code class="code">GeneratorsOfEndomorphismMonoid</code>, called with a single argument, returns a generating set for the monoid of all endomorphisms of <var class="Arg">digraph</var>. If <var class="Arg">digraph</var> belongs to <code class="func">IsImmutableDigraph</code> (<a href="chap3.html#X7CAFAA89804F80BD">3.1-3</a>), then the value of <code class="code">GeneratorsOfEndomorphismMonoid</code> will not be recomputed on future calls.

If the <var class="Arg">colors</var> argument is specified, then <code class="code">GeneratorsOfEndomorphismMonoid</code> will return a generating set for the monoid of endomorphisms which respect the given colouring. The colouring <var class="Arg">colors</var> can be in one of two forms:

<ul>
<li>A list of positive integers of size the number of vertices of <var class="Arg">digraph</var>, where <var class="Arg">colors</var><code class="code">[i]</code> is the colour of vertex <code class="code">i</code>.

</li>
<li>A list of lists, such that <var class="Arg">colors</var><code class="code">[i]</code> is a list of all vertices with colour <code class="code">i</code>.

</li>
</ul>
If the <var class="Arg">limit</var> argument is specified, then it will return only the first <var class="Arg">limit</var> homomorphisms, where <var class="Arg">limit</var> must be a positive integer or <code class="code">infinity</code>.

<div class="example"><pre>
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 ]
</pre></div>

<a id="X86D0A74B83D6B9A7" name="X86D0A74B83D6B9A7"></a>

<h5>7.3-15 DigraphColouring</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphColouring</code>( <var class="Arg">digraph</var>, <var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A transformation, or <code class="keyw">fail</code>.

A proper colouring of a digraph is a labelling of its vertices in such a way that adjacent vertices have different labels. A proper <code class="code">n</code>-colouring is a proper colouring that uses exactly <code class="code">n</code> colours. Equivalently, a proper (<code class="code">n</code>-)colouring of a digraph can be defined to be a <code class="func">DigraphEpimorphism</code> (<a href="chap7.html#X7CB5AD9F861684FD">7.3-6</a>) from a digraph onto the complete digraph (with <code class="code">n</code> vertices); see <code class="func">CompleteDigraph</code> (<a href="chap3.html#X812417E278198D9C">3.5-13</a>). Note that a digraph with loops (<code class="func">DigraphHasLoops</code> (<a href="chap6.html#X7D92935C7D535187">6.2-1</a>)) does not have a proper <code class="code">n</code>-colouring for any value <code class="code">n</code>.

If <var class="Arg">digraph</var> is a digraph and <var class="Arg">n</var> is a non-negative integer, then <code class="code">DigraphColouring(<var class="Arg">digraph</var>, <var class="Arg">n</var>)</code> returns an epimorphism from <var class="Arg">digraph</var> onto the complete digraph with <var class="Arg">n</var> vertices if one exists, else it returns <code class="keyw">fail</code>.

See also <code class="func">DigraphGreedyColouring</code> (<a href="chap7.html#X7AB7200D831013C1">7.3-16</a>) and

Note that a digraph with at least two vertices has a 2-colouring if and only if it is bipartite, see <code class="func">IsBipartiteDigraph</code> (<a href="chap6.html#X860CFB0C8665F356">6.2-3</a>).

<div class="example"><pre>
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 ] )
</pre></div>

<a id="X7AB7200D831013C1" name="X7AB7200D831013C1"></a>

<h5>7.3-16 DigraphGreedyColouring</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphGreedyColouring</code>( <var class="Arg">digraph</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphGreedyColouring</code>( <var class="Arg">digraph</var>, <var class="Arg">func</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphGreedyColouring</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A transformation, or <code class="keyw">fail</code>.

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 (<code class="func">DigraphHasLoops</code> (<a href="chap6.html#X7D92935C7D535187">6.2-1</a>)) does not have any proper colouring.

If <var class="Arg">digraph</var> is a digraph and <var class="Arg">order</var> is a dense list consisting of all of the vertices of <var class="Arg">digraph</var> (in any order), then <code class="code">DigraphGreedyColouring</code> uses a greedy algorithm with the specified order to obtain some proper colouring of <var class="Arg">digraph</var>, which may not use the minimal number of colours.

If <var class="Arg">digraph</var> is a digraph and <var class="Arg">func</var> is a function whose argument is a digraph, and that returns a dense list <var class="Arg">order</var>, then <code class="code">DigraphGreedyColouring(<var class="Arg">digraph</var>, <var class="Arg">func</var>)</code> returns <code class="code">DigraphGreedyColouring(<var class="Arg">digraph</var>, <var class="Arg">func</var>(<var class="Arg">digraph</var>))</code>.

If the optional second argument (either a list or a function), is not specified, then <code class="func">DigraphWelshPowellOrder</code> (<a href="chap7.html#X7F9CB3B27B9590DB">7.3-17</a>) is used by default.

See also <code class="func">DigraphColouring</code> (<a href="chap7.html#X86D0A74B83D6B9A7">7.3-15</a>).

<div class="example"><pre>
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 ] )
</pre></div>

<a id="X7F9CB3B27B9590DB" name="X7F9CB3B27B9590DB"></a>

<h5>7.3-17 DigraphWelshPowellOrder</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphWelshPowellOrder</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of the vertices.

<code class="code">DigraphWelshPowellOrder</code> returns a list of all of the vertices of the digraph <var class="Arg">digraph</var> ordered according to the sum of the number of out- and in-neighbours, from highest to lowest.

<div class="example"><pre>
gap> DigraphWelshPowellOrder(Digraph([[4], [9], [9], [],
> [4, 6, 9], [1], [], [],
> [4, 5], [4, 5]]));
[ 5, 9, 4, 1, 6, 10, 2, 3, 7, 8 ]
</pre></div>

<a id="X807D49358529A37C" name="X807D49358529A37C"></a>

<h5>7.3-18 ChromaticNumber</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ChromaticNumber</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
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 <code class="func">DigraphEpimorphism</code> (<a href="chap7.html#X7CB5AD9F861684FD">7.3-6</a>) from a digraph onto a complete digraph.

If <var class="Arg">digraph</var> is a digraph without loops (see <code class="func">DigraphHasLoops</code> (<a href="chap6.html#X7D92935C7D535187">6.2-1</a>), then <code class="code">ChromaticNumber</code> returns the least non-negative integer <code class="code">n</code> such that there is a proper colouring of <var class="Arg">digraph</var> with <code class="code">n</code> colours. In other words, for a digraph with at least one vertex, <code class="code">ChromaticNumber</code> returns the least number <code class="code">n</code> such that <code class="code">DigraphColouring(<var class="Arg">digraph</var>, n)</code> does not return <code class="keyw">fail</code>. See <code class="func">DigraphColouring</code> (<a href="chap7.html#X86D0A74B83D6B9A7">7.3-15</a>).

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:

<ul>
<li><code class="code">lawler</code> - Lawler's Algorithm <a href="chapBib.html#biBLaw1976">[Law76]</a>

</li>
<li><code class="code">byskov</code> - Byskov's Algorithm <a href="chapBib.html#biBBys2002">[Bys02]</a>

</li>
<li><code class="code">zykov</code> - Zykov's Algorithm <a href="chapBib.html#biBCorneil1973">[CG73]</a>

</li>
<li><code class="code">christofides</code> - Christofides's Algorithm <a href="chapBib.html#biBWang1974">[Wan74]</a>

</li>
</ul>

<div class="example"><pre>
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
</pre></div>

<a id="X863487EF7D64EF56" name="X863487EF7D64EF56"></a>

<h5>7.3-19 DigraphCore</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphCore</code>( <var class="Arg">D</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of positive integers.

If <var class="Arg">D</var> is a digraph, then <code class="code">DigraphCore</code> returns a list of vertices corresponding to the <code class="code">core</code> of <var class="Arg">D</var>. In particular, the subdigraph of <var class="Arg">D</var> induced by this list is isomorphic to the core of <var class="Arg">D</var>.

The core of a digraph <code class="code">D</code> is the minimal subdigraph <var class="Arg">C</var> of <code class="code">D</code> which is a homomorphic image of <code class="code">D</code>. The core of a digraph is unique up to isomorphism.

<div class="example"><pre>
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 ]
</pre></div>

<a id="X7EEA340C81FCA52D" name="X7EEA340C81FCA52D"></a>

<h5>7.3-20 LatticeDigraphEmbedding</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LatticeDigraphEmbedding</code>( <var class="Arg">L1</var>, <var class="Arg">L2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A transformation, or <code class="keyw">fail</code>.

If <var class="Arg">L1</var> and <var class="Arg">L2</var> are lattice digraphs (<code class="func">IsLatticeDigraph</code> (<a href="chap6.html#X78D3E17B7F737516">6.4-3</a>) returns <code class="keyw">true</code>, then <code class="code">LatticeDigraphEmbedding</code> returns a single injective <code class="func">DigraphHomomorphism</code> (<a href="chap7.html#X85E9B019877AD7FE">7.3-2</a>) between <var class="Arg">L1</var> and <var class="Arg">L2</var>, with the property that it is a lattice homomorphism. If no such homomorphism exists, <code class="keyw">fail</code> 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 <code class="code">map</code> is an embedding, in the sense that the inverse of <code class="code">map</code> is a lattice homomorphism also.

<div class="example"><pre>
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
</pre></div>

<a id="X7E183D4979D324EF" name="X7E183D4979D324EF"></a>

<h5>7.3-21 IsLatticeHomomorphism</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsLatticeHomomorphism</code>( <var class="Arg">L1</var>, <var class="Arg">L2</var>, <var class="Arg">map</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsLatticeEpimorphism</code>( <var class="Arg">L1</var>, <var class="Arg">L2</var>, <var class="Arg">map</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsLatticeEmbedding</code>( <var class="Arg">L1</var>, <var class="Arg">L2</var>, <var class="Arg">map</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsLatticeMonomorphism</code>( <var class="Arg">L1</var>, <var class="Arg">L2</var>, <var class="Arg">map</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsLatticeEndomorphism</code>( <var class="Arg">L</var>, <var class="Arg">map</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.

Each of the function described in this section (except <code class="code">IsLatticeEndomorphism</code>) takes a pair of digraphs <var class="Arg">L1</var> and <var class="Arg">L2</var>, and a transformation <var class="Arg">map</var>, returning <code class="keyw">true</code> if <var class="Arg">map</var> is a lattice homomorphism from <var class="Arg">L1</var> to <var class="Arg">L2</var>, and <code class="keyw">false</code> otherwise. If <var class="Arg">L1</var> or <var class="Arg">L2</var> is not a lattice, then <code class="keyw">false</code> is returned.

A transformation or permutation <var class="Arg">map</var> is a lattice homomorphism if <var class="Arg">map</var> respects meets and joins of every pair of vertices, and <var class="Arg">map</var> fixes every <code class="code">i</code> which is not a vertex of <var class="Arg">L1</var>.

<code class="code">IsLatticeHomomorphism</code> returns <code class="keyw">true</code> if the permutation or transformation <var class="Arg">map</var> is a lattice homomorphism from the lattice digraph <var class="Arg">L1</var> to the lattice digraph <var class="Arg">L2</var>.

<code class="code">IsLatticeEpimorphism</code> returns <code class="keyw">true</code> if the permutation or transformation <var class="Arg">map</var> is a surjective lattice homomorphism from the lattice digraph <var class="Arg">L1</var> to the lattice digraph <var class="Arg">L2</var>.

<code class="code">IsLatticeEmbedding</code> returns <code class="keyw">true</code> if the permutation or transformation <var class="Arg">map</var> is an injective lattice homomorphism from the lattice digraph <var class="Arg">L1</var> to the lattice digraph <var class="Arg">L2</var>. The function <code class="code">IsLatticeMonomorphism</code> is a synonym of <code class="code">IsLatticeEmbedding</code>.

<code class="code">IsLatticeEndomorphism</code> returns <code class="keyw">true</code> if the permutation or transformation <var class="Arg">map</var> is an lattice endomorphism of the lattice digraph <var class="Arg">L</var>.

<div class="example"><pre>
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
</pre></div>

<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap6.html">[Previous Chapter]</a> <a href="chap8.html">[Next Chapter]</a> </div>

<div class="chlinkbot">Goto Chapter: <a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chapA.html">A</a> <a href="chapB.html">B</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>

<hr />
generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a>
</body>
</html>

Messung V0.5 in Prozent

¤ Dauer der Verarbeitung: 0.97 Sekunden (vorverarbeitet am 2026-04-29) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.