Quelle consmod.tex Sprache: Latech

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%A  consmod.tex            GRAPE documentation              Leonard Soicher
%
%
%
\Chapter{Functions to construct and modify graphs}

This chapter describes the functions used to construct and modify graphs.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Graph}

\>Graph( <G>, <L>, <act>, <rel> )
\>Graph( <G>, <L>, <act>, <rel>, <invt> )

This  is the most  general  and  useful  way  of constructing a graph
in {\GRAPE}.

First suppose that the optional boolean parameter <invt> is unbound or
has value `false'. Then should be a list of elements of a set $S$ on
which the group <G> acts, with the action given by the function <act>. The
parameter <rel> should be a boolean function defining a <G>-invariant
relation on $S$ (so that for $g$ in <G>, $x,y$ in $S$, $<rel>(x,y)$
if and only if $<rel>(<act>(x,g),<act>(y,g))$). Then the function `Graph'
returns a graph <gamma> which has as vertex-names (an immutable copy of)
\begintt
  Concatenation( Orbits( <G>, <L>, <act> ) )
\endtt
(the concatenation of the distinct orbits of the elements in <L> under
<G>), and for vertices $v,w$ of <gamma>, $[v,w]$ is an edge if and only if
\begintt
  <rel>( VertexName( <gamma>, <v> ), VertexName( <gamma>, <w> ) ).
\endtt
(Note that you may choose to have <G> act trivially on $S$, in
which case <G> could be given as the trivial permutation group,
`Group( () )', and could be given as the trivial action,
`function(x,g) return x; end'.)

Now if the  parameter <invt> exists  and  has value `true', then it is
assumed  that <L> is invariant  under <G> with respect  to  action <act>.
Then the function `Graph' behaves as above, except that the vertex-names
of <gamma> become (an immutable copy of) <L>.

The group associated with the graph <gamma> returned is  the image of <G>
acting via <act> on `<gamma>.names'.

For example, we may use `Graph' to construct the Petersen graph as follows:

\beginexample
gap> Petersen := Graph( SymmetricGroup(5), [[1,2]], OnSets,
>                    function(x,y) return Intersection(x,y)=[]; end );
rec(
  isGraph := true,
  order := 10,
  group := Group( [ ( 1, 2, 3, 5, 7)( 4, 6, 8, 9,10), ( 2, 4)( 6, 9)( 7,10)
     ] ),
  schreierVector := [ -1, 1, 1, 2, 1, 1, 1, 1, 2, 2 ],
  adjacencies := [ [ 3, 5, 8 ] ],
  representatives := [ 1 ],
  names := [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 1, 3 ], [ 4, 5 ], [ 2, 4 ],
      [ 1, 5 ], [ 3, 5 ], [ 1, 4 ], [ 2, 5 ] ] )
\endexample

The function `Graph' may be used to construct a graph in {\GRAPE} format
from an adjacency matrix
\index{adjacency matrix}
for that graph. For
example, suppose you have an $n$ by $n$ adjacency matrix $A$ for a graph
$gamma$, so that the vertex-set of $gamma$ is $\{1,\ldots,n\}$, and
$[i,j]$ is an edge of $gamma$ if and only if $A[i][j]=1$.  Then the graph
$gamma$ in {\GRAPE}-graph format, with associated group the trivial group,
is returned by `Graph( Group(()), [1..n], OnPoints, function(x,y) return
A[x][y]=1; end, true );'

\beginexample
gap> A := [[0,1,0],[1,0,0],[0,0,1]];
[ [ 0, 1, 0 ], [ 1, 0, 0 ], [ 0, 0, 1 ] ]
gap> gamma := Graph( Group(()), [1..3], OnPoints,
>        function(x,y) return A[x][y]=1; end,
>        true );
rec( adjacencies := [ [ 2 ], [ 1 ], [ 3 ] ], group := Group(()),
  isGraph := true, names := [ 1, 2, 3 ], order := 3,
  representatives := [ 1, 2, 3 ], schreierVector := [ -1, -2, -3 ] )
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{EdgeOrbitsGraph}

\>EdgeOrbitsGraph( <G>, <edges> )
\>EdgeOrbitsGraph( <G>, <edges>, <n> )

This is a common way of constructing a graph in {\GRAPE}.

