A-level Mathematics/OCR/D1/Node Graphs/Introduction

This section is concerned with node graphs, sometimes known as graphs, or networks.

Firstly, we must say what we mean by a graph. A graph is a set of points (which we call nodes, or vertices), connected by lines (arcs, or edges). When thinking about graphs, the length and layout of each arc do not matter, only which vertices are connected to which other vertices.

The Königsberg Bridge Problem

The Königsberg Bridge Problem, or the Seven Bridges of Königsberg, is a classic problem, one of the first in graph theory. It was inspired by the actual layout of the city of Königsberg, Prussia (now Kaliningrad).

Above is a map of the city, with a river coloured in blue, and the bridges in green. The problem is this, is it possible to start somewhere in the city, and cross each bridge one and only once, and return to the starting point. Mathematician Leonard Euler (1707–1783) managed to solve this problem, by concentrating on the important aspects. He realised that all that matters is which places are connected, and how many times, not the length of each bridge, or their layout. In other words, the problem can be represented by a graph. Below is one such representation:

In the graph, the red points are vertices representing each bank of the river, and the two islands in the middle. The lines and curves between are arcs representing the bridges. Euler's solution to the problem is easier to see in such an abstract representation. He released that it was impossible to traverse each bridge only once, for the following reason:

As a walker traverses the bridges, every place they visit, apart from the start and end, they must enter and exit in pairs. That is, if they visit once, they enter, then leave, if twice, they enter twice and leave twice, and so on. This means, as each entrance and exit must be by a different bridge, and all the bridges must be used, there must be an even number of bridges leading from each point, apart from the start and end of the route. The start and end can in general be exceptions, as the walker leaves one without entering, and enters the other without leaving, so there will be an odd number of bridges from them. However, if the start and end are the same, as required here, then the entrances and exits pair off again, so all points must have an even number of bridges from them.

To summarise, such a route is possible if there are an even number of bridges from each point. This means that in the case of the Seven Bridges of Königsberg it is impossible to traverse each bridge once and only once in sequence, as each point has an odd number of bridges leading from it. It isn't even possible to start and end from different places.

Eulerian and Semi-Eulerian Graphs

Euler's solution to the Königsberg Bridge problem leads to a result that applies to all graphs. Before we see this however, we need some more terminology.

Firstly, a Eulerian path is a route from one vertex to another in a graph, using up all the edges in the graph. A Eulerian circuit is a Eulerian path, where the start and end points are the same. This is equivalent to what would be required in the problem. Given these terms a graph is Eulerian if there exists an Eulerian circuit, and Semi-Eulerian if there exists a Eulerian path that is not a circuit. Finally, the degree of a vertex is the number of edges that lead from it.

The result above showed that a graph can only be Eulerian if all vertices have an even number of edges from them. In other words, each vertex must have an even degree. It was later proven that any graph with all vertices of even degree will be Eulerian. Similarly if and only if a graph has only 2 vertices with odd order, it will be Semi-Eulerian.

Examples

Below are some examples of graphs, which illustrate how we can tell if a graph is eulerian, or semi-eulerian:

• 
  Example one
• 
  Example two
• 
  Example three
• 
  Example four

Example one is a graph that is neither Eulerian, or Semi-Eulerian, as there are four vertices of odd degree, rather than the required zero (for a eulerian graph), or two (for a semi-eulerian graph).

Examples two and three are Semi-eulerian, as two vertices only have odd degree.

Example four is Eulerian, as all of its vertices have even degree.

Fleury's algorithm

Now we know how to tell if a eulerian path or circuit exists. However, we do not have a method of generating such a path. Fleury's algorithm is one method that is guaranteed to provide such a path or circuit when they exist. The method is as follows:

1. Pick any vertex of odd degree. If none exist then pick any vertex.
2. Choose any edge from that vertex that we can delete from the graph without disconnected it. In other words, when we remove the edge, we can still get from any vertex to any other vertex.
3. Cross that edge, and delete it from the graph.
4. Delete any vertices that have no edges leading from # them.
5. If any edges are left to cross, return to step 2.

If we follow this method, we will have followed a eulerian path, or trial, provided one exists. The condition to keep the graph connected removes the possibility that we split the graph into two "islands", and end up standed on one of them, with no unused edges to get back to the other one. We can leave "orphan" vertices, with no edgres from them, disconnected, as there are no edges to and from them to traverse. This is why we can delete them.

No eulerian path can split the graph as describes, so any eulerian path must be formed by using the algorithm.

May want to define more terms at this point.