# Graph theory¶

See the Sage wiki page http://wiki.sagemath.org/graph_survey for an excellent survey of exisiting graph theory software.

## Networkx¶

Networkx (http://networkx.lanl.gov) “is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks”. More details can also be found on http://wiki.sagemath.org/graph_survey or in Robert Miller’s SageDays 3 talk.

sage: C = graphs.CubeGraph(4)


Now type C.show(vertex_labels=False, vertex_size=60, graph_border=True, figsize=[9,8]) to view this with some of the options.

The digraph below is a $$3$$-cycle with vertices $$\{0,1,2\}$$ and edges $$0\rightarrow 1$$, $$1\rightarrow 2$$, $$2\rightarrow 0$$:

sage: D = DiGraph( { 0: [1], 1: [2], 2: [0]} )


Type D.show() to view this.

## Cayley graphs¶

includes wrappers to many NetworkX commands, written mainly by Emily Kirkman and Robert Miller. The implementation of Cayley graphs was written by Bobby Moretti and Robert Miller.

sage: G = DihedralGroup(5)
sage: C = G.cayley_graph(); C
Digraph on 10 vertices
sage: C.diameter()
3
sage: C.girth()
2
sage: C.automorphism_group().order()
10
sage: len(C.edges())
20


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

Here is an example of the syntax in (copied from Robert Miller’s SageDays 3 talk): 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. A diameter of $$-1$$ is returned if G is not (strongly) connected. Otherwise, the diameter of G is equal to the maximum (directed) distance $$d(x,y)$$ in G (as $$x$$ and $$y$$ range over all the vertices of G).

sage: M = Matrix ([ [0, 1, 1], [1, 0, 1], [1, 1, 0] ])
sage:  # (the order is the number of edges)
sage: G = Graph(M); G.order()
3
sage: G.distance(0,2)
1
sage: G.diameter()
1