Subsections

7. Graph theory


7.1 Cayley graphs

In general, to do any graph theory in SAGE, you must load Leonard Soicher's GAP package GRAPE ({http://www.gap-system.org/Packages/grape.html), which in turn calls the C programs in Brendan McKay's nauty (http://cs.anu.edu.au/people/bdm/nauty/). These packages require a unix environment to be installed (such as linux or cygwin - see the GRAPE readme file http://www.maths.qmul.ac.uk/~leonard/grape/README file for details). To install GRAPE in SAGE, see §18.8.

sage: gap.eval('LoadPackage("grape")')           # need optional gap packages
      'true'
sage: print gap.eval("C := CayleyGraph(SymmetricGroup(4),[(1,2),(2,3),(3,4)])")               # optional gap package
rec( isGraph := true, order := 24,
  group := Group([ (1,10,17,19)(2,9,18,20)(3,12,14,21)(4,11,13,22)(5,7,16,
        23)(6,8,15,24), (1,7)(2,8)(3,9)(4,10)(5,11)(6,12)(13,15)(14,16)(17,
        18)(19,21)(20,22)(23,24) ]),
  schreierVector := [ -1, 1, 1, 2, 2, 1, 2, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2,
      1, 1, 2, 2, 1, 2 ], adjacencies := [ [ 2, 3, 7 ] ],
  representatives := [ 1 ],
  names := [ (), (3,4), (2,3), (2,3,4), (2,4,3), (2,4), (1,2), (1,2)(3,4),
      (1,2,3), (1,2,3,4), (1,2,4,3), (1,2,4), (1,3,2), (1,3,4,2), (1,3),
      (1,3,4), (1,3)(2,4), (1,3,2,4), (1,4,3,2), (1,4,2), (1,4,3), (1,4),
      (1,4,2,3), (1,4)(2,3) ], isSimple := true )
sage: print gap.eval("Girth(C)")                   # optional gap package
4
sage: print gap.eval("Diameter(C)")                   # optional gap package
6
sage: print gap.eval("AutGroupGraph(C)")                   # optional gap package (uses nauty)
Group([ (2,7)(4,13)(5,9)(6,15)(10,19)(12,21)(16,20)(18,23),
  (1,2)(3,5)(4,6)(7,8)(9,11)(10,12)(13,19)(14,20)(15,21)(16,22)(17,23)(18,24),
  (1,3)(2,4)(5,6)(7,13)(8,14)(9,15)(10,16)(11,17)(12,18)(19,20)(21,23)(22,24)
 ])

The command AutGroupGraph uses the 2.2 version of nauty.


7.2 Graphs from adjacency matrices

To construct the graph Gamma with $ n \times n$ adjacency matrix $ A$ , you want a graph $ X$ so that the vertex-set of Gamma is $ \{1,..., n\}$ , and $ [i,j]$ is an edge of Gamma if and only if $ A[i][j] = 1$ . Here is an example of the syntax:

sage: gap.eval("A := [[0,1,0],[1,0,0],[0,0,1]]")
      '[ [ 0, 1, 0 ], [ 1, 0, 0 ], [ 0, 0, 1 ] ]'
sage: gap.eval("G := Group( (1,2) )")
      'Group([ (1,2) ])'
sage: print gap.eval("Gamma := Graph( G, [1..3], OnPoints,
       function(x,y) return A[x][y] = 1; end,true )")           # optional gap package
rec( isGraph := true, order := 3, group := Group([ (1,2) ]),
  schreierVector := [ -1, 1, -2 ], adjacencies := [ [ 2 ], [ 3 ] ],
  representatives := [ 1, 3 ], names := [ 1, 2, 3 ] )
sage: gap.eval("Adjacency(Gamma,1)")           # optional gap package
      '[ 2 ]'
sage: gap.eval("Adjacency(Gamma,2)")           # optional gap package
      '[ 1 ]'
sage: gap.eval("Adjacency(Gamma,3)")           # optional gap package
      '[ 3 ]'
sage: gap.eval("IsEdge( Gamma, [ 1, 2 ] )")           # optional gap package
      'true'
sage: gap.eval("Vertices( Gamma )")           # optional gap package
      '[ 1 .. 3 ]'

Define the distance $ d(x,y)$ from $ x$ to $ y$ to be the minimum length of a (directed) path in Gamma joining a vertex $ x$ to a vertex $ y$ if such a path exists, and $ -1$ otherwise.

sage: gap.eval("Distance( Gamma, 1, 3 )")           # optional gap package
      '-1'

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

sage: gap.eval("Distance( Gamma, 1, 2 )")           # optional gap package
      '1'

See About this document... for information on suggesting changes.