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