ABSTRACT
In the past few decades, graph theory has been a powerful analytical tool for understanding and solving various problems in operations research (OR). The study of graphs (or networks) traces back to the solution of the Ko¨nigsberg bridge problem by Euler in 1735. In Ko¨nigsberg, the river Preger flows through the town dividing it into four land areas as shown in Figure 11.1a. These land areas are connected by seven different bridges. The Ko¨nigsberg bridge problem is to find whether it is possible to traverse through the city on a route that crosses each bridge exactly once, and return to the starting point. Euler formulated the problem using a graph theoretical representation and proved that the traversal is not possible. He represented each land area as a vertex (or node) and each bridge as an edge between two nodes (land areas), as shown in Figure 11.1b. Then, he posed the question as whether there exists a path such that it passes every edge exactly once and ends at the start node. This path was later termed an Eulerian circuit. Euler proved that for a graph to have an Eulerian circuit, all the nodes in the graph need to have an even degree.
