in Graph

The impact of bridges in a graph

In graph theory, a bridge is an edge whose removal leads to the disconnection of the network. It is usually found in undirected graphs and can also be viewed within the context of disconnected undirected graphs. In these disconnected undirected graphs, removing a bridge leads to a further separation of the subgraphs. Let’s explore some examples below. 

Bridge in an undirected connected graph:

The below graph is undirected but it is connected. There are 9 nodes and 10 edges in this graph. You can determine that one edge is in red and the rest are in grey/black. The edge in red is the bridge and removal will lead to a disconnection of node [L] from the rest of the graph. Assuming all of these nodes were train stations and the edges are London tube lines.  A rail track maintenance work, shortage of control room staff or a broken train on the track are some of the reasons that can cause a train line that connects node [H] to node[L] to become disconnected or temporarily removed from the train network or graph. When this occurs, people living close to the station [L] will become stranded or short of transportation options. This is a connected graph because the disconnected unit is not a sub-graph on its own but a single node stranded and possibly struggling in the network.  

Bridge in an undirected dis-connected graph:

From the example graph below, one can identify two graphs which are disconnected in nature. There is no bridge in the first graph that are 12 nodes and 15 edges. The second graph is made of two bridges [Q, P] and [P, R]. If this was a transport network, a disruption to the train line that travels between [Q, P, R] can disconnect two or all three of the nodes. This is an example of a bridge in an undirected disconnected graph. 

Core attributes of bridges in a graph:

  1. The removal of a bridge increases the number of connected components of the graph: This is one of the core features of a bridge in a graph. When a bridge in the form of an edge is removed it increases the cluster of connected nodes or components by +1. From the example graph below, there is only one connected component or cluster of nodes. The removal of one of the edges will lead to two separate components. 
  1. A bridge does not belong to a cycle: A cycle in graph theory is a network where the only repeated vertices are the first and last ones respectively. The nodes are expected to be connected in a closed chain. Chains are found in the networkx Python library using the networkx.chain_decomposition() function.

In practice, the number of bridges a graph can contain will be -1 of its total number of nodes. Simply stating that n-1 bridges can exist in a given graph. If an extra edge is added to the graph it becomes a cycle and when all bridges in a graph are bridges the network is referred to as a forest. 

Here is a code implementation of bridge identification in Java inspired by Aakash Asija

// Finding bridges in an undirected graph
import java.io.*;
import java.util.*;
import java.util.LinkedList;

// This class expresses an undirected graph using adjacency list
// representation
class Graph
{
	private int V; // No. of vertices

	// Here is an array of lists for Adjacency List Representation
	private LinkedList<Integer> adj[];
	int time = 0;
	static final int NIL = -1;

	//Class constructor
	Graph(int v)
	{
		V = v;
		adj = new LinkedList[v];
		for (int i=0; i<v; ++i)
			adj[i] = new LinkedList();
	}

	// Here is a function to add an edge into the graph
	void addEdge(int v, int w)
	{
		adj[v].add(w); // Adding w to v's list.
		adj[w].add(v); //Adding v to w's list
	}

	// A recursive function that finds and prints bridges
	// Mainly using DFS traversal
	void bridgeUtil(int u, boolean visited[], int disc[],
					int low[], int parent[])
	{

		// Acknowledge the current node as visited
		visited[u] = true;

		// Commence discovery time and low value
		disc[u] = low[u] = ++time;

		// Visit all vertices adjacent to this
		Iterator<Integer> i = adj[u].iterator();
		while (i.hasNext())
		{
			int v = i.next(); // the v is current adjacent of u

			// If v is not visited yet, then make it a child
			// of u in DFS tree and recur for it.
			// If v is not visited yet, then recur for it as well
			if (!visited[v])
			{
				parent[v] = u;
				bridgeUtil(v, visited, disc, low, parent);

				// Check if the subtree rooted with v has a
				// connection to one of the ancestors of u
				low[u] = Math.min(low[u], low[v]);

				// If the lowest vertex reachable from subtree
				// under v is below u in DFS tree, then u-v is
				// a bridge
				if (low[v] > disc[u])
					System.out.println(u+" "+v);
			}

			// Update low value of u for parent function calls.
			else if (v != parent[u])
				low[u] = Math.min(low[u], disc[v]);
		}
	}


	// A DFS based function to find all bridges. It uses recursive
	// function bridgeUtil()
	void bridge()
	{
		// Acknowledge all the vertices as not visited
		boolean visited[] = new boolean[V];
		int disc[] = new int[V];
		int low[] = new int[V];
		int parent[] = new int[V];


		// Initialize parent and visited, and ap(articulation point)
		// arrays
		for (int i = 0; i < V; i++)
		{
			parent[i] = NIL;
			visited[i] = false;
		}

		// Request for the recursive helper function to find Bridges
		// in DFS tree rooted with vertex 'i'
		for (int i = 0; i < V; i++)
			if (visited[i] == false)
				bridgeUtil(i, visited, disc, low, parent);
	}

	public static void main(String args[])
	{
		// The creation of the graphs
		System.out.println("Highlighting the bridges in first graph ");
		Graph g1 = new Graph(7);
		g1.addEdge(1, 0);
		g1.addEdge(0, 2);
		g1.addEdge(2, 1);
		g1.addEdge(0, 3);
		g1.addEdge(3, 4);
        g1.addEdge(4, 5);
        g1.addEdge(5, 6);
		g1.bridge();
		System.out.println();

		System.out.println("Introducing the bridges in Second graph");
		Graph g2 = new Graph(6);
		g2.addEdge(0, 1);
		g2.addEdge(1, 2);
		g2.addEdge(2, 3);
        g2.addEdge(3, 4);
        g2.addEdge(4, 5);
		g2.bridge();
		System.out.println();

		System.out.println("Generating the bridges in Third graph ");
		Graph g3 = new Graph(9);
		g3.addEdge(0, 1);
		g3.addEdge(1, 2);
		g3.addEdge(2, 0);
		g3.addEdge(1, 3);
		g3.addEdge(1, 4);
		g3.addEdge(1, 6);
		g3.addEdge(3, 5);
		g3.addEdge(4, 5);
        g3.addEdge(6, 1);
        g3.addEdge(7, 6);
		g3.bridge();
	}
}


// Here are the outputs 


Highlighting the bridges in first graph 
5 6
4 5
3 4
0 3

Introducing the bridges in Second graph
4 5
3 4
2 3
1 2
0 1

Generating the bridges in Third graph 
6 7
1 6

Write a Comment

Comment