Connectivity in graphs: core concepts

Connectivity in graphs

• Exploring graph connectivity.

• Connected components.

• Finding connected components algorithmically.

In a previous topic we had a glimpse on graph connectivity, its basic definition. In this topic we are going to learn about it in more detail as well as get acquainted with connected components, which are very closely related to the concept of connectivity and then end up with taking a look at the algorithms of finding these components. Let us start with a recap on graph connectivity.

What is graph connectivity?

Connected Graph: A graph where there is a path between every pair of vertices.

For example, consider a simple graph with three vertices $A$, $B$, $C$ and three edges $AB$, $BC$, $AC$.

Disconnected Graph: A graph that is not connected. There are at least two vertices between which no path exists.

For example, imagine a graph with four vertices $A$, $B$, $C$, $D$ and two edges $AB$, $CD$.

What are degrees of connectivity?

A k-connected graph (also known as a k-vertex-connected graph) is a graph that remains connected whenever fewer than $k$ vertices are removed. The minimum number of vertices that need to be removed to disconnect the graph is called the vertex connectivity of the graph.

An example of a connected graph with three vertices $A$, $B$, $C$ and three edges $AB$, $BC$, $AC$.

This graph is 2-connected, because we need to remove at least two vertices to disconnect this graph.

Similarly, a k-edge-connected graph is a graph that remains connected whenever fewer than $k$ edges are removed. The minimum number of edges that we need to be remove in order to disconnect the graph is called the edge connectivity of the graph.

With a basic example of three vertices $A$, $B$, $C$ and two edges $AB$, $BC$ we can see that this graph is 1-edge-connected.

By removing either of the edges, the graph becomes disconnected.

The concepts of k-connected graphs and k-edge-connected graphs are especially important in network reliability and resilience. By grasping these concepts we have a better understanding of the possibilities of how resilient these graphs may be before disconnecting them. But there are still more things for us to learn in this lesson, so let us move on.

What is a subgraph?

Vertex-Induced Subgraph: A subgraph that includes some of the vertices from the original graph and all the edges connecting these vertices.

An example of a vertex-induced subgraph would be the following (original graph on the left and vertex-induced graph on the right):

The graph on the right above features some of the vertices from the original graph and includes all the edges, connecting these vertices.

Edge-Induced Subgraph: A subgraph that includes all the vertices of the original graph, but with certain edges removed.

The graph on the right above features all the vertices of the original graph, but with certain edges.

What is a connected component?

Strongly Connected Component (Directed Graph): A subset of the graph in which there is a directed path from any vertex to any other vertex in the subset.

Weakly Connected Component (Directed Graph): A subset of the graph in which there is a path from any vertex to any other vertex in the subset, ignoring the direction of the edges.

The concept of connected components is useful in many applications. For instance, in social network analysis, each connected component could represent a community. In biology, connected components of a genetic similarity graph could represent species. Connected components of a graph can give us important insights about both structure and properties of the system that the graph represents.

What algorithms help us explore graph connectivity?

Now that we have gained some knowledge in various parts of graph connectivity, it is time to take a look at some algorithms, that help us explore it. As we know, graphs can have different properties (and we sure did cover them in this lesson), which is why there are a number of algorithms:

1. Depth-First Search (DFS): a common algorithm for traversing or searching through a graph. Starting at a root node, the algorithm explores as far as possible along each branch before falling back. DFS can be used to determine whether a graph is connected by checking if the algorithm visits all nodes in the graph. If that is not the case, then the graph is disconnected.

2. Breadth-First Search (BFS): another common algorithm for traversing or searching through a graph. It starts at the root node and explores all the neighboring nodes at the present depth before moving on to nodes at the next depth level. Like DFS, BFS can be used to determine whether a graph is connected by checking if the algorithm visits all nodes in the graph.

3. Tarjan’s Algorithm: this is a DFS-based algorithm that can be used to find the strongly connected components in a directed graph. The algorithm keeps track of the nodes visited during the DFS and uses a stack to find the strongly connected components.

4. Kosaraju's Algorithm: this algorithm finds all the strongly connected components in a directed graph. It involves running DFS twice, the second time on the transpose of the graph (i.e., the graph with all edge directions reversed).

5. Floyd-Warshall Algorithm: This algorithm is used to find the shortest paths between all pairs of nodes in a weighted graph. It can also be used to determine the connectivity of a graph by checking if the shortest path between any pair of nodes exists.

By using these algorithms and methods, we can explore different aspects of graph connectivity, such as identifying connected components, finding bridges and understanding the overall structure of the network, in general, represented by the graph.

Conclusion

We took a look at a number of concepts during this lesson, so now it is time to recap of what we learned:

• Graphs can be either connected or disconnected.

• More complex graphs have degrees of connectivity: vertex connectivity and edge connectivity.

• Subgraphs and subsets. A subgraph features both vertices and edges from the original graph, while the latter features only the vertices.

• A connected component is a subset is which a path from any vertex to any vertex exists.

• Connected components may be strongly connected or weakly connected.

• Algorithms help us identifying and understanding the graph's structure more efficiently.