Graph Theory

In this set of articles we explore the class of objects called graphs. In its most basic incarnation a graph is a collection of vertices V and a collection of edges E. An edge is a pair of vertices (u,v) and represents a connections between those vertices. For instance, the graph given by V={a, b, c, d} and E={(a, c), (a, d), (b, c), (c, d)} is shown.

Graphs are useful tools for capturing relationships between objects. In this aspect they are frequently called networks, and if this brings the internet to mind it is no coincidence. The internet can be thought of a graph whose vertices are computers or other electronic devices and whose edges represent direct connections between these devices, wired or wireless. Similarly social relationships can be thought of as graphs where vertices are individuals and edges represent specific types of relationships.

Processes on graphs, rather random or algorithmic, provide us with a toll for studying the dynamics of such real world networks: knowing how a random particle moves in a graph might tell us something about how a file moves across a network or a book or CD passed amongst friends. Allowing for more complicated processes we can study things like the spread of trends and disease. In the articles we visit some of these processes as well as look at some structural properties of graphs. These articles are self-contained and can be sampled in any order. Their difficulty varies with the random walks and flows being the most technical.


Here are some terms and notation that will crop up repeatedly in the articles.


Solutions for the activities in the articles can be found here