SSL inspect.tex Sprache: Latech

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%A  inspect.tex               GRAPE documentation              Leonard Soicher
%
%
%
\def\GRAPE{\sf GRAPE}
\def\nauty{\it nauty}
\def\G{\Gamma}
\def\Aut{{\rm Aut}\,}
\def\x{\times}
\Chapter{Functions to inspect graphs, vertices and edges}

This chapter describes functions to inspect graphs, vertices and edges.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsGraph}

\>IsGraph( <obj> )

This boolean function  returns `true' if and only if , which can be
an object of arbitrary type, is a graph.

\beginexample
gap> IsGraph( 1 );
false
gap> IsGraph( JohnsonGraph( 3, 2 ) );
true
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{OrderGraph}

\>OrderGraph( <gamma> )

This function returns the number of vertices (the *order*) of the graph
<gamma>.

\beginexample
gap> OrderGraph( JohnsonGraph( 4, 2 ) );
6
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsVertex}

\>IsVertex( <gamma>, <v> )

This  boolean  function returns `true' if and only if is vertex of
the graph <gamma>.

\beginexample
gap> gamma := JohnsonGraph( 3, 2 );;
gap> IsVertex( gamma, 1 );
true
gap> IsVertex( gamma, 4 );
false
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{VertexName}

\>VertexName( <gamma>, <v> )

This function returns (an immutable copy of) the name of vertex <v> in
the graph <gamma>.

See also "VertexNames" and "AssignVertexNames".

\beginexample
gap> VertexName( JohnsonGraph(4,2), 6 );
[ 3, 4 ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{VertexNames}

\>VertexNames( <gamma> )

This function returns (an immutable copy of) the list of vertex-names
for the graph <gamma>.  The <i>-th element of this list is the name of
vertex <i>.

See also "VertexName" and "AssignVertexNames".

\beginexample
gap> VertexNames( JohnsonGraph(4,2) );
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Vertices}

\>Vertices( <gamma> )

This function returns the vertex-set $\{1,\ldots, `<gamma>\.order'\}$
of the graph <gamma>.

\beginexample
gap> Vertices( JohnsonGraph( 4, 2 ) );
[ 1 .. 6 ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{VertexDegree}

\>VertexDegree( <gamma>, <v> )

This  function  returns the  (out)degree  of the vertex <v> of  the graph
<gamma>.

\beginexample
gap> VertexDegree( JohnsonGraph( 3, 2 ), 1 );
2
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{VertexDegrees}

\>VertexDegrees( <gamma> )

This function returns the set of vertex (out)degrees for the graph
<gamma>.

\beginexample
gap> VertexDegrees( JohnsonGraph( 4, 2 ) );
[ 4 ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsLoopy}

\>IsLoopy( <gamma> )

This boolean function returns `true' if and only if the graph has
a *loop*, i.e. an edge of the form $[x,x]$.

\beginexample
gap> IsLoopy( JohnsonGraph( 4, 2 ) );
false
gap> IsLoopy( CompleteGraph( Group( (1,2,3), (1,2) ), 3 ) );
false
gap> IsLoopy( CompleteGraph( Group( (1,2,3), (1,2) ), 3, true ) );
true
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsSimpleGraph}

\>IsSimpleGraph( <gamma> )

This boolean function returns `true' if and only if the graph
is *simple*, i.e. has no loops and whenever $[x,y]$ is an edge then so
is $[y,x]$.

\beginexample
gap> IsSimpleGraph( CompleteGraph( Group( (1,2,3) ), 3 ) );
true
gap> IsSimpleGraph( CompleteGraph( Group( (1,2,3) ), 3, true ) );
false
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Adjacency}

\>Adjacency( <gamma>, <v> )

This function returns (a copy of) the set of vertices of the graph
<gamma> adjacent to the vertex <v> of <gamma>.  A vertex $w$ is
*adjacent* to <v> if and only if $[v,w]$ is an edge.

\beginexample
gap> Adjacency( JohnsonGraph( 4, 2 ), 1 );
[ 2, 3, 4, 5 ]
gap> Adjacency( JohnsonGraph( 4, 2 ), 6 );
[ 2, 3, 4, 5 ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsEdge}

\>IsEdge( <gamma>, <e> )

This  boolean function returns `true' if and only if is an edge of
the graph <gamma>.

