Graph

We can concisely depict many real-life problems as collections of objects and links between them. Such representations are known as graphs. A graph can be considered as a set of objects, usually named nodes or vertices, and links (edges) that connect these objects with each other.

To fully understand the importance of graphs, it is sufficient to mention that there exists a branch of theoretical computer science known as Graph Theory. Furthermore, this is undoubtedly one of the fields with the largest number of unsolved problems, and scientists from all over the world work on them from day to day. Here, however, we will focus on the very basics of this theory — only on the elements necessary to understand the algorithms that use this data structure.

A brief history of graphs

If you want to understand today, you have to search yesterday, they say. Let's learn how graphs first appeared. The history of graph theory can be traced back specifically to 1735, when Swiss mathematician Leonhard Euler solved the Königsberg bridge problem.

The Königsberg bridge problem was an old puzzle concerning the possibility of finding a path over each one of the seven bridges that span a forked river flowing past an island. But (and here's the tricky part) without crossing any bridge twice. Euler argued that no such path exists. His proof involved only references to the physical arrangement of the bridges, but essentially he proved the first theorem in graph theory.

An important graph problem

Now, let's take a look at one of the most discussed problems in modern graph theory — the map-coloring problem. The task can be stated as follows: we need to assign a color to every country, taking an obvious restriction into account — two neighbors should have different colors. Consider the following example:

Here is a partial map of Europe. To get rid of the unnecessary details of a map, we represent each country as a node and connect two countries if they are neighbors. This results in the following graph:

The figure on the left corresponds to a map with borders represented as links between countries, and the figure on the right is a graph where we've substituted each country for a node. Thus, we reduce the problem of coloring a political map to the problem of coloring the nodes of a graph. Although the example above is quite simple, such representation would be indispensable for larger maps: it allows us not only to keep the important details, but also to automate the solution to this problem.

More applications

Unsurprisingly, graphs come in handy in many areas other than theoretical computer science. Assume that you need to drive from one city to another. Chances are, you'd probably rely on services like Google Maps or MapQuest. We all use them, but have you ever thought about how they work under the hood? A possible way is to represent the map as a graph with nodes corresponding to cities and edges showing the roads. Then, in terms of graphs, our question is: what is the shortest path between the start node and the destination node?

Map coloring and finding the shortest path are not the only problems where graphs appear useful. For instance, we could represent the World Wide Web as a graph, with nodes symbolizing the sites and edges as links between these sites. In social networks, you can view people as nodes, and a link between two people meaning that one of them follows the other. In other words, a graph is a convenient structure, suitable for modeling various real-life problems.

Formal definition

Using formal language is essential when it comes to working with graphs conveniently, storing them on a computer, or describing algorithms for graph processing. Formally, a graph $G$ is a pair of two sets: $G = (V, E)$. Here, $V$ is a set of nodes and $E$ is a set of edges. Each edge is a pair of nodes connected by a link. Consider the following three examples:

Here we have three graphs. The first graph $G_1$ consists of three nodes and has no edges. So,

$G_1 = (V_1, E_1),\ V_1 = \{0, 1, 2\},\ E_1= \emptyset$

The second graph $G_2$ is the same as $G_1$ but contains two edges:

$G_2 = (V_2, E_2),\ V_2 = \{0, 1, 2\},\ E_2 = \{\{0, 1\}, \{0, 2\}\}$

The third graph $G_3$ consists of four nodes and four edges:

$G_3 = (V_3, E_3),\ V_3 = \{0, 1, 2, 3\},\ E_3 = \{\{0, 1\}, \{0, 2\}, \{1, 2\}, \{1, 3\}\}$

The nodes in the graphs above are labeled as numbers, but labels might actually be of different types. See the following examples:

The graph $G_4 = (V_4, E_4)$ consists of four nodes with labels $V_4 = \{A, B, C, D\}$ and edges $E_4 = \{\{A, B\}, \{A, C\}, \{B, C\}, \{B, D\}\}$. The graph $G_5 = (V_5, E_5)$ represents a group of people, with edges showing acquaintance:

$V_5 = \{Bob, Alice, Tom, Mark\},$

$\ E_5 = \{\{Bob, Alice\}, \{Bob, Tom\}, \{Alice, Tom\}, \{Tom, Mark\}\}.$

Depending on a particular problem you need to solve, different types of labels might be convenient.

Directed graphs

Up until this moment, we've talked only about graphs where edges don't have any direction. For example, consider the edge $\{0, 1\}$ of $G_2$ that connects the nodes $0$ and $1$. If we swap the nodes, it won't change anything: the edge $\{1, 0\}$ still connects the same nodes. Such graphs, where the order of nodes is not important, are called undirected graphs. A political map is a structure that we can naturally reduce to an undirected graph. If one country is a neighbor of another, the direction of the edge showing this relation is not important.

However, in some other cases, undirected graphs don't suffice. Assume that we want to model a social network as a graph. We can represent people as nodes and put an edge between two people if one of them follows the other.

In this case, the direction is important. If a user $x$ follows $y$, it doesn't mean that $y$ follows $x$. To model this and similar situations, directed graphs suit much better. You can see an example of a directed graph in the figure above:

The given graph consists of four nodes and four directed edges:

$V = \{0, 1, 2, 3\},\ E = \{(0, 1), (0, 2), (1, 2), (3, 2)\}$

To show that an edge is directed, we use round brackets instead of curly ones.

As mentioned before, different types of graphs are better suited for modeling different problems. Depending on the task you need to solve, you can choose either directed or undirected graphs.

Summary

A graph is a convenient structure that we can use to model many real-life objects and processes. In this topic, we've considered several examples where graphs might be useful and learned how to describe their structure. Formally, a graph is a set of nodes and edges that connect these nodes with each other. If the order of nodes is not important, we say that the graph is undirected. Otherwise, we call it directed.

Yet, in order to solve real problems efficiently, you need to know more about graphs. In the following topics, we will learn some terminology used to describe graphs, consider how to store them on a computer, and then learn some efficient algorithms for their processing.