%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % %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 <obj>, 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 <v> 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 <gamma> 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 <gamma> 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 <e> 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 <gamma> 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 <gamma>, 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 <gamma> 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 <gamma> 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