Main Content

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

biconncomp

双连通图分量

说明

示例

bins = biconncomp(G) 以 bin 形式返回图 G双连通分量。bin 编号指示图中的每个边所属的双连通分量。G 中的每条边属于一个双连通分量,而 G 中的节点可以属于多个双连通分量。如果两个节点无论从图中删除哪一个都不会使它们断开连接,则说明它们属于同一个双连通分量。

示例

bins = biconncomp(G,'OutputForm',form)(其中 form'cell')以元胞数组形式返回输出,因此 bins{j} 包含分量 j 中所有节点的节点 ID。form 的默认值为 'vector'

示例

[bins,iC] = biconncomp(___) 还返回节点索引 iC,指示哪些节点是割点(也称为关节点)。

示例

全部折叠

创建并绘制一个图。根据每条边所属的双连通分量显示边的颜色。

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,'LineWidth',2);

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

p.EdgeCData =  biconncomp(G);

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);
plot(G)

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

根据每个节点所属的双连通分量,将图节点分组成多个 bin。然后遍历每个 bin,并为每个双连通分量提取子图。使用原来的节点索引标记每个子图中的节点。

bincell = biconncomp(G, 'OutputForm', 'cell');
n = length(bincell);

for ii = 1:n
    subplot(2,2,ii)
    plot(subgraph(G, bincell{ii}), 'NodeLabel', bincell{ii});
end

Figure contains 4 axes objects. Axes object 1 contains an object of type graphplot. Axes object 2 contains an object of type graphplot. Axes object 3 contains an object of type graphplot. Axes object 4 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.

[edgebins,iC] = biconncomp(G)
edgebins = 1×13

     4     4     4     4     4     3     3     3     3     2     1     1     1

iC = 1×3

     4     6     7

节点 4、6 和 7 是图 G 的割点。使用 highlight 放大 iC 中引用的割点。

highlight(p, iC)

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

输入参数

全部折叠

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

示例: G = graph(1,2)

输出的类型,指定为下列值之一:

选项输出
'vector'(默认值)bins 是数值向量,指示每条边所属的双连通分量。
'cell'bins 是元胞数组,bins{j} 包含属于分量 j 的所有节点的节点 ID。

输出参数

全部折叠

双连通分量,以向量或元胞数组形式返回。bin 编号将图中的每个边或节点赋给一个双连通分量:

  • 如果 OutputForm'vector'(默认值),则 bins 是数值向量,指示每个边所属的连通分量 (bin)。自环边分配给 bin 0,因为这些边不属于任何双连通分量。

  • 如果 OutputForm'cell',则 bins 是元胞数组,bins{j} 包含属于分量 j 的所有节点的节点 ID。

割点索引,以节点 ID 的数值向量形式返回。

详细信息

全部折叠

双连通分量

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

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

下图描绘了:

  • (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 中推出