Gedichte Musik Bilder Quellcodebibliothek Diashow Normaldarstellung
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 14 kB image not shown  

Quelle  CHAP003.htm   Sprache: HTML

 
 products/Sources/formale Sprachen/GAP/pkg/grape/htm/CHAP003.htm


<html><head><title>[grape] 3 Functions to inspect graphs, vertices and edges</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP002.htm">Previous</a>] [<a href ="CHAP004.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<h1>3 Functions to inspect graphs, vertices and edges</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP003.htm#SECT001">IsGraph</a>
<li> <A HREF="CHAP003.htm#SECT002">OrderGraph</a>
<li> <A HREF="CHAP003.htm#SECT003">IsVertex</a>
<li> <A HREF="CHAP003.htm#SECT004">VertexName</a>
<li> <A HREF="CHAP003.htm#SECT005">VertexNames</a>
<li> <A HREF="CHAP003.htm#SECT006">Vertices</a>
<li> <A HREF="CHAP003.htm#SECT007">VertexDegree</a>
<li> <A HREF="CHAP003.htm#SECT008">VertexDegrees</a>
<li> <A HREF="CHAP003.htm#SECT009">IsLoopy</a>
<li> <A HREF="CHAP003.htm#SECT010">IsSimpleGraph</a>
<li> <A HREF="CHAP003.htm#SECT011">Adjacency</a>
<li> <A HREF="CHAP003.htm#SECT012">IsEdge</a>
<li> <A HREF="CHAP003.htm#SECT013">DirectedEdges</a>
<li> <A HREF="CHAP003.htm#SECT014">UndirectedEdges</a>
<li> <A HREF="CHAP003.htm#SECT015">Distance</a>
<li> <A HREF="CHAP003.htm#SECT016">Diameter</a>
<li> <A HREF="CHAP003.htm#SECT017">Girth</a>
<li> <A HREF="CHAP003.htm#SECT018">IsConnectedGraph</a>
<li> <A HREF="CHAP003.htm#SECT019">IsBipartite</a>
<li> <A HREF="CHAP003.htm#SECT020">IsNullGraph</a>
<li> <A HREF="CHAP003.htm#SECT021">IsCompleteGraph</a>
</ol><p>
<p>
This chapter describes functions to inspect graphs, vertices and edges.
<p>
<p>
<h2><a name="SECT001">3.1 IsGraph</a></h2>
<p><p>
<a name = "SSEC001.1"></a>
<li><code>IsGraph( </code><var>obj</var><code> )</code>
<p>
This boolean function  returns <code>true</code> if  and only if <var>obj</var>, which can be
an object of arbitrary type, is a graph.
<p>
<pre>
gap> IsGraph( 1 );
false
gap> IsGraph( JohnsonGraph( 3, 2 ) );
true 
</pre>
<p>
<p>
<h2><a name="SECT002">3.2 OrderGraph</a></h2>
<p><p>
<a name = "SSEC002.1"></a>
<li><code>OrderGraph( </code><var>gamma</var><code> )</code>
<p>
This function returns the number of vertices (the <strong>order</strong>) of the graph
<var>gamma</var>.
<p>
<pre>
gap> OrderGraph( JohnsonGraph( 4, 2 ) );
6 
</pre>
<p>
<p>
<h2><a name="SECT003">3.3 IsVertex</a></h2>
<p><p>
<a name = "SSEC003.1"></a>
<li><code>IsVertex( </code><var>gamma</var><code>, </code><var>v</var><code> )</code>
<p>
This  boolean  function returns <code>true</code> if  and  only if  <var>v</var> is vertex of
the graph <var>gamma</var>.
<p>
<pre>
gap> gamma := JohnsonGraph( 3, 2 );;
gap> IsVertex( gamma, 1 );
true
gap> IsVertex( gamma, 4 );
false 
</pre>
<p>
<p>
<h2><a name="SECT004">3.4 VertexName</a></h2>
<p><p>
<a name = "SSEC004.1"></a>
<li><code>VertexName( </code><var>gamma</var><code>, </code><var>v</var><code> )</code>
<p>
This function returns (an immutable copy of) the name of vertex <var>v</var> in
the graph <var>gamma</var>. 
<p>
See also <a href="CHAP003.htm#SSEC005.1">VertexNames</a> and <a href="CHAP002.htm#SSEC011.1">AssignVertexNames</a>.
<p>
<pre>
gap> VertexName( JohnsonGraph(4,2), 6 );
[ 3, 4 ] 
</pre>
<p>
<p>
<h2><a name="SECT005">3.5 VertexNames</a></h2>
<p><p>
<a name = "SSEC005.1"></a>
<li><code>VertexNames( </code><var>gamma</var><code> )</code>
<p>
This function returns (an immutable copy of) the list of vertex-names
for the graph <var>gamma</var>.  The <var>i</var>-th element of this list is the name of
vertex <var>i</var>.
<p>
See also <a href="CHAP003.htm#SSEC004.1">VertexName</a> and <a href="CHAP002.htm#SSEC011.1">AssignVertexNames</a>.
<p>
<pre>
gap> VertexNames( JohnsonGraph(4,2) );
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]                 
</pre>
<p>
<p>
<h2><a name="SECT006">3.6 Vertices</a></h2>
<p><p>
<a name = "SSEC006.1"></a>
<li><code>Vertices( </code><var>gamma</var><code> )</code>
<p>
This function returns the vertex-set <var>{1,..., <code></code><var>gamma</var><code>.order</code>}</var>
of the graph <var>gamma</var>.
<p>
<pre>
gap> Vertices( JohnsonGraph( 4, 2 ) );
[ 1 .. 6 ] 
</pre>
<p>
<p>
<h2><a name="SECT007">3.7 VertexDegree</a></h2>
<p><p>
<a name = "SSEC007.1"></a>
<li><code>VertexDegree( </code><var>gamma</var><code>, </code><var>v</var><code> )</code>
<p>
This  function  returns the  (out)degree  of the vertex <var>v</var> of  the graph
<var>gamma</var>.
<p>
<pre>
gap> VertexDegree( JohnsonGraph( 3, 2 ), 1 );
2 
</pre>
<p>
<p>
<h2><a name="SECT008">3.8 VertexDegrees</a></h2>
<p><p>
<a name = "SSEC008.1"></a>
<li><code>VertexDegrees( </code><var>gamma</var><code> )</code>
<p>
This function returns the set of vertex (out)degrees for the graph
<var>gamma</var>.
<p>
<pre>
gap> VertexDegrees( JohnsonGraph( 4, 2 ) );
[ 4 ] 
</pre>
<p>
<p>
<h2><a name="SECT009">3.9 IsLoopy</a></h2>
<p><p>
<a name = "SSEC009.1"></a>
<li><code>IsLoopy( </code><var>gamma</var><code> )</code>
<p>
This boolean function returns <code>true</code> if and only if the graph <var>gamma</var> has
a <strong>loop</strong>, i.e. an edge of the form <var>[x,x]</var>.
<p>
<pre>
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 
</pre>
<p>
<p>
<h2><a name="SECT010">3.10 IsSimpleGraph</a></h2>
<p><p>
<a name = "SSEC010.1"></a>
<li><code>IsSimpleGraph( </code><var>gamma</var><code> )</code>
<p>
This boolean function returns <code>true</code> if and only if the graph <var>gamma</var>
is <strong>simple</strong>, i.e. has no loops and whenever <var>[x,y]</var> is an edge then so
is <var>[y,x]</var>.
<p>
<pre>
gap> IsSimpleGraph( CompleteGraph( Group( (1,2,3) ), 3 ) );
true
gap> IsSimpleGraph( CompleteGraph( Group( (1,2,3) ), 3, true ) );
false 
</pre>
<p>
<p>
<h2><a name="SECT011">3.11 Adjacency</a></h2>
<p><p>
<a name = "SSEC011.1"></a>
<li><code>Adjacency( </code><var>gamma</var><code>, </code><var>v</var><code> )</code>
<p>
This function returns (a copy of) the set of vertices of the graph
<var>gamma</var> adjacent to the vertex <var>v</var> of <var>gamma</var>.  A vertex <var>w</var> is
<strong>adjacent</strong> to <var>v</var> if and only if <var>[v,w]</var> is an edge.
<p>
<pre>
gap> Adjacency( JohnsonGraph( 4, 2 ), 1 );
[ 2, 3, 4, 5 ]
gap> Adjacency( JohnsonGraph( 4, 2 ), 6 );
[ 2, 3, 4, 5 ] 
</pre>
<p>
<p>
<h2><a name="SECT012">3.12 IsEdge</a></h2>
<p><p>
<a name = "SSEC012.1"></a>
<li><code>IsEdge( </code><var>gamma</var><code>, </code><var>e</var><code> )</code>
<p>
This  boolean function returns <code>true</code> if and  only  if <var>e</var> is an  edge of
the graph <var>gamma</var>.
<p>
<pre>
gap> IsEdge( JohnsonGraph( 4, 2 ), [ 1, 2 ] );
true
gap> IsEdge( JohnsonGraph( 4, 2 ), [ 1, 6 ] );
false 
</pre>
<p>
<p>
<h2><a name="SECT013">3.13 DirectedEdges</a></h2>
<p><p>
<a name = "SSEC013.1"></a>
<li><code>DirectedEdges( </code><var>gamma</var><code> )</code>
<p>
This function  returns the  set of directed  (ordered) edges of the graph
<var>gamma</var>.
<p>
See also <a href="CHAP003.htm#SSEC014.1">UndirectedEdges</a>.
<p>
<pre>
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 ] ]
</pre>
<p>
<p>
<h2><a name="SECT014">3.14 UndirectedEdges</a></h2>
<p><p>
<a name = "SSEC014.1"></a>
<li><code>UndirectedEdges( </code><var>gamma</var><code> )</code>
<p>
This function returns the set of undirected (unordered) edges of <var>gamma</var>,
which must be a simple graph.
<p>
See also <a href="CHAP003.htm#SSEC013.1">DirectedEdges</a>.
<p>
<pre>
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 ] ]
</pre>
<p>
<p>
<h2><a name="SECT015">3.15 Distance</a></h2>
<p><p>
<a name = "SSEC015.1"></a>
<li><code>Distance( </code><var>gamma</var><code>, </code><var>X</var><code>, </code><var>Y</var><code> )</code>
<li><code>Distance( </code><var>gamma</var><code>, </code><var>X</var><code>, </code><var>Y</var><code>, </code><var>G</var><code> )</code>
<p>
This function returns the distance from <var>X</var> to <var>Y</var> in <var>gamma</var>. The
parameters <var>X</var> and <var>Y</var> may be vertices or nonempty lists of vertices.
We define the <strong>distance</strong> <var>d(<var>X</var>,<var>Y</var>)</var> from <var>X</var> to <var>Y</var> to be the minimum
length of a (directed) path joining a vertex of <var>X</var> to a vertex of <var>Y</var>
if such a path exists, and <var>-1</var> otherwise.
<p>
The  optional parameter <var>G</var>,  if present, is assumed to  be a subgroup of
<var>Aut(<var>gamma</var>)</var> fixing  <var>X</var>  setwise.  Including  such a <var>G</var> can speed up
the function.
<p>
See also <a href="CHAP003.htm#SSEC016.1">Diameter</a>.
<p>
<pre>
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
</pre>
<p>
<p>
<h2><a name="SECT016">3.16 Diameter</a></h2>
<p><p>
<a name = "SSEC016.1"></a>
<li><code>Diameter( </code><var>gamma</var><code> )</code>
<p>
This  function  returns the  diameter of <var>gamma</var>.  A diameter of <var>-1</var>
is returned if <var>gamma</var> is not (strongly) connected.  Otherwise, the
<strong>diameter</strong> of <var>gamma</var> is equal to the maximum (directed) distance
<var>d(x,y)</var> in <var>gamma</var> (as <var>x</var> and <var>y</var> range over all the vertices of 
<var>gamma</var>).
<p>
See also <a href="CHAP003.htm#SSEC015.1">Distance</a>.
<p>
<pre>
gap> Diameter( JohnsonGraph( 5, 3 ) );
2
gap> Diameter( JohnsonGraph( 5, 4 ) );
1 
</pre>
<p>
<p>
<h2><a name="SECT017">3.17 Girth</a></h2>
<p><p>
<a name = "SSEC017.1"></a>
<li><code>Girth( </code><var>gamma</var><code> )</code>
<p>
This function returns the girth of <var>gamma</var>, which must be a simple graph.
A girth of <var>-1</var> is returned if <var>gamma</var> is a forest.  Otherwise the <strong>girth</strong>
is the length of a shortest cycle in <var>gamma</var>.
<p>
<pre>
gap> Girth( JohnsonGraph( 4, 2 ) );
3 
</pre>
<p>
<p>
<h2><a name="SECT018">3.18 IsConnectedGraph</a></h2>
<p><p>
<a name = "SSEC018.1"></a>
<li><code>IsConnectedGraph( </code><var>gamma</var><code> )</code>
<p>
This boolean function returns <code>true</code> if and only if the graph <var>gamma</var>
is (strongly) <strong>connected</strong>, i.e. there is a (directed) path from <var>x</var> to
<var>y</var> for every pair of vertices <var>x,y</var> of <var>gamma</var>.
<p>
<pre>
gap> IsConnectedGraph( JohnsonGraph(4,2) );
true
gap> IsConnectedGraph( NullGraph(SymmetricGroup(4)) );
false 
</pre>
<p>
<p>
<h2><a name="SECT019">3.19 IsBipartite</a></h2>
<p><p>
<a name = "SSEC019.1"></a>
<li><code>IsBipartite( </code><var>gamma</var><code> )</code>
<p>
This boolean function returns <code>true</code> if and only if the graph <var>gamma</var>,
which must be simple, is <strong>bipartite</strong>, i.e. if the vertex-set can be
expressed as the disjoint union of two sets, on each of which <var>gamma</var>
induces a null graph (these two sets are called the <strong>bicomponents</strong> or
<strong>parts</strong> of <var>gamma</var>).
<p>
See also <a href="CHAP005.htm#SSEC003.1">Bicomponents</a> and <a href="CHAP006.htm#SSEC010.1">BipartiteDouble</a>.
<p>
<pre>
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
</pre>
<p>
<p>
<h2><a name="SECT020">3.20 IsNullGraph</a></h2>
<p><p>
<a name = "SSEC020.1"></a>
<li><code>IsNullGraph( </code><var>gamma</var><code> )</code>
<p>
This boolean function returns <code>true</code> if and only if the graph <var>gamma</var> has
no edges.
<p>
See also <a href="CHAP002.htm#SSEC003.1">NullGraph</a>.
<p>
<pre>
gap> IsNullGraph( CompleteGraph( Group(()), 3 ) );
false
gap> IsNullGraph( CompleteGraph( Group(()), 1 ) );
true 
</pre>
<p>
<p>
<h2><a name="SECT021">3.21 IsCompleteGraph</a></h2>
<p><p>
<a name = "SSEC021.1"></a>
<li><code>IsCompleteGraph( </code><var>gamma</var><code> )</code>
<li><code>IsCompleteGraph( </code><var>gamma</var><code>, </code><var>mustloops</var><code> )</code>
<p>
This boolean function returns  <code>true</code> if and only if the graph <var>gamma</var> is
a complete graph.  The optional boolean  parameter <var>mustloops</var> determines
whether all loops must be present for <var>gamma</var> to be considered a complete
graph (default: <code>false</code> (loops are ignored)).
<p>
See also <a href="CHAP002.htm#SSEC004.1">CompleteGraph</a>.
<p>
<pre>
gap> IsCompleteGraph( NullGraph( Group(()), 3 ) );
false
gap> IsCompleteGraph( NullGraph( Group(()), 1 ) );
true
gap> IsCompleteGraph( CompleteGraph(SymmetricGroup(3)), true );
false 
</pre>
<p>
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP002.htm">Previous</a>] [<a href ="CHAP004.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<P>
<address>grape manual<br>September 2025
</address></body></html>

99%


¤ Dauer der Verarbeitung: 0.3 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




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.