Main Content

本页翻译不是最新的。点击此处可查看最新英文版本。

bctree

块割点树图

说明

示例

tree = bctree(G) 返回图 G 的块割点树,使 tree 中的每个节点代表 G 的一个双连通分量割点。代表割点的节点与代表包含该割点的双连通分量的所有节点相连。

示例

[tree,ind] = bctree(G) 还返回一个数值节点索引向量,其中的索引将 G 的节点映射到 tree 的节点。

示例

全部折叠

计算一个图的块割点树、查看生成的节点属性,然后突出显示图论图中的割点。

创建并绘制一个图。

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);

Figure contains an axes object. The axes object contains an object of type graphplot.

计算图的块割点树并查看节点属性。

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       

绘制块割点树,使用红色菱形标记表示代表割点的节点。圆形节点代表原图中的双连通分量。

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

Figure contains an axes object. The axes object contains an object of type graphplot.

创建并绘制一个图。

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);

Figure contains an axes object. The axes object contains an object of type graphplot.

计算图的块割点树 tr,并指定第二个输出 ix 以返回节点索引。

[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

每个索引 ix(j) 指示块割点树中的一个节点,它代表输入图中的节点 j。例如,tr 中的节点 4 代表 G 中的一个分量,该分量包含节点 1、2 和 3,所以 ix 中的前三个项都是 4。

输入参数

全部折叠

输入图,指定为 graph 对象。使用 graph 创建一个无向图对象。

示例: G = graph(1,2)

输出参数

全部折叠

块割点树图,返回为 graph 对象。treeG 中的每个割点包含一个节点,还为 G 中的每个双连通分量包含一个节点。节点表 tree.Nodes 中包含其他节点属性,用来描述每个节点所代表的内容:

  • tree.Nodes.IsComponent(i) - 如果节点 i 代表一个双连通分量,则该值等于逻辑值 1 (true)。否则,该值等于逻辑值 0 (false)。

  • tree.Nodes.ComponentIndex(i) - 索引,指示节点 i 所代表的分量。如果节点 i 代表一个割点,则该值为零。

  • tree.Nodes.CutVertexIndex(i) - 索引,指示节点 i 所代表的割点。如果节点 i 代表一个双连通分量,则该值为零。

节点索引,返回为数值向量。ind(i) 是输出图 tree 中的节点,代表输入图 G 中的节点 i

  • 如果节点 i 是图 G 中的一个割点,则 ind(i)tree 中的关联节点。

  • 如果节点 i 不是割点,但属于图 G 中的某个双连通分量,则 ind(i)tree 中代表该双连通分量的节点。

  • 如果节点 i 是图 G 中的一个孤立节点,则 ind(i) 为零。

详细信息

全部折叠

双连通分量

图的双连通分量是指最大双连通子图。如果一个图中不包含任何割点,则它就是一个双连通图。

将一个图分解成双连通分量,可帮助我们判断该图的连通性。您可以将任何连通图分解成双连通分量树,称为块割点树。树中的各个块在共同的顶点处相连,这些顶点即为割点。

下图描绘了:

  • (a) 一个具有 11 个节点的无向图。

  • (b) 图的五个双连通分量,原图的割点通过不同颜色表示各自所属的分量。

  • (c) 图的块割点树,其中包含代表各个双连通分量的节点(用纯色大圆表示)和代表各个割点的节点(用多色小圆表示)。在块割点树中,每个割点与它所属的每个分量之间由一条边相连。

An undirected graph, the biconnected components of the graph, and the block-cut tree of the graph

割点

割点也称为关节点,是指删除它之后会导致连通分量增多的图节点。在上图中,割点是具有多种颜色的那些节点:节点 4、6 和 7。

扩展功能

基于线程的环境
使用 MATLAB® backgroundPool 在后台运行代码或使用 Parallel Computing Toolbox™ ThreadPool 加快代码运行速度。

版本历史记录

在 R2016b 中推出