VTU eNotes On Graph Theory & Combinatronics (Computer Science)
About this eBook
social science, As will become evident after reading this chapter graphs are excellent modeling tools, we now look at several classic problems. We begin with the bridges of Konigsberg. This problem has a historical significance, as it was the first problem to be stated and then solved using what is now known as graph theory. Leonard euler fathered graph theory in 1973 when his general solution to such problems was published euler not only solved this particular problem but more importantly introduced the terminology for graph theory 1.THE KONIGSBERG BRIDGE PROBLEM Euler 1707-- 1782 became the father of graph theory as well as topology when in 1736 he settled a famous unsolved problem of his day called the Konigsberg bridge problem. The city of Konigsberg was located on the Pregel river in Prussia, the city occupied two island plus areas on both banks. These region were linked by seven bridges as shown in fig 1.1 . The problem was to begin at any of the four land areas, walk across each bridge exactly once and return to the starting point one can easily try to solve this problem empirically but all attempts must be unsuccessful, for the tremendous contribution of Euler in this case was negative. In proving that the problem is unsolvable, Euler replaced each land area by a point and each bridge by a line joining the corresponding points these by producing a graph this graph is shown in fig 1.2 where the points are labeled to correspond to the four land areas of fig 1.1 showing that the problem is unsolvable is equivalent to showing that the graph of fig 1.2 cannot be traversed in a certain way. In proving that the problem is unsolvable, Euler replaced each land area by a point and each bridge by a line joining the corresponding points these by producing a graph this graph is shown in fig 1.2 where the points are labeled to correspond to the four land areas of fig 1.1 showing that the problem is unsolvable is equivalent to showing that the graph of fig 1.2 cannot be traversed in a certain way.
Figure1.1 A park in Konigsberg 1736
Figure1.2 The Graph of the Konigsberg bridge problem Rather than treating this specific situation, Euler generalized the problem and developed a criterion for a given graph to be so traversable namely that it is connected and every point is incident with an even number of lines. While the graph in fig 1.2 is connected, not every point incident with an even number of lines. 2.ELECTRIC NETWORKS Kirchhoffs developed the theory of trees in 1847 in order to solve the system of simultaneous linear equations linear equations which gives the current in each branch and around each circuit of an electric network.. Although a physicist he thought like a mathematician when he abstracted an electric network with its resistances, condensers, inductances, etc, and replaced it by its corresponding combinatorial structure consisting only of points and lines without any indication of the type of electrical element represented by individual lines. Thus, in effect, Kirchhoff replaced each electrical network by its underlying graph and showed that it is not necessary to consider every cycle in the graph of an electric network separating in order to solve the system of equation. Instead, he pointed out by a simple but powerful construction, which has since became std procedure, that the independent cycles of a graph determined by any of its 4