This function returns the (directed) graph with vertex-set $\{1,\ldots,
<n>\}$, edge-set $\cup_{e\in <edges>} e^{<G>}$, and associated
(permutation) group <G>, which must act naturally on $\{1,\ldots,<n>\}$.
The parameter <edges> should be a list of edges (lists of length 2 of
vertices), although a singleton edge will be understood as an edge-list
of length 1. The parameter <n> may be omitted, in which case <n> is
taken to be the largest point moved by <G>.

Note that <G> may be the trivial permutation group (`Group( () )' in
{\GAP} notation), in which case the (directed) edges of <gamma> are
simply those in the list <edges>.

\beginexample
gap> EdgeOrbitsGraph( Group((1,3),(1,2)(3,4)), [[1,2],[4,5]], 5 );
rec(
  isGraph := true,
  order := 5,
  group := Group( [ (1,3), (1,2)(3,4) ] ),
  schreierVector := [ -1, 2, 1, 2, -2 ],
  adjacencies := [ [ 2, 4, 5 ], [  ] ],
  representatives := [ 1, 5 ],
  isSimple := false )
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{NullGraph}

\>NullGraph( <G> )
\>NullGraph( <G>, <n> )

This function returns the null graph (graph with no edges) with vertex-set
$\{1,\ldots,<n>\}$, and associated (permutation) group <G>. The parameter
<n> may be omitted, in which case <n> is taken to be the largest point
moved by <G>.

See also "IsNullGraph".

\beginexample
gap> NullGraph( Group( (1,2,3) ), 4 );
rec(
  isGraph := true,
  order := 4,
  group := Group( [ (1,2,3) ] ),
  schreierVector := [ -1, 1, 1, -2 ],
  adjacencies := [ [  ], [  ] ],
  representatives := [ 1, 4 ],
  isSimple := true )
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CompleteGraph}

\>CompleteGraph( <G> )
\>CompleteGraph( <G>, <n> )
\>CompleteGraph( <G>, <n>, <mustloops> )

This function returns the complete graph with vertex-set
$\{1,\ldots,<n>\}$ and associated (permutation) group <G>. The parameter
<n> may be  omitted, in which case <n> is taken to be the largest point
moved by <G>.  The optional boolean parameter <mustloops> determines
whether the complete graph has all loops present or no loops (default:
`false' (no loops)).

See also "IsCompleteGraph".

\beginexample
gap> CompleteGraph( Group( (1,2,3), (1,2) ) );
rec(
  isGraph := true,
  order := 3,
  group := Group( [ (1,2,3), (1,2) ] ),
  schreierVector := [ -1, 1, 1 ],
  adjacencies := [ [ 2, 3 ] ],
  representatives := [ 1 ],
  isSimple := true )
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{JohnsonGraph}

\>JohnsonGraph( <n>, <e> )

Let <n> and <e> be integers, with $<n>\ge <e>\ge 0$.  Then this function
returns a graph <gamma> isomorphic to the Johnson graph $J(<n>,<e>)$.
The vertices (actually the vertex-names) of <gamma> are the <e>-subsets
of $\{1,\ldots, <n>\}$, with $x$ joined to $y$ if and only if $|x \cap y|
= <e>-1$.  The group associated with <gamma> is the image of the symmetric
group $S_{<n>}$ acting on the <e>-subsets of $\{1,\ldots,<n>\}$.

\beginexample
gap> JohnsonGraph(5,3);
rec(
  isGraph := true,
  order := 10,
  group := Group( [ ( 1, 7,10, 6, 3)( 2, 8, 4, 9, 5), ( 4, 7)( 5, 8)( 6, 9)
     ] ),
  schreierVector := [ -1, 1, 1, 2, 1, 1, 1, 2, 1, 1 ],
  adjacencies := [ [ 2, 3, 4, 5, 7, 8 ] ],
  representatives := [ 1 ],
  names := [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 2, 5 ], [ 1, 3, 4 ], [ 1, 3, 5 ],
      [ 1, 4, 5 ], [ 2, 3, 4 ], [ 2, 3, 5 ], [ 2, 4, 5 ], [ 3, 4, 5 ] ],
  isSimple := true )
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{HammingGraph}

\>HammingGraph( <d>, <q> )