\beginexample
gap> IsEdge( JohnsonGraph( 4, 2 ), [ 1, 2 ] );
true
gap> IsEdge( JohnsonGraph( 4, 2 ), [ 1, 6 ] );
false
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{DirectedEdges}

\>DirectedEdges( <gamma> )

This function  returns the  set of directed  (ordered) edges of the graph
<gamma>.

See also "UndirectedEdges".

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{UndirectedEdges}

\>UndirectedEdges( <gamma> )

This function returns the set of undirected (unordered) edges of <gamma>,
which must be a simple graph.

See also "DirectedEdges".

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Distance}

\>Distance( <gamma>, <X>, <Y> )
\>Distance( <gamma>, <X>, <Y>, <G> )

This function returns the distance from <X> to <Y> in <gamma>. The
parameters <X> and <Y> may be vertices or nonempty lists of vertices.
We define the *distance* $d(<X>,<Y>)$ from <X> to <Y> to be the minimum
length of a (directed) path joining a vertex of <X> to a vertex of <Y>
if such a path exists, and $-1$ otherwise.

The  optional parameter <G>,  if present, is assumed to  be a subgroup of
$\Aut(<gamma>)$ fixing  <X>  setwise.  Including  such a <G> can speed up
the function.

See also "Diameter".

\beginexample
gap> Distance( JohnsonGraph(4,2), 1, 6 );
2
gap> Distance( JohnsonGraph(4,2), 1, 5 );
1
gap> Distance( JohnsonGraph(4,2), [1], [5,6] );
1
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Diameter}

\>Diameter( <gamma> )

This  function  returns the  diameter of <gamma>.  A diameter of $-1$
is returned if <gamma> is not (strongly) connected.  Otherwise, the
*diameter* of <gamma> is equal to the maximum (directed) distance
$d(x,y)$ in <gamma> (as $x$ and $y$ range over all the vertices of
<gamma>).

See also "Distance".

\beginexample
gap> Diameter( JohnsonGraph( 5, 3 ) );
2
gap> Diameter( JohnsonGraph( 5, 4 ) );
1
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Girth}

\>Girth( <gamma> )

This function returns the girth of <gamma>, which must be a simple graph.
A girth of $-1$ is returned if <gamma> is a forest.  Otherwise the *girth*
is the length of a shortest cycle in <gamma>.

\beginexample
gap> Girth( JohnsonGraph( 4, 2 ) );
3
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsConnectedGraph}

\>IsConnectedGraph( <gamma> )

This boolean function returns `true' if and only if the graph
is (strongly) *connected*, i.e. there is a (directed) path from $x$ to
$y$ for every pair of vertices $x,y$ of <gamma>.

\beginexample
gap> IsConnectedGraph( JohnsonGraph(4,2) );
true
gap> IsConnectedGraph( NullGraph(SymmetricGroup(4)) );
false
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsBipartite}

\>IsBipartite( <gamma> )

This boolean function returns `true' if and only if the graph ,
which must be simple, is *bipartite*, i.e. if the vertex-set can be
expressed as the disjoint union of two sets, on each of which <gamma>
induces a null graph (these two sets are called the *bicomponents* or
*parts* of <gamma>).

See also "Bicomponents" and "BipartiteDouble".

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsNullGraph}

\>IsNullGraph( <gamma> )

This boolean function returns `true' if and only if the graph has
no edges.

See also "NullGraph".

\beginexample
gap> IsNullGraph( CompleteGraph( Group(()), 3 ) );
false
gap> IsNullGraph( CompleteGraph( Group(()), 1 ) );
true
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsCompleteGraph}

\>IsCompleteGraph( <gamma> )
\>IsCompleteGraph( <gamma>, <mustloops> )

This boolean function returns  `true' if and only if the graph is
a complete graph.  The optional boolean  parameter <mustloops> determines
whether all loops must be present for <gamma> to be considered a complete
graph (default: `false' (loops are ignored)).

See also "CompleteGraph".

\beginexample
gap> IsCompleteGraph( NullGraph( Group(()), 3 ) );
false
gap> IsCompleteGraph( NullGraph( Group(()), 1 ) );
true
gap> IsCompleteGraph( CompleteGraph(SymmetricGroup(3)), true );
false
\endexample

quality93%

¤ Dauer der Verarbeitung: 0.22 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.