Introduction To Graph Theory
The best way to introduce GT is perhaps, the way my lecturer Ms.Radhika did — with the Konisberg Bridge Problem.
The Seven Bridges of Königsberg
The Seven Bridges of Königsberg is a historically notable problem in mathematics. It goes like this.
The city of Königsberg in Prussia which is now known as Kaliningrad, Russia) was set on both sides of the Pregel River. It included two large islands — Kneiphof and Lomse. These landmasses were connected to each other, or to the two mainland portions of the city, by seven bridges, as shown in the actual map above.
Problem Statement: Plan a route through the city that would cross each of those seven bridges once and only once.
Conditions:
These are not allowed
- Reaching an island or mainland bank other than via one of the bridges
- Accessing any bridge without crossing to its other end
Solution: It’s at the end of the blog. Give it a few minutes thought amigo.
What does this have anything to do with Graph Theory?
Well, Euler observed that…
1. Choice of land route within each land mass is irrelevant.
This implied that the problem needn’t be viewed photographically or in a map, but can be expressed in an abstract form.
This kinda means you could chuck the map, draw each landmass as a dot or node, and the bridges as lines or curves. This also means you can bend this drawing in any way ( without breaking the lines/curves or removing anything) and the problem and solution would still be the same!
This transforms our problem as below
2. If one enters by a bridge, one must leave by a bridge.
Euler observed that except at the endpoints of the walk, when one enters a vertex by a bridge, one must exit the vertex by a bridge. That is the number of times one enters a non-terminal vertex equals the number of times one leaves it. Now, if every bridge can be walked upon just once, then for each vertex ( the non-terminal ones) the number of bridges touching that land mass must be even, that is the degree of each node should be even(half of them towards,half away from the land)
He concluded that a necessary condition for the walk of the desired form is that the graph be connected and have exactly zero or two landmasses of odd degree.The rest must be of even degree.( The degree refers to the number of bridges connected to it)
But in our problem here, degree of a, b, c and d are 3. All nodes have odd degrees, which mean a solution is impossible.
There is no solution!A bit disappointing huh, but this problem laid foundation to the much renowned Graph Theory. It took over 150 years for mathematicians to picture as a graph though.
So what is a graph?
Some defintions:
A Graph is an ordered triplet G=(V(G), E(G), ψ(G)) consisting of non-empty set V(G) of vertices, a set E(G) of edges and an incidence function ψ(G) that associates with each edge of G with an un-ordered pair of vertices.
The definition means you can have a graph with no edges and just nodes, but the converse won’t be a graph.
To relate with the problem, the landmasses we saw in point 1 are the vertices, the bridges are the edges, a mapping function of both would be your ψ(G) and the entire figure is your graph.
A simple graph would be one with neither self-loops( the edge starts and ends on the same node) or parallel edges( edges that share the same nodes).
A graph would be trivial if it had just one isolated node.
Two vertices are said to be adjacent if they are the end vertices of the same edge.
When a vertex v is an end vertex of some edge e, then they are said to incident on each other.
That’s it folks. That’s how Graph Theory was first conceived.This is a humble introduction to GT. With more on this fine subject, see you on the next blog!
