news.

graph theory basics

whilst doing my masters (which focussed on graphical models), i used to joke that i was researching the areas i loved most (graph theory), and hated most (statistics). since then my focus has changed somewhat (and i don’t hate statistics anymore), but graph theory remains fun to play with.

(very) basics of graph theory

simply put, a graph G=(V,E) consists of a finite, non-empty set of vertices (or nodes) V connected to each other by a set of edges (or links/arcs) E. consider the graph G in figure 1. the vertex set is V={a, b, c, d, e} and the edge set is E = {ab, ae, bc, be, cd}. this is known as an undirected graph, since the edges are not directed from one vertex to another. a directed graph is shown in figure 2. this graph has vertex set V={u,v,w} and edge set E={uv, uw, wv}. note that the edge vw is not present in the directed graph, since the direction of the arrow is from vertex w to vertex v.

figure 1: undirected graph G=({a, b, c, d, e}, {ab, ae, bc, be, cd}

figure 1: undirected graph G=({a, b, c, d, e}, {ab, ae, bc, be, cd}

figure 2: directed graph

figure 2: directed graph

edges indicate that there is some type of relationship (depending on the problem being modelled) between the two vertices that they connect.

a walk in a graph is a sequence of alternating vertices and edges, such as v0e1v1…eivi…envn with ei connecting vertices vi-1 and vi. a u-v walk in a graph is such that u=v0 and v=vn. in figure 1 there are 2 a-d walks, namely a-b-c-d and a-e-b-c-d.u-v walk does not take direction into account, whereas a directed walk does. a closed walk is one where v0=vn. in a walk, edges may be repeated. in a trail, however, no edges may be repeated.

in certain situation, weights are associated with the edges. for instance, say the vertices represent cities, and edges direct routes between the cities. the weight of an edge will then represent the distance between the two cities.

a planar graph is a graph where none of the edges cross each other (or a graph that can be drawn such that none of the edges cross each other. the graphs in figures 1 and 2 are planar, whereas the heawood graph, illustrated in figure 3, is not planar, seeing as it cannot be drawn such that there are no overlapping edges.

figure 3: heawood graph - non-planar graph

figure 3: heawood graph – non-planar graph

with these basic ideas in place, we can consider some of the more famous graph theory problems, namely the köningsberg bridge problem, the travelling salesman problem and the 4-colour problem.

köningsberg bridge problem

this is quite a famous problem since it is often cited as the “beginning of graph theory”. in this problem, there are 7 bridges of the river pregel. as the story goes, according to [1], the residents of köningsberg (now kaliningrad in russia) debated about whether one could travel across all 7 bridges, without doubling back,  and end at the same place as where one started (ie a closed trail). a drawing of the bridges, taken from [1], is shown in figure 4.  (since the original problem, some of the bridges were removed and some were joined).

figure 4: bridges of k

figure 4: bridges of köningsberg, taken from [1]

 

one way of representing the problem using a graph, also taken from [1], is given in figure 5.

figure 5:graphical representation of the bridges, taken from [1]

figure 5:graphical representation of the bridges, taken from [1]

here vertex A represents alstadt and löbnicht, vertex K represents kneiphof, vertex V represents vorstadt and vertex L represents lomse. each edge represents one bridge. euler, in [2], proved that no such trail exists. since then, a graph that does hold a closed trail is often referred to as an eulerian graph. for more information on the history of this problem, such as a discussion on the bridges being removed and built, see [1].

 

the travelling salesman problem

the basics of this problem was already touched on when discussing weights placed on edges. a travelling salesman knows which cities he must visit, and the distance between cities. he wants to find the shortest route that will allow him to visit each city exactly once, except the initial city, since he wants to return to the city he starts from (this is also know as a hamiltonian cycle). if we model this problem using graphs, each city will be represented by a node and each weighted edge will represent a route between the cities. in the köningsberg bridge problem, each edge had to be visited exactly once. in this problem, each node has to be visited exactly once.

consider the example in figure 6.  the hamiltonian cycle b-d-c-a-e-b gives a total weight of 120, the cycle a-b-e-d-c-a gives a total weight of 120 as well, whereas the hamiltonian cycle a-e-d-b-c-a gives a total weight of 85. if only these cycles are considered (there are other possibilities too), the solution to this problem would be a-e-d-b-c-a.

figure 6: travelling salesman example graph

figure 6: travelling salesman example graph

although an example like this can easily be solved by inspection, in general the travelling salesman problem is np-hard.

4-colour theorem

the four-colour theorem basically says that any map can be coloured such that no two adjacent regions have the same colour, using only 4 colours. a map in this instance could be what most of know as a map, but more generally, it is when a plane is separated into adjoining regions. consider the map in figure 7, taken from [3].

figure 7: map of the united states coloured according to four colour theorem, taken from [3].

figure 7: map of the united states coloured according to four colour theorem, taken from [3].

in figure 8, a section of this map is taken and drawn as a planar graph, with the vertices coloured. it is graphs like these that can be used when using techniques to determine what colour each section should be.

figure 8: planar graph of section of map in figure 7, taken from [3].

figure 8: planar graph of section of map in figure 7, taken from [3].

other applications

apart from the above more famous problems, graph theory is used extensively in other areas as well. most notably is that it is used for all kinds of network problem (such as traffic flow, social networks on the internet – think degrees of separation, deciding where to build new service buildings such as hospitals, etc). some even solve sudoko games by using graph theory.

references

[1] gribkovskaia, i., halskau, Ø., & laporte, g. (2007). the bridges of königsberg—a historical perspective. networks49(3), 199-203.

[2] euler, l. “solutio problematis ad geometriam situs pertinentis”. commentarii academiae scientarum imperialis petropolitanea 8, 128-140, 1736.

[3] legner, p., http://world.mathigon.org/Graph_Theory. accessed on 31-10-2013.

No comments yet.

Leave a comment

Leave a Reply

(required)