Graph Theory

Graphs are mathematical structures that are used to model pairwise relationships. Graph theory provides a tool to quantify these relationships in a dynamic system. In other words, graphs are ways to represent a network or a collection of interconnected objects. Graph theory is mostly applied in operations research and social sciences. Its history dates back to the 18th century when the Swiss mathematician Leonhard Euler solved the Königsberg bridge problem (Figure 6.1), which served as a precursor to graph theory. The city of Königsberg in Russia was set on both sides of the Pregel river and included two large islands, namely, Kneiphof and Lomse, which were connected by seven bridges. The problem was to devise a walk through the city that would cross each of these bridges only once. Euler drew out the first known visual representation of a modern graph for the city. It is represented (abstractly) by a set of points known as vertices or nodes, connected by a set...