[Up] [Previous] [Next] [Index]

3 Functions to inspect graphs, vertices and edges

Sections

  1. IsGraph
  2. OrderGraph
  3. IsVertex
  4. VertexName
  5. VertexNames
  6. Vertices
  7. VertexDegree
  8. VertexDegrees
  9. IsLoopy
  10. IsSimpleGraph
  11. Adjacency
  12. IsEdge
  13. DirectedEdges
  14. UndirectedEdges
  15. Distance
  16. Diameter
  17. Girth
  18. IsConnectedGraph
  19. IsBipartite
  20. IsNullGraph
  21. IsCompleteGraph

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

3.1 IsGraph

  • 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 
    

    3.2 OrderGraph

  • OrderGraph( gamma )

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

    gap> OrderGraph( JohnsonGraph( 4, 2 ) );
    6 
    

    3.3 IsVertex

  • 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 
    

    3.4 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.

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

    3.5 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.

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

    3.6 Vertices

  • Vertices( gamma )

    This function returns the vertex-set {1,, gamma .order} of the graph gamma.

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

    3.7 VertexDegree

  • VertexDegree( gamma, v )

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

    gap> VertexDegree( JohnsonGraph( 3, 2 ), 1 );
    2 
    

    3.8 VertexDegrees

  • VertexDegrees( gamma )

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

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

    3.9 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].

    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 
    

    3.10 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].

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

    3.11 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.

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

    3.12 IsEdge

  • 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 
    

    3.13 DirectedEdges

  • 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 ] ]
    

    3.14 UndirectedEdges

  • 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 ] ]
    

    3.15 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.

    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
    

    3.16 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.

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

    3.17 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.

    gap> Girth( JohnsonGraph( 4, 2 ) );
    3 
    

    3.18 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.

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

    3.19 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.

    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
    

    3.20 IsNullGraph

  • 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 
    

    3.21 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.

    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
    January 2016