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:
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 );'
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>.
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>.
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)).
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>\}$.
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.
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.
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>.
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>.
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.
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'.
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.