Let <d> and <q> be positive integers.  Then this function returns a
graph <gamma> isomorphic to the Hamming graph $H(<d>,<q>)$.  The vertices
(actually the vertex-names) of <gamma> are the <d>-vectors with entries
in $\{1,\ldots,<q>\}$, with $x$ joined to $y$ if and only if $x$ and $y$
differ in exactly one coordinate (that is, $x$ and $y$ are at Hamming
distance~1).  The group associated with <gamma> is the image of the wreath
product of the symmetric group $S_{<q>}$ with the symmetric group
$S_{<d>}$, in its product action on the vertices.

\beginexample
gap> H:=HammingGraph(3,4);
rec( adjacencies := [ [ 2, 3, 4, 5, 9, 13, 17, 33, 49 ] ],
  group := <permutation group with 8 generators>, isGraph := true,
  names := [ [ 1, 1, 1 ], [ 1, 1, 2 ], [ 1, 1, 3 ], [ 1, 1, 4 ],
      [ 1, 2, 1 ], [ 1, 2, 2 ], [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 1 ],
      [ 1, 3, 2 ], [ 1, 3, 3 ], [ 1, 3, 4 ], [ 1, 4, 1 ], [ 1, 4, 2 ],
      [ 1, 4, 3 ], [ 1, 4, 4 ], [ 2, 1, 1 ], [ 2, 1, 2 ], [ 2, 1, 3 ],
      [ 2, 1, 4 ], [ 2, 2, 1 ], [ 2, 2, 2 ], [ 2, 2, 3 ], [ 2, 2, 4 ],
      [ 2, 3, 1 ], [ 2, 3, 2 ], [ 2, 3, 3 ], [ 2, 3, 4 ], [ 2, 4, 1 ],
      [ 2, 4, 2 ], [ 2, 4, 3 ], [ 2, 4, 4 ], [ 3, 1, 1 ], [ 3, 1, 2 ],
      [ 3, 1, 3 ], [ 3, 1, 4 ], [ 3, 2, 1 ], [ 3, 2, 2 ], [ 3, 2, 3 ],
      [ 3, 2, 4 ], [ 3, 3, 1 ], [ 3, 3, 2 ], [ 3, 3, 3 ], [ 3, 3, 4 ],
      [ 3, 4, 1 ], [ 3, 4, 2 ], [ 3, 4, 3 ], [ 3, 4, 4 ], [ 4, 1, 1 ],
      [ 4, 1, 2 ], [ 4, 1, 3 ], [ 4, 1, 4 ], [ 4, 2, 1 ], [ 4, 2, 2 ],
      [ 4, 2, 3 ], [ 4, 2, 4 ], [ 4, 3, 1 ], [ 4, 3, 2 ], [ 4, 3, 3 ],
      [ 4, 3, 4 ], [ 4, 4, 1 ], [ 4, 4, 2 ], [ 4, 4, 3 ], [ 4, 4, 4 ] ],
  order := 64, representatives := [ 1 ],
  schreierVector := [ -1, 5, 5, 5, 3, 5, 5, 5, 3, 5, 5, 5, 3, 5, 5, 5, 1, 5,
      5, 5, 3, 5, 5, 5, 3, 5, 5, 5, 3, 5, 5, 5, 1, 5, 5, 5, 3, 5, 5, 5, 3,
      5, 5, 5, 3, 5, 5, 5, 1, 5, 5, 5, 3, 5, 5, 5, 3, 5, 5, 5, 3, 5, 5, 5 ] )
gap> GlobalParameters(H);
[ [ 0, 0, 9 ], [ 1, 2, 6 ], [ 2, 4, 3 ], [ 3, 6, 0 ] ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CayleyGraph}

\>CayleyGraph( <G> )
\>CayleyGraph( <G>, <gens> )
\>CayleyGraph( <G>, <gens>, <undirected> )

Given a group <G> and a generating list <gens> for  <G>, `CayleyGraph(
<G>, <gens> )' returns a Cayley graph for with respect to .
The generating list <gens> is optional, and if omitted, then <gens> is
taken to be `GeneratorsOfGroup( <G> )'. The boolean argument
is also optional, and if <undirected>=`true' (the default), then the
returned graph is undirected (as if <gens> was closed under inversion,
whether or not it is).

The Cayley graph  <caygraph>  which is returned is defined as follows:
the vertices (actually the vertex-names) of <caygraph>  are the elements
of <G>;  if <undirected>=`true' (the default) then vertices $x,y$ are
joined by an edge if and only if there is a $g$ in the list <gens> with
$y=gx$ or $y=g^{-1}x$; if <undirected>=`false' then $[x,y]$ is an edge
if and only if there is a $g$ in <gens> with $y=gx$.

The permutation group `<caygraph>.group' associated with is
the image of <G> acting in its right regular representation.

