Connectivity in graphs: advanced concepts

For now, we've already learned what a graph is and discussed some basic terminology. However, there is one important concept that has not been covered yet. It is widely used in routing, social network analysis, fraud investigation, and many more spheres, not even talking about the fact that various algorithms are based on it. Are you already eager to learn, which concept hides behind this description? It is connectivity! In this topic, we will discuss it in detail: first, for undirected graphs and then for directed ones.

Connectivity in undirected graphs

In order to fully understand which graphs are called connected, we need to learn about some additional terms: connected nodes and connected components. In an undirected graph, two nodes are connected if there is a path between these nodes. For example, the nodes $1$ and $3$ of $G_1$ are connected since there is a path $1-2-3$:

An example of nodes that are not connected is $3$ and $6$: as you can see, there is no path that's connecting them.

Moving on, a connected component is such a subgraph of a graph that:

• each pair of nodes in this subgraph is connected;
• no other node can be added to this component without breaking its property of being connected. It means that we should maximize the number of nodes in a component if it is possible to maintain the nodes connected.

For example, if it wasn't for the second rule, we could say that in the graph above vertices $0$, $1$ and $2$ form a connected component. However, as we maximize the possible number of the nodes in a component, and there is node $3$, that can be added with keeping it connected, these vertices are part of a bigger component $0$, $1$, $2$ and $3$.

If you look at the graph above once more, you can see that in reality, it consists of two connected components – $\{0, 1, 2, 3\}$ and $\{4, 5, 6, 7\}$.

Now, as you are familiar with all the crucial terms, it's time to discuss the connectivity of a graph itself. A graph $G$ is called connected if it consists only of one connected component. In other words, in this graph, there is a path between each pair of nodes. As you can see, in $G_1$ there are two connected components, which is why it doesn't fit this definition. Therefore, it's an example of a disconnected graph.

Mind that a connected component may even consist of one vertex. For instance, in the following graph you can see 3 connected components: $\{1, 2, 3\}$, $\{4\}$ and $\{5\}$.

Why do we need connected components? Imagine, that you've created your very own social network and want to recommend similar things (posts, pictures, articles) to groups of friends. As being a friend is mutual, you may use the undirected graph to show the relations between the users. After that, you need to find groups of friends somehow. And these groups of friends are none other than the connected components! Cool, isn't it?

Directed graphs: weak connectivity

As for directed graphs, the concept of connectivity is a bit more complex than for undirected ones, as there are two different types of connectivity: weak and strong.

Let's start with the first one. A directed graph is weakly connected if there is an undirected path between each pair of nodes in the graph. In other words, if we remove the direction of each edge of the directed graph and end up with a connected undirected graph, then the initially directed graph is weakly connected. Let's consider the following example:

If we remove the direction of each edge of the graph $G_1$, we will get a connected undirected graph $G_2$ (convince yourself that it is connected!). Therefore, $G_1$ is weakly connected.

Directed graphs: strong connectivity

As for the second type of connectivity, let's start with the definition of a strongly connected component (SCC). It is such a subgraph of a directed graph that:

• there is a directed path between each pair of nodes in this subgraph;
• no other nodes or edges can be added to this subgraph without breaking its property of being strongly connected. Just like in the case of a connected component of the undirected graph, it means that you put as many vertices as possible to an SCC, while it stays connected.

The graph $G_1$, for example, consists of two strongly connected components. The blue nodes $0$, $3$ and $4$ belong to the first component, while the red nodes $1$, $2$, and $5$ represent the second one.

Moving on to graph connectivity, a directed graph is called strongly connected if it consists of only one SCC. In other words, it is such a graph that there is a directed path between each pair of nodes in it. It means that you can go from a certain node to any other one of the graph while keeping the edges directed. Mind that the vertices should be connected in both directions: there has to be a path from vertex $A$ to vertex $B$, as well as a path from vertex $B$ to vertex $A$.

According to this definition, $G_1$ is not strongly connected as some nodes are not connected by a path. For instance, there is no way you can go to vertex $3$ from vertex $2$. As for the example of a strongly connected directed graph, it may look like this:

Note: by definition of a strongly connected component, a subgraph containing only one node can also be a strongly connected component in a directed graph!

Note: a strongly connected graph is also weakly connected.

Last but not least, why would we want to know about the strongly connected components? Well, let's get back to our example with your own social network. Previously, we wanted to recommend different information to the user and used connected components for it. However, sometimes the relation between users is not mutual, as is the case with friendship. For example, one person may follow another, but not be followed back. In such a situation, the solution is to use a directed graph and find the SCCs to get the needed information. For instance, if a user follows someone from the SCC, you may recommend they follow other people from the same SCC.

Condensation

Now it's time to learn the last term of this topic – condensation. It is a directed acyclic graph, that is created by merging the nodes of each strongly connected component into one and connecting them by the edges. For example, a condensation of $G_1$ looks like this:

You may wonder, where the edge between the blue and red components came from, and how we figured out its direction. Well, firstly, in the graph $G_1$ the blue and red components are connected with edges $0-1$ and $4-1$. So, you should show this connection in condensation as well, which is why there is this edge between the components. As for the direction of an edge, you can see that the starting vertices of the mentioned edges belong to the blue component, and the destinations – to the red one. Therefore, in a condensation, the edge also goes from the blue components to the red ones.

Graph condensation makes it easier to analyze the graph connectivity on big graphs. Additionally, it helps to use less memory for storing the information if it is only important for us to know about the components and the way they are connected. Additionally, it may be used in transportation problems. For instance, you may condense a transportation network graph, that shows roads between various destinations, to identify the most critical routes.

A more complicated case

Let's look at one more example of a directed graph and find a condensation for it.

The graph is the following:

Before reading the next paragraph, as a practice try to answer the following questions yourself: is this graph connected? If so, is it connected weakly or strongly?

Well, this graph consists of 5 SCCs: $\{1, 2, 3, 4\}$, $\{5\}$, $\{6\}$, $\{7\}$ and $\{8\}$. Let's call them $A$, $B$, $C$, $D$ and $E$ respectively. Therefore, it is definitely not strongly connected. However, if you convert it into an undirected graph, you will see that it is connected, resulting in the fact that the initial graph is weakly connected.

Now, it's time to create a condensation. As has already been mentioned, there are 5 SCCs in the graph. Moreover, component $A$ is connected to all of the others, while components $B$, $C$, $D$ and $E$ are not connected between themselves. The edges, that connect the component $A$ to the other ones start in the vertices, that belong to these components, and have destinations in the components $B$, $C$, $D$ and $E$. Therefore, in the condensation, the edges go from the component $A$ to all of the other components, and not in the opposite direction. The final condensation looks like this:

Conclusion

In this topic, we've learned about connectivity in undirected and directed graphs. Let's go through the main points once again:

• If there is a path between two nodes, they are called connected.
• A connected component is a subgraph, where each pair of nodes is connected and there is no way to add any more nodes to it while preserving connectivity.
• A graph is called connected if each pair of its nodes is connected. Otherwise, it is called disconnected.
• Directed graphs, unlike undirected ones, can be weakly or strongly connected.
• A directed graph is weakly connected if after turning the edges into undirected ones you get a connected undirected graph.
• A directed graph is strongly connected if even while keeping the directions of the edges each pair of its nodes is connected. Nodes should be connected in both directions.
• A strongly connected graph is also weakly connected.
• A connected component or SCC can consist even of 1 node.