see the figures at the end of the article )
Konigsberg was an old city in Eastern Prussia which flourished during 17th 18th century. Through this city flowed the river Pregel which divided the city in to different segments including an island called Kneiphof. In the map it can be seen that the river branches off into two branches in the right. To enable the citizens of Konigsberg to travel easily from one part of the city to another, seven bridges were constructed over the river as seen in the map. People of K tried to find a route around the city which would cross all the seven bridges only once. Their attempt failed. Many believed that the task was impossible.
The Queen of K put the problem of KB as a challenge to Mathematicians. It took about hundred years to solve the problem when in 1736 Leonhard Euler found that such a route cnnot exist. He also discovered a method to modify the bridge pattern to satisfy the people of K. By solving KB problem, Euler was laying the foundation of the branch of Mathematics called Graph Theory.
Euler's Approach to KB problem.
While solving the KB problem Euler took two important steps:
1. Map of the city was replaced to a simple diagram showing main features.
2. He denoted four land areas as points A,B,C and D and seven bridges by line a, b, c, d and e joining the points.
Euler redefined the KB problem as finite set of
vertices or nodes ( land areas) and a finite set of
edges or lines ( bridges). A path which connects all the nodes using all the edges only once was the one which was sought by the people of K. Such path ,in the language of Graph Thoery ( GT) is called the Eulerian path.
Euler solved the KB problem using the symmetry properties of the constructed diagram and showed that
If more than two areas to which odd number of bridges lead, then the journey envisaged by the people is not possible
2. If the number of bridges is odd for exactly two areas, then the journey is possible if it starts from either of these areas
3. If all the areas are connected by even number of brodges, then the journey can be accomplished by starting from any area.
In 1815, people of K honoured Euler by constructing an additional bridge over the river so that they can have the Eulerian Path to visit all parts of the city by crossing all the bridges only once.
Thus we see that the Eulerian path is possible if and only if either the number of lines joining each vertex is even or exactly two vertices are connected by odd number of bridges.
Importance of Graph Theory
Graph theory is one of the branches of mathematics which finds applications in different fields like physics, chemistry, communication technology, computer science, electrical and civil engineering, architecture, genetics, psychology, sociology, economics, anthroplogy and linguistics. It also helps in describing complex systems quantitatively. For example, it is said that the diameter of the World Wide Web is 19. The diameter is not the geometrical distance but comes from the concept of GT called connectivity or acquaintance graph diagram. On the web we get from one place to place ( pages to pages) by clicking on hypertext links. That is, we travel through such links which are the steps we take in web browsing. The question is if we select two web pages randomly how many links will separate them, on an average? Among 800 million pages, if we watch our steps we can get any where in 19 clicks. The recent interest in GT has resulted in the emergence of new branches of study like Graph Engineering and Quantum Graph Theory. The graph theoretical problem solving is followed by web search engines like
GT is also intimately connected with many branches of mathematics like group theory, matrix theory, numerical analysis, probability , topology etc. GT serves as a mathematical model for any system involving elements which interact. The diagrammatic technique of GT will help in solving problems using models. This is useful when direct solution of a complex problem is difficult. For example, graph diagrams were introduced in quantum field theory by Richard Fynmann and are called Fynmann diagrams.
GT also helps to know how different areas of knowledge are related to one another. We can ,some times, even explain such relationships and thereby clarify the connections between seemingly unrelated fields. We represent objects by vertices or nodes and interactions between the objects as connections between the nodes by lines or edges . Some of the examples are given below.
||Wires joining terminals
||Pairs of people knowing each other
In 1973 New York Sanitation Department wanted to improve its garbage collection service by organizing an efficient route schedule for trucks. One aspect of this complex problem involved was that no two trucks visited same site on same day. This led to the design of the truck route as an appropriate graph problem.
Stability of building using rectangular steel frame - works can also be analysed using graphs. Many problems of modern society involve complex systems consisting of variables that constantly change and interact. Future behaviour can be predicted using graph model. An example is the complex problem of energy use by a society. Vertices are various elements which consume energy. Edges are relations between various vertices. Some relations saves energy while others consume. The graph diagram will help in deciding the stability of networks.
In the last century, archaeologists were trying to date a large number of graves in pre-dynastic Egypt ( 4000-2800BC) from the materials found in them. Two different materials can occur in the same grave if and only if their time periods overlaps. One can construct a matrix called adjacency matrix and obtain the graph. Relations between the objects (a,…… e) are represented ( 0- no relation, 1- related) as rows and columns as shown below. Now we have a mathematical object called matrix which can be used for
Another problem was laying an under sea gas pipe line network in the gulf of Mexico, linking various gas sources. Since under sea network are expensive to construct, designers used a particular form of graph diagram called tree diagram to link sources (nodes) in the cheapest way. They were able to bring down the initial cost of 110 million US dollars to 101 million. Basic ideas of graph theory saved about 10% cost.
GT was developed in to the present form due to initiations by three independent discoveries in different fields by different people in three different periods as shown below:
|Konigsberg Problem - a riddle
||Euler in 1736
|Complex electrical network analysis
||Kirchhoff in 1847
|Enumeration of isomers in saturated hydrocarbon
||Cayley in 1857
|First book on GT
After 1936, the subject GT developed so fast that there are no fields of knowledge at present which are not influenced by it. In the present article attempt will be made to describe some of the topics in GT.
Definition of Graph
A Graph G can be defined as a finite set of vertices or nodes vi and edges or lines
ei. or G = ( vi, ei). Diagrammatic representation of graph is called graph diagram. For example, the Graph corresponding to KB problem is
G = ( A,B,C,D, a, b, c, d, e ,f, g). In KB problem Eulerian path is not possible.
Now let us see some of the terminologies in GT.
Some of the
Terminologies in Graph Theory
||Objects in the set which have mutual interactions.
||Relations between pairs of objects or lines joining the nodes.
||Graph in which there exists a path connecting any pairs of nodes.
||Graph which is not connected, splits up into connected path called its components.
Valency of vertex
||Number of edges meeting at the vertex
nodes connected by a line are called
If a line d is connected to a node D , then d and D are said to be incident with
If two distinct lines are incident with a common node, then such lines are called Adjacent lines.
A graph with p nodes and q edges are called (p,q) graph. (1,0) graph is trivial namely a single node.
||Line joining a point to it self is called loop. Loops are not allowed in a graph
||A graph in which more than one line join two points are multigraph. KB problem is a multi graph.
||A graph in which both multiple lines and loops are allowed.
Directed graph or digraph
||Graph in which lines are directed ( ordered pairs of nodes) is called digraph. A digraph has no loops or multiple lines.
||A graph in which nodes and edges are distinguished by naming them .
||Two graphs G and H are isomorphic if there exists one to one correspondence between their point- set which preserve their adjacency.
Invariant of a graph
||A number associated with a graph which has same value for all isomorphic graphs. Eg. Number of nodes and lines are invariants
||Walk of a graph is alternate sequence of nodes and lines beginning and ending with points in which each line is incident with two points immediately preceding and following it. Walk joins to nodes in a graph. There will be more than one walk possible between a pair of nodes.
||Path is the walk in which all nodes are distinct( except for initial and final point which is a closed path).
||Trail is a walk if all lines are distinct but nodes are not distinct.
||A closed walk in a graph with same initial and final points is called circuit
||G1 is a sub graph of G if all the lines and points of
G1 belongs to G also. G is said to be the super graph of
Spanning sub graph
subgraph containing all the points of the super graph.
subgraph which does not contain all the points of the
Distance in a graph
Length of a path or walk is the number of occurrence of lines in it. The girth of a graph G ,denoted by g(G) , is the length of any shortest cycle if any in the Graph.
The circumference c(G) of a graph is the length of any longest cycle in the graph.
The distance d(u,v) between two points u and v in a graph G is the length of the shortest path joining them. The diameter of G ,d(G) ,is the longest path between two points in the graph.
The sum of the degrees of points of a graph is equal to twice the number of lines. For example in KB graph sum of the degrees is 14 and there are 7 edges.
A corollary: In any graph the number of points with odd degree is even number. For example in KB graph there are 4 nodes with odd number of edges
Euler's Theorem: For a graph in a plane with number of vertices V number of edges E and number of regions F in the graph , then following formula is satisfied
V-E +F =2
Size of a complex network
Concept of distance in graph theory is useful to describe the size of a complex network. Larger the interaction smaller will be the distance and hence the size of the network. For example one can find the size of a social network by taking mutual acquaintance as the interaction and hence the edge between the nodes ( individual). Let us construct a graph diagram of film stars and fix the size of that galaxy. Nodes are film stars and edges are whether a pair of stars have acted together in any films. Nodes are Sathyan (S), Madhu (M), Nazeer (N), Mohanlal(Mh), Mammootty(Mm), Kamalhasan(K), Jayaram(Jr) and Jayan (J).
From the graph it is clear that distance between Mammootty and Sathyan is 2 and Mammootty - Jayan is also 2. Note that diameter of the constructed galaxy is 2. In two steps we can reach any pairs of stars. It is said that the acquaintance graph of whole world population is 6. A well - knit society will have very small diameter.
Four colour problem
This is another problem which took 200 years to get solved( in 1976) and a better proof came in 1997.Four colour problem says that any map drawn in a plane can be coloured with not more than four colours such that no two adjacent regions ( regions having common boundary) will have same colour. A map in a plane can be represented as a graph. Each country in the map is represented by the node and the common boundary between two countries is represented by the line joining the nodes. Thus according to FC problem, no two adjacent nodes will have same colour with maximum of four colours employed.
Seven bridges across the River Pregel flowing through the city of Konigsberg. People of K wanted to find a route to visit all parts of the city by crossing all the bridges only once. This is the famous KB problem
Euler solved the KB problem using a diagram called graph diagram. Each segment in the map is represented by Nodes and bridges by connecting line.
The Graph diagram of KB problem used by Euler. Euler found that The path envisaged by citizens of K is not possible ( this path is now called Eulerian Path) since degree of each vertex ( number of edges reaching the vertex) is odd number. Strictly speaking, this is a multigraph. See the text for details.
The city of K honoured Euler by constructing an additional bridge so that now there are exactly two vertices with odd degrees. Eulerian path is possible if one star from any of such odd vertex.
Graph diagram of KB problem with two vertices of odd degrees. Euler path is possible if one start from odd vertices A or D .
Now all the vertices are of even degrees and journey can start from any vertex.
A (5,7) graph G = (A, B, C, D, E, a, b, c, d, e ,f , g ). Valency or degrees of vertices are (3, 3, 3, 3, 2 ) in the alphabetical order.
(A,B), (B,C) are adjacent pairs of points. (A,D) are not adjacent points. They also will becom adjacent if line AD is joined. (f,b) are adjacent lines but (a,c) are not.
ABC ia a path. The path BACB is a circuit . ABCBD is a walk not path or trail. ABCAE is a trail. Details are in the text.
Two (6,9) graphs which are isomorphic. Label the right diagram and find the correspondence.
We have seen how a branch of knowledge is created unexpectedly by solving familiar problems, which may look useless like KB problem. Novel approaches to the problem is the most important like what Euler did with KB problem, If we look around we will find a number of such problems which are still waiting for their Eulers and Kirchhoffs.
For further readings:
Graph Theory by F Harry
Dr. V. P. N. Nampoori is a professor at
International School of Photonics at Cochin
University of Science and Technology