*Note* It is not checked whether <G> is actually generated by <gens>.
However, even if <G> is not generated by <gens>, the function still
works as described above (as long as <gens> is contained in <G>), but
returns a ``Cayley graph'' which is not connected.

\beginexample
gap> C:=CayleyGraph(SymmetricGroup(4),[(1,2),(2,3),(3,4)]);
rec(
  isGraph := true,
  order := 24,
  group :=
   Group( [ ( 1,10,17,19)( 2, 9,18,20)( 3,12,14,21)( 4,11,13,22)( 5, 7,16,23)
        ( 6, 8,15,24), ( 1, 7)( 2, 8)( 3, 9)( 4,10)( 5,11)( 6,12)(13,15)
        (14,16)(17,18)(19,21)(20,22)(23,24) ] ),
  schreierVector := [ -1, 1, 1, 2, 2, 1, 2, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2,
      1, 1, 2, 2, 1, 2 ],
  adjacencies := [ [ 2, 3, 7 ] ],
  representatives := [ 1 ],
  names := [ (), (3,4), (2,3), (2,3,4), (2,4,3), (2,4), (1,2), (1,2)(3,4),
      (1,2,3), (1,2,3,4), (1,2,4,3), (1,2,4), (1,3,2), (1,3,4,2), (1,3),
      (1,3,4), (1,3)(2,4), (1,3,2,4), (1,4,3,2), (1,4,2), (1,4,3), (1,4),
      (1,4,2,3), (1,4)(2,3) ],
  isSimple := true )
gap> Girth(C);
4
gap> Diameter(C);
6
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{GeneralizedOrbitalGraphs}

\>GeneralizedOrbitalGraphs( <G> )
\>GeneralizedOrbitalGraphs( <G>, <k> )

Suppose <G> is a non-trivial transitive permutation group
on $\{1,\ldots,n\}$, where $n$ is the largest point moved by <G>.
Then this function returns a list of distinct generalized
orbital graphs for <G>, where a  *generalized orbital graph*
\index{generalized orbital graph}
for <G>  is a (simple) graph with vertex set $\{1,\ldots,n\}$ and
undirected-edge set a union of zero or more <G>-orbits of 2-subsets
of $\{1,\ldots,n\}$.

