`bctree`

Block-cut tree of an undirected graph.

Category: Mathematics > Graph and Network Algorithms

Syntax

T = bctree(G)

Returns the block-cut tree of G.

Description

A block is a maximal piece of the graph that stays connected if any single node is removed. A cut vertex is a node whose removal disconnects the graph. Gluing blocks along their cut vertices gives a tree (a forest if G is disconnected), which is the block-cut tree.

The tree shows at a glance where a network is fragile: every cut vertex is a single point of failure.

Input arguments

G: An undirected graph.

Output arguments

T: A graph with one node for each biconnected component (block) and one for each cut vertex. Each cut vertex is linked to the blocks that contain it.
map: Optional second output relating the nodes of G to nodes of T.

Example

Triangle with a chain

G = graph([1 2 3 3 4 5], [2 3 1 4 5 6]);
T = bctree(G);
fprintf('%d nodes, %d edges\n', numnodes(T), numedges(T))

Output

7 nodes, 6 edges

bctree