graph_theory.rst

************
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 :math:`3`-cycle with vertices
:math:`\{0,1,2\}` and edges :math:`0\rightarrow 1`,
:math:`1\rightarrow 2`, :math:`2\rightarrow 0`:

::

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

Type ``D.show()`` to view this.

.. _section-cayley:

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


.. index::
   pair: graph; adjacency matrix

.. section_adjacency:

Graphs from adjacency matrices
==============================

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

Here is an example of the syntax in (copied from Robert Miller's
SageDays 3 talk): Define the distance :math:`d(x,y)` from :math:`x` to
:math:`y` to be the minimum length of a (directed) path in Gamma
joining a vertex :math:`x` to a vertex :math:`y` if such a path
exists, and :math:`-1` otherwise.
A diameter of :math:`-1` is returned if G is not (strongly)
connected. Otherwise, the diameter of G is equal to the maximum
(directed) distance :math:`d(x,y)` in G (as :math:`x` and
:math:`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