This chapter describes functions to inspect graphs, vertices and edges.
IsGraph( obj )
This boolean function returns true if and only if obj, which can be
an object of arbitrary type, is a graph.
gap> IsGraph( 1 ); false gap> IsGraph( JohnsonGraph( 3, 2 ) ); true
OrderGraph( gamma )
This function returns the number of vertices (the order) of the graph gamma.
gap> OrderGraph( JohnsonGraph( 4, 2 ) ); 6
IsVertex( gamma, v )
This boolean function returns true if and only if v is vertex of
the graph gamma.
gap> gamma := JohnsonGraph( 3, 2 );; gap> IsVertex( gamma, 1 ); true gap> IsVertex( gamma, 4 ); false
VertexName( gamma, v )
This function returns (an immutable copy of) the name of vertex v in the graph gamma.
See also VertexNames and AssignVertexNames.
gap> VertexName( JohnsonGraph(4,2), 6 ); [ 3, 4 ]
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.
gap> VertexNames( JohnsonGraph(4,2) ); [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]
Vertices( gamma )
This function returns the vertex-set {1,..., gamma.order}
of the graph gamma.
gap> Vertices( JohnsonGraph( 4, 2 ) ); [ 1 .. 6 ]
VertexDegree( gamma, v )
This function returns the (out)degree of the vertex v of the graph gamma.
gap> VertexDegree( JohnsonGraph( 3, 2 ), 1 ); 2
VertexDegrees( gamma )
This function returns the set of vertex (out)degrees for the graph gamma.
gap> VertexDegrees( JohnsonGraph( 4, 2 ) ); [ 4 ]
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].
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
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].
gap> IsSimpleGraph( CompleteGraph( Group( (1,2,3) ), 3 ) ); true gap> IsSimpleGraph( CompleteGraph( Group( (1,2,3) ), 3, true ) ); false
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.
gap> Adjacency( JohnsonGraph( 4, 2 ), 1 ); [ 2, 3, 4, 5 ] gap> Adjacency( JohnsonGraph( 4, 2 ), 6 ); [ 2, 3, 4, 5 ]
IsEdge( gamma, e )
This boolean function returns true if and only if e is an edge of
the graph gamma.
gap> IsEdge( JohnsonGraph( 4, 2 ), [ 1, 2 ] ); true gap> IsEdge( JohnsonGraph( 4, 2 ), [ 1, 6 ] ); false
DirectedEdges( gamma )
This function returns the set of directed (ordered) edges of the graph gamma.
See also UndirectedEdges.
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 ] ]
UndirectedEdges( gamma )
This function returns the set of undirected (unordered) edges of gamma, which must be a simple graph.
See also DirectedEdges.
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 ] ]
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.
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
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.
gap> Diameter( JohnsonGraph( 5, 3 ) ); 2 gap> Diameter( JohnsonGraph( 5, 4 ) ); 1
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.
gap> Girth( JohnsonGraph( 4, 2 ) ); 3
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.
gap> IsConnectedGraph( JohnsonGraph(4,2) ); true gap> IsConnectedGraph( NullGraph(SymmetricGroup(4)) ); false
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.
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
IsNullGraph( gamma )
This boolean function returns true if and only if the graph gamma has
no edges.
See also NullGraph.
gap> IsNullGraph( CompleteGraph( Group(()), 3 ) ); false gap> IsNullGraph( CompleteGraph( Group(()), 1 ) ); true
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.
gap> IsCompleteGraph( NullGraph( Group(()), 3 ) ); false gap> IsCompleteGraph( NullGraph( Group(()), 1 ) ); true gap> IsCompleteGraph( CompleteGraph(SymmetricGroup(3)), true ); false
[Up] [Previous] [Next] [Index]
grape manual