bctree

Block-cut tree graph

Syntax

tree = bctree(G)

[tree,ind] = bctree(G)

Description

tree = bctree(G) returns the block-cut tree of graph G, such that each node in tree represents either a biconnected component or cut vertex of G. A node representing a cut vertex is connected to all nodes representing biconnected components that contain that cut vertex.

[tree,ind] = bctree(G) also returns a vector of numeric node indices mapping the nodes of G into the nodes of tree.

Examples

Compute Block-Cut Tree of Graph

Compute the block-cut tree of a graph, view the resulting node properties, and then highlight the cut vertices in the graph plot.

Create and plot a graph.

s = [1 1 2 2 3 4 4 5 6 6 7 7 8];
t = [2 3 3 4 4 5 7 6 7 10 8 9 9];
G = graph(s,t);
p = plot(G);

Compute the block-cut tree of the graph and view the node properties.

tree = bctree(G);
tree.Nodes

ans=7×3 table
    IsComponent    ComponentIndex    CutVertexIndex
    ___________    ______________    ______________

       true              1                 0       
       true              2                 0       
       true              3                 0       
       true              4                 0       
       false             0                 4       
       false             0                 6       
       false             0                 7       

Plot the block-cut tree using red diamond markers for the nodes that represent cut vertices. The circular nodes represent the biconnected components in the original graph.

p2 = plot(tree,'MarkerSize',9);
highlight(p2,5:7,'Marker','d','NodeColor','r')

Return Node Indices for Block-Cut Tree

Create and plot a graph.

s = [1 1 2 2 3 4 4 5 6 6 7 7 8];
t = [2 3 3 4 4 5 7 6 7 10 8 9 9];
G = graph(s,t);
p = plot(G);

Compute the block-cut tree tr of the graph, and specify a second output ix to return the node indices.

[tr,ix] = bctree(G)

tr = 
  graph with properties:

    Edges: [6x1 table]
    Nodes: [7x3 table]

ix = 1×10

     4     4     4     5     3     6     7     1     1     2

Each index ix(j) indicates the node in the block-cut tree that represents node j in the input graph. For example, node 4 in tr represents a component in G that contains nodes 1, 2, and 3, so the first three entries in ix are all 4.

Input Arguments

G — Input graph

graph object

Input graph, specified as a graph object. Use graph to create an undirected graph object.

Example: G = graph(1,2)

Output Arguments

tree — Block-cut tree graph

graph object

Block-cut tree graph, returned as a graph object. tree contains a node for each cut vertex in G and a node for each biconnected component in G. The nodes table tree.Nodes contains additional node attributes to describe what each node represents:

• tree.Nodes.IsComponent(i) — Value equal to logical 1 (true) if node i represents a biconnected component. Otherwise, the value is equal to and logical 0 (false).

• tree.Nodes.ComponentIndex(i) — Index indicating the component represented by node i. The value is zero if node i represents a cut vertex.

• tree.Nodes.CutVertexIndex(i) — Index indicating the cut vertex represented by node i. The value is zero if node i represents a biconnected component.

ind — Node indices

vector

Node indices, returned as a numeric vector. ind(i) is the node in the output graph tree that represents node i in the input graph G:

• If node i is a cut vertex in graph G, then ind(i) is the associated node in tree.

• If node i is not a cut vertex, but belongs to one of the biconnected components in graph G, then ind(i) is the node in tree representing that biconnected component.

• If node i is an isolated node in graph G, then ind(i) is zero.

More About

Biconnected Components

A biconnected component of a graph is a maximally biconnected subgraph. A graph is biconnected if it does not contain any cut vertices.

Decomposing a graph into its biconnected components helps to measure how well-connected the graph is. You can decompose any connected graph into a tree of biconnected components, called the block-cut tree. The blocks in the tree are attached at shared vertices, which are the cut vertices.

The illustration depicts:

• (a) An undirected graph with 11 nodes.

• (b) Five biconnected components of the graph, with the cut vertices of the original graph colored for each component to which they belong.

• (c) Block-cut tree of the graph, which contains a node for each biconnected component (as large circles) and a node for each cut vertex (as smaller multicolored circles). In the block-cut tree, an edge connects each cut vertex to each component to which it belongs.

Cut Vertices

Also known as articulation points, cut vertices are graph nodes whose removal increases the number of connected components. In the previous illustration, the cut vertices are those nodes with more than one color: nodes 4, 6, and 7.

Extended Capabilities

Thread-Based Environment
Run code in the background using MATLAB® backgroundPool or accelerate code with Parallel Computing Toolbox™ ThreadPool.

Version History

Introduced in R2016b