Introduction

Graphs are everywhere; when you get in your car and drive around using a GPS, you perhaps do not even realize that it is solving a graph problem to get you from point A to point B over the shortest path or in the shortest time.

The origins of graph theory reach the 18th century when Leonard Euler proposed the solution to the Königsberg bridge problem. (To read more on the topic, you can refer to http://www2.gsu.edu/~matgtc/origin%20of%20graph%20theory.pdf.) From that point onward, some of the problems that were deemed unsolvable could be solved; the Internet (or even your local network) can be viewed and analyzed as a graph, scheduling problems that airlines solve can be modeled as a graph, or (as we will see) a social network is much easier to handle if we realize that it is a graph.

Graphs are structures consisting of nodes (sometimes called vertices) and edges (sometimes called arcs or lines) that connect two nodes:

The preceding example shows the simplest network possible,...