Lesson 3

A graph is called biconnected if it is connected and remains connected after the removal of any vertex. For example, any cycle is biconnected. A path or a tree with at least three vertices is not biconnected.

The set of edges of any graph can be partitioned into biconnected blocks using the following equivalence relation: \(e \sim e'\) if \(e\) and \(e'\) lie on the same cycle or are equal (the fact that this is indeed an equivalence relation needs to be proven, but it is not difficult). The resulting blocks are either bridges or maximally inclusive biconnected graphs and intersect at articulation points.

The code below finds all bridges, articulation points, and blocks of the graph shown below.

import networkx as nx

g = nx.Graph([
    (0, 1), (1, 5), (5, 4), (4, 0), (8, 9), (9, 13), (13, 12),
    (8, 5), (14, 15), (11, 6), (11, 7), (6, 7), (2, 7), (2, 3),
    (3, 7), (2, 6)
])

print('Bridges:', *nx.bridges(g))
print('Cut points:', *nx.articulation_points(g))
print('Biconnected components:', *nx.biconnected_components(g))

Bridges: (5, 8) (8, 9) (9, 13) (13, 12) (14, 15)
Cut points: 13 9 8 5
Biconnected components: {12, 13} {9, 13} {8, 9} {8, 5}
    {0, 1, 4, 5} {14, 15} {2, 3, 6, 7, 11}

Once again, note that blocks do not intersect each other via edges, but may intersect via vertices.