The optional second parameter <k> (default: `false') must be `false',
`true', or a non-negative integer. If =`true' then all the generalized
orbital graphs for <G> are in the returned list, if <k>=`false' (the
default) then only the non-null generalized orbital graphs for <G> are in
this list, and if <k> is a non-negative integer then the list consists
of all the generalized orbital graphs for <G> whose undirected-edge set
is the union of exactly <k> <G>-orbits of 2-subsets of $\{1,\ldots,n\}$.

The group associated with each graph in the returned list is <G>.

\beginexample
gap> G:=JohnsonGraph(7,3).group;;
gap> L:=GeneralizedOrbitalGraphs(G);;
gap> List(L,VertexDegrees);
[ [ 12 ], [ 30 ], [ 34 ], [ 16 ], [ 18 ], [ 22 ], [ 4 ] ]
gap> List(L,Diameter);
[ 3, 2, 1, 2, 2, 2, 3 ]
gap> C:=CyclicGroup(IsPermGroup,6);
Group([ (1,2,3,4,5,6) ])
gap> GeneralizedOrbitalGraphs(C,1);
[ rec( adjacencies := [ [ 2, 6 ] ], group := Group([ (1,2,3,4,5,6) ]),
      isGraph := true, order := 6, representatives := [ 1 ],
      schreierVector := [ -1, 1, 1, 1, 1, 1 ] ),
  rec( adjacencies := [ [ 3, 5 ] ], group := Group([ (1,2,3,4,5,6) ]),
      isGraph := true, order := 6, representatives := [ 1 ],
      schreierVector := [ -1, 1, 1, 1, 1, 1 ] ),
  rec( adjacencies := [ [ 4 ] ], group := Group([ (1,2,3,4,5,6) ]),
      isGraph := true, isSimple := true, order := 6, representatives := [ 1 ],
      schreierVector := [ -1, 1, 1, 1, 1, 1 ] ) ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{AddEdgeOrbit}

\>AddEdgeOrbit( <gamma>, <e> )
\>AddEdgeOrbit( <gamma>, <e>, <H> )

This procedure adds the orbit of <e> under `<gamma>.group' to the
edge-set of the graph <gamma>. The parameter <e> must be a sequence of
length 2 of vertices of <gamma>. If the optional third parameter <H> is
given then it is assumed that `<e>[2]' has the same orbit under as
it does under the stabilizer in `<gamma>.group' of `[1]', and this
knowledge can speed up the procedure.

Note that if `<gamma>.group' is trivial then this procedure simply adds the
single (directed) edge <e> to <gamma>.

See also "RemoveEdgeOrbit".

\beginexample
gap> gamma := NullGraph( Group( (1,3), (1,2)(3,4) ) );;
gap> AddEdgeOrbit( gamma, [4,3] );
gap> gamma;
rec(
  isGraph := true,
  order := 4,
  group := Group( [ (1,3), (1,2)(3,4) ] ),
  schreierVector := [ -1, 2, 1, 2 ],
  adjacencies := [ [ 2, 4 ] ],
  representatives := [ 1 ],
  isSimple := true )
gap> GlobalParameters(gamma);
[ [ 0, 0, 2 ], [ 1, 0, 1 ], [ 2, 0, 0 ] ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{RemoveEdgeOrbit}

\>RemoveEdgeOrbit( <gamma>, <e> )
\>RemoveEdgeOrbit( <gamma>, <e>, <H> )

This procedure removes the orbit of <e> under `<gamma>.group' from the
edge-set of the graph <gamma>. The parameter <e> must be a sequence of
length 2 of vertices of <gamma>, but if <e> is not an edge of <gamma>
then this procedure has no effect. If the optional third parameter <H>
is given then it is assumed that `<e>[2]' has the same orbit under
as it does under the stabilizer in `<gamma>.group' of `[1]', and
this knowledge can speed up the procedure.

See also "AddEdgeOrbit".

\beginexample
gap> gamma := CompleteGraph( Group( (1,3), (1,2)(3,4) ) );;
gap> RemoveEdgeOrbit( gamma, [1,3] );
gap> gamma;
rec(
  isGraph := true,
  order := 4,
  group := Group( [ (1,3), (1,2)(3,4) ] ),
  schreierVector := [ -1, 2, 1, 2 ],
  adjacencies := [ [ 2, 4 ] ],
  representatives := [ 1 ],
  isSimple := true )
gap> GlobalParameters(gamma);
[ [ 0, 0, 2 ], [ 1, 0, 1 ], [ 2, 0, 0 ] ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{AssignVertexNames}

\>AssignVertexNames( <gamma>, <names> )

This procedure allows the user to give new names for the vertices of
<gamma>, by specifying a list <names> (of length `<gamma>.order') of
vertex-names for the vertices of <gamma>, such that `<names>[<i>]'
contains the user{\pif}s name for the <i>-th vertex of <gamma>.

An immutable copy of <names> is assigned to `<gamma>.names'.

See also "VertexNames" and "VertexName".

\beginexample
gap> gamma := NullGraph( Group(()), 3 );
rec(
  isGraph := true,
  order := 3,
  group := Group( [ () ] ),
  schreierVector := [ -1, -2, -3 ],
  adjacencies := [ [  ], [  ], [  ] ],
  representatives := [ 1, 2, 3 ],
  isSimple := true )
gap> AssignVertexNames( gamma, ["a","b","c"] );
gap> gamma;
rec(
  isGraph := true,
  order := 3,
  group := Group( [ () ] ),
  schreierVector := [ -1, -2, -3 ],
  adjacencies := [ [  ], [  ], [  ] ],
  representatives := [ 1, 2, 3 ],
  isSimple := true,
  names := [ "a", "b", "c" ] )
\endexample

quality82%

¤ Dauer der Verarbeitung: 0.34 Sekunden (vorverarbeitet) ¤

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.