The development of the Internet and the World Wide Web has changed our outlook on the world.  Science has followed suit with an increased emphasis on the study of networks.  However, mathematicians have studied networks for over one hundred years.  A network, to a mathematician, is a graph, and graph theory is a fertile research area on the cross-section of mathematics and computer science.

This course offers an introduction to graph theory, with an emphasis on applications and modelling.  Topics include: paths and cycles, shortest route problem, connectivity and trees, minimum spanning trees, network flow, planar graphs, matchings, assignment problem, graph colouring, Hamiltonian cycles and the Traveling Salesman Problem.

Topics to be covered include (but are not limited to):

1. *Paths, cycles and the concept of diameter
   

2. *Shortest paths
   

3. *Connectivity, strong connectivity & connected components
   

4. *Connectivity and spanning trees
   

5. *Minimum flow & maximum cut
   

6. *Graph colouring
   

7. *Graph models