Quellcode-Bibliothek 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>
--> --------------------

--> maximum size reached

--> --------------------

quality99%

¤ 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.0.88Bemerkung: (vorverarbeitet) ¤

*Bot Zugriff

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 ist noch experimentell.