`biconncomp`

Biconnected components (blocks) of an undirected graph.

Category: Mathematics > Graph and Network Algorithms

Syntax

bins = biconncomp(G)

Labels each edge with the block it belongs to.

[bins, cut] = biconncomp(G)

Also returns the cut vertices.

Description

A biconnected component is a maximal set of edges in which any two edges lie on a common cycle, so the component survives the removal of any one node. Components can share a cut vertex but never an edge, which is why the labels belong to edges and not to nodes.

An edge that is not on any cycle, such as a bridge, forms a block by itself.

Input arguments

G: An undirected graph.

Output arguments

bins: One integer per edge, in the order of G.Edges. Edges with the same label lie in the same block.
cut: Indices of the cut vertices (articulation points).

Example

Blocks of a triangle with a tail

G = graph([1 2 3 3 4 5], [2 3 1 4 5 6]);
[bins, cut] = biconncomp(G);
fprintf('%d blocks\n', max(bins))
disp(cut)

Output

4 blocks
     3     4     5

biconncomp