Graphs and Applications

Many real-world problems can be solved using graph algorithms. Graphs are useful in modeling and solving real-world problems. For example, the problem to find the least number of flights between two cities can be modeled using a graph, where the vertices represent cities and the edges represent the flights between two adjacent cities, as shown in Figure below. The problem of finding the minimal number of connecting flights
between two cities is reduced to finding a shortest path between two vertices in a graph.

The study of graph problems is known as graph theory. Graph theory was founded by Leonhard Euler in 1736, when he introduced graph terminology to solve the famous Seven Bridges of Königsberg problem. The city of Königsberg, Prussia (now Kaliningrad, Russia), was divided by the Pregel River. There were two islands on the river. The city and islands were connected by seven bridges, as shown in Figure below (a). The question is, can one take a walk, cross each bridge exactly once, and return to the starting point? Euler proved that it is not possible.

To establish a proof, Euler first abstracted the Königsberg city map by eliminating all streets, producing the sketch shown in Figure above (a). Next, he replaced each land mass with a dot, called a vertex or a node, and each bridge with a line, called an edge, as shown in Figure above (b). This structure with vertices and edges is called a graph.

Looking at the graph, we ask whether there is a path starting from any vertex, traversing all edges exactly once, and returning to the starting vertex. Euler proved that for such a path to exist, each vertex must have an even number of edges. Therefore, the Seven Bridges of Königsberg problem has no solution.

Graph problems are often solved using algorithms. Graph algorithms have many applications in various areas, such as in computer science, mathematics, biology, engineering, economics, genetics, and social sciences.

Basic Graph Terminologies

A graph consists of vertices, and edges that connect the vertices. This chapter does not assume that you have any prior knowledge of graph theory or discrete mathematics. We use plain and simple terms to define graphs.

What is a graph? A graph is a mathematical structure that represents relationships among entities in the real world. For example, the graph in Figure above represents the flights among cities, and the graph in Figure below (b) represents the bridges among land masses.

A graph consists of a nonempty set of vertices (also known as nodes or points), and a set of edges that connect the vertices. For convenience, we define a graph as G = (V, E), where V represents a set of vertices and E represents a set of edges. For example, V and E for the graph in Figure below are as follows:

V = {"Seattle", "San Francisco", "Los Angeles",
"Denver", "Kansas City", "Chicago", "Boston", "New York",
"Atlanta", "Miami", "Dallas", "Houston"};

E = {{"Seattle", "San Francisco"},{"Seattle", "Chicago"},
{"Seattle", "Denver"}, {"San Francisco", "Denver"},
...
};

A graph may be directed or undirected. In a directed graph, each edge has a direction, which indicates that you can move from one vertex to the other through the edge. You can model parent/child relationships using a directed graph, where an edge from vertex A to B indicates that A is a parent of B. Figure below (a) shows a directed graph.

In an undirected graph, you can move in both directions between vertices. The graph in Figure below is undirected.

Edges may be weighted or unweighted. For example, you can assign a weight for each edge in the graph in Figure above to indicate the flight time between the two cities.

Two vertices in a graph are said to be adjacent if they are connected by the same edge. Similarly, two edges are said to be adjacent if they are connected to the same vertex. An edge in a graph that joins two vertices is said to be incident to both vertices. The degree of a vertex is the number of edges incident to it.

Two vertices are called neighbors if they are adjacent. Similarly, two edges are called neighbors if they are adjacent.

A loop is an edge that links a vertex to itself. If two vertices are connected by two or more edges, these edges are called parallel edges. A simple graph is one that has doesn’t have any loops or parallel edges. In a complete graph, every two pairs of vertices are connected, as shown in Figure below (b).

A graph is connected if there exists a path between any two vertices in the graph. A subgraph of a graph G is a graph whose vertex set is a subset of that of G and whose edge set is a subset of that of G. For example, the graph in Figure above (c) is a subgraph of the graph in Figure above (b).

Assume that the graph is connected and undirected. A cycle is a closed path that starts from a vertex and ends at the same vertex. A connected graph is a tree if it does not have cycles. A spanning tree of a graph G is a connected subgraph of G and the subgraph is a tree that contains all vertices in G.