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:
- 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.
- 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.