Graph Theory

Graph Theory is simply a branch of mathematics focusing on the properties of graphs. In this branch of mathematics, the term 'graph' has nothing to do with the graphs commonly used to illustrate data, as the definitions below will show. The aim of this page is to provide a simple introduction to this interesting branch of mathematics, and to briefly outline the ways in which algorithms can be used to solve some problems relating to graphs.

A graph is simply a set of points, some or all of which are connected by lines.
A simple example:
A simple example of a graph
Points are also commonly referred to as NODES or VERTICES, similarly lines are known as EDGES or ARCS. I will usually use the terms 'node' and 'arc'.

Some useful terminology (all examples refer to the graph above)
  • A walk is a finite sequence of arcs such that the end node of one arc is the starting node of the next, e.g. ACBEDBAC.
  • A trail is a walk in which no arc is used more than once, e.g. ACBEDB.
  • A path is a trail in which no node is passed through more than once, e.g. DEBCA.
  • A cycle is a closed path, e.g. ACEDBA.
  • Two nodes are connected if there is a path between them, although not necessarily direct.
  • A tree is a connected path with no cycles.
  • The order of a node is the number of arcs connected to it. Note therefore that the sum of the orders of any graph MUST BE EVEN since each arc must count twice.

A complete graph is one in which there is a DIRECT connection between every pair of nodes. These can be denoted by K2, K3, K4, K5, etc. These first 4 cases are shown by the diagrams below.
Examples of complete graphs
With n nodes there are 0.5 x n x (n-1) arcs required for a complete graph.

Traversability

Traversability of graphs was first studied in detail by the mathematician Leonard Euler in 1736, as he tried to solve a problem known as the 'Seven Bridges of Königsberg'. A graph is traversable or Eulerian if it is possible to pass over each arc exactly once and return to the starting point. A graph is semi-traversable (semi-Eulerian) if it is possible to start at one node and pass over each arc exactly once, finishing at a different node. In all other cases, a graph is non-traversable or non-Eulerian. The city of Königsberg, set on the river Pregel in Prussia, included two large islands which were connected to each other and the mainland by seven bridges. The question set in 1736 was whether it was possible to walk a route that crossed each bridge exactly once, and returned to the starting point, i.e if the graph corresponding to the problem was Eulerian.

A photograph of Leonard Euler
In general, to determine the traversibility of a graph, apply EULER'S THEOREM:
A graph is Eulerian if and only if it has no nodes of odd order,
A graph is semi-Eulerian if it has EXACTLY 2 nodes of odd order (to traverse the graph it is necessary to start at one of these nodes and finish at the other),
A graph is non-Eulerian if it has more than 2 nodes of odd order.

In the problem above, Euler proved that it was not possible to walk a route that crossed each bridge exactly once, and returned to the starting point, since the graph corresponding to Königsberg has four nodes of odd order.



Examples
Examples of an Eulerian, a Semi-Eulerian, and a Non-Eulerian graph
Check these examples for yourself!

NETWORKS

A network is simply a graph with numbers (weights) associated with its arcs. A simple way to think of these weights is as distances or times, although this does not have to be the case. These weights lead to several types of problems relating to networks, each with a special algorithmic method that can be used to solve the problem.

Problem Type 1: Minimum Spanning Tree (MST)
A spanning tree is a tree (so has no cycles) that contains all the nodes. The MST is the one with the least total weight. Two different algorithms can be used to find the MST.

A) Prim's Algorithm
Step 1- Choose any node
Step 2- Connect this to the 'nearest' node (by weight) to form a tree. If there is a choice of nodes, choose either.
Step 3- Connect to the tree the unconnected node that is 'nearest' to the tree, although NOT NECESSARILY nearest to the last node connected. Again, if there is a choice, choose either.
Step 4- Repeat Step 3 until all nodes are connected. Then stop.

B) Kruskal's Algorithm
This simply looks for the LOWEST weight amongst all unconnected arcs and adds it to the 'chosen set', provided it doesn't create a cycle. This continues until all nodes have been included. Both of these algorithms will ALWAYS find the MST (if applied correctly!)

Problem Type 2: Finding path of least weight between 2 nodes
This can be found using DIJKSTRA'S algorithm, where each node is assigned a label. The lowest total weight from the starting node up to each node is recorded so that nodes are systematically labelled in the order of least weight.

The convention for labels is:
ORDER OF
PERMANENT LABEL		 LEAST WEIGHT
FROM SOURCE
SPACE FOR WORKING VALUES

It is easiest to show how the algorithm works by using an example. The first few steps of the algorithm will be specific to this example, and then the algorithm will become more general. Consider the following matrix:
Simple example of a network

To find the shortest path from A to E using Dijkstra's algorithm:
Step 1- Permanently label A as 1, with least weight total 0,
Step 2- For each of the nodes directly connected to A (B, C and D), place the weight from A in the working box. These boxes are now 'open'.
Step 3- Select the open box of least total weight (choose either if more than one) and permanently label it one more than previously labelled node. Enter its least total weight.
Step 4- Take the most recently labelled node 'x' and consider each unlabelled box connected to it. For each one add the arc weight to the least weight total of 'x'. If this is less than the previous working then replace it.
Step 5- Repeat Steps 3 and 4 until all points are chosen, or at least until the endpoint is labelled.

Remembering our example, following these steps closely will show that the shortest path from A to E has weight 9 (ACDE). Even in this simple case it would be easy at first glance to think that the shortest route from A to E was ABE, ACE or ADE, and so it soon becomes clear with more complex networks that the use of Dijkstra's algorithm is essential whenever a shortest path has to be found.

Problem Type 3: Route inspection

This problem is to find the shortest (by weight) route around a network so as to start and finish at the same node and to traverse each arc at least once. This is known as the CHINESE POSTMAN PROBLEM.

If the network is Eulerian (traversable) there is no real problem. As any network MUST have an even number of odd nodes, consider first the case with exactly two odd nodes. It is possible to traverse the route without retracing steps by starting at one of these nodes and finishing at the other. It is therefore only necessary to find the path of least weight between these two odd nodes, as this will need to be retraced in order to complete the whole journey. This can be found by Dijkstra's algorithm (or inspection in very simple cases), and so this is added to the sum of all the weights to give the required shortest route.

If there are four (or more) odd nodes, it is necessary to consider each possible pairings of odd nodes, and to find the paths of least weight for each. For example if there are 4 odd nodes A, B, C and D, then there are 3 possible sets of pairings: AB CD, AC BD, and AD BC. These three pairings require the use of Dijkstra's algorithm 6 times, and the smallest total from these three pairings is again added to the sum of the weights to give the solution to the problem.

With 6 odd nodes there are 15 possible combinations of pairings (each of these has 3 pairs so Dijkstra's algorithm is needed 45 times). It is therefore clear that even with as few as 6 odd nodes, finding a solution to this problem can become very time-consuming and tedious. As with all of the previously mentioned algorithms, it may be necessary to program a computer to solve the problem, although if the number of odd nodes becomes too large the problem will even be beyond the capability of a computer.

Links and Bibliography

More information on Euler and the bridges problem
Another graph theory page
Back To My Home Page