| Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/grape/htm/ (Algebra von RWTH Aachen Version 4.15.1©) Datei vom 6.8.2025 mit Größe 3 kB |
|
Quelle CHAP010.htm Sprache: HTML |
|||||||||||
<html><head><title>[grape] 10 Auxiliary Functions</title></head>
<body text="#000000" bgcolor="#ffffff"> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP009.htm">Previous</a>] [<a href = "theindex.htm">In <h1>10 Auxiliary Functions</h1><p> <P> <H3>Sections</H3> <oL> <li> <A HREF="CHAP010.htm#SECT001">Steve Linton's Function SmallestImageSet <li> <A HREF="CHAP010.htm#SECT002">Exact Set-cover</a> </ol><p> <p> This chapter documents some auxiliary functions used in GRAPE, which may be of wider interest. <p> <p> <h2><a name="SECT001">10.1 Steve Linton's Function SmallestImageSet <p><p> <a name = "SSEC001.1"></a> <li><code>SmallestImageSet( </code><var>G</var><code>, </code><var>S</var><code> )</code> <li><code>SmallestImageSet( </code><var>G</var><code>, </code><var>S</var><code>, </code><var>H</var><code> )</co <p> Let <var>G</var> be a permutation group on <var>{1,...,n}</var>, and let <var>S</var> be a subset of <var>{1,...,n}</var>. Then this function returns the lexicographically least set in the <var>G</var>-orbit of <var>S</var>, with respect to the action <code>OnSets</code>, without explicitly computing this (possibly huge) orbit. <p> Thus, if <var>C</var> is a list of subsets of <var>{1,...,n}</var> and we want to determine a set of (canonical) representatives for the distinct <var>G</var>-orbits of the elements of <var>C</var>, we can do this as <code>Set(</code><var>C</var><code>,c->SmallestImageSet(</code><var>G</var><code>,c))</code>. <p> If the setwise stabilizer in <var>G</var> of <var>S</var> is known, then this should be given as the optional third parameter, to avoid the recomputation of this stabilizer. <p> The function <code>SmallestImageSet</code> was written by Steve Linton, based on his algorithm described in <a href="biblio.htm#Lin04"><cite>Lin04</cite></a>. <p> <pre> gap> J:=JohnsonGraph(12,5);; gap> OrderGraph(J); 792 gap> G:=J.group;; gap> Size(G); 479001600 gap> S:=[67,93,100,204,677,750];; gap> SmallestImageSet(G,S); [ 1, 2, 22, 212, 242, 446 ] </pre> <p> <p> <h2><a name="SECT002">10.2 Exact Set-cover</a></h2> <p><p> <a name = "SSEC002.1"></a> <li><code>GRAPE_ExactSetCover( </code><var>G</var><code>, </code><var>blocks</var><code>, </code><var>n</var>< <li><code>GRAPE_ExactSetCover( </code><var>G</var><code>, </code><var>blocks</var><code>, </code><var>n</var>< <p> Suppose <var>n</var> is a non-negative integer, <var>G</var> is a permutation group on <var>{1,...,n}</var>, <var>blocks</var> is a list of non-empty subsets of <var>{1,...,n}</var>, and the optional parameter <var>H</var> (default: <code>Group(())</code>) is a subgroup of <var>G</var>. <p> Then this function returns an <var>H</var>-invariant exact set-cover of <var>{1,...,n}</var>, consisting of elements from the union of <code>Orbits(</code><var>G</var><code>,</code><var>blocks</var><code>,OnSets)</code>, if such a cover exi and returns <code>fail</code> otherwise. An exact set-cover is given as a set of sets forming a partition of <var>{1,...,n}</var>. <p> <pre> gap> G:=PSL(2,5);; gap> GRAPE_ExactSetCover(G,[[1,2,3]],6); fail gap> G:=PGL(2,5);; gap> GRAPE_ExactSetCover(G,[[1,2,3]],6); [ [ 1, 2, 3 ], [ 4, 5, 6 ] ] gap> n:=280;; gap> G:=OnePrimitiveGroup(NrMovedPoints,n,Size,604800*2); J_2.2 gap> gamma:=First(GeneralizedOrbitalGraphs(G),x->VertexDegrees(x)=[135]);; gap> omega:=CliqueNumber(gamma); 28 gap> blocks:=CompleteSubgraphsOfGivenSize(ComplementGraph(gamma),n/omega,2);; gap> Collected(List(blocks,Length)); [ [ 10, 2 ] ] gap> H:=SylowSubgroup(G,7);; gap> partition:=GRAPE_ExactSetCover(G,blocks,n,H);; gap> Collected(List(partition,Length)); [ [ 10, 28 ] ] gap> Union(partition)=[1..n]; true </pre> <p> <p> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP009.htm">Previous</a>] [<a href = "theindex.htm">In <P> <address>grape manual<br>September 2025 </address></body></html> ¤ Dauer der Verarbeitung: 0.1 Sekunden (vorverarbeitet) ¤*© Formatika GbR, Deutschland |
|
2026-03-28