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
.
To construct the graph Gamma with
adjacency matrix
,
you want a graph
so that the vertex-set of Gamma is
,
and
is an edge of Gamma if and only if
.
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
from
to
to be the minimum length
of a (directed) path in Gamma joining a vertex
to a vertex
if such a path exists, and
otherwise.
sage: gap.eval("Distance( Gamma, 1, 3 )") # optional gap package '-1'
A diameter of
is returned if Gamma is not (strongly) connected.
Otherwise, the diameter of Gamma is equal to the maximum (directed)
distance
in gamma (as
and
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.