biconncomp
双连通图分量
说明
示例
突出显示双连通分量
创建并绘制一个图。根据每条边所属的双连通分量显示边的颜色。
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);
p.EdgeCData = biconncomp(G);
以子图的形式提取双连通分量
此示例说明如何以子图的形式从图中提取双连通分量,然后使用原图中的节点索引标记每个子图中的节点。
创建并绘制一个图。
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)
根据每个节点所属的双连通分量,将图节点分组成多个 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
标识割点
标识图中的割点,然后在图论图中突出显示这些顶点。
创建并绘制一个图。计算每条图边所属的双连通分量,并指定第二个输出以返回标识割点的向量。
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);
[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)
输入参数
输出参数
bins
— 双连通分量
向量 | 元胞数组
双连通分量,以向量或元胞数组形式返回。bin 编号将图中的每个边或节点赋给一个双连通分量:
如果
OutputForm
是'vector'
(默认值),则bins
是数值向量,指示每个边所属的连通分量 (bin)。自环边分配给 bin0
,因为这些边不属于任何双连通分量。如果
OutputForm
是'cell'
,则bins
是元胞数组,bins{j}
包含属于分量j
的所有节点的节点 ID。
iC
— 割点索引
向量
割点索引,以节点 ID 的数值向量形式返回。
详细信息
双连通分量
图的双连通分量是指最大双连通子图。如果一个图中不包含任何割点,则它就是一个双连通图。
将一个图分解成双连通分量,可帮助我们判断该图的连通性。您可以将任何连通图分解成双连通分量树,称为块割点树。树中的各个块在共同的顶点处相连,这些顶点即为割点。
下图描绘了:
(a) 一个具有 11 个节点的无向图。
(b) 图的五个双连通分量,原图的割点通过不同颜色表示各自所属的分量。
(c) 图的块割点树,其中包含代表各个双连通分量的节点(用纯色大圆表示)和代表各个割点的节点(用多色小圆表示)。在块割点树中,每个割点与它所属的每个分量之间由一条边相连。
割点
割点也称为关节点,是指删除它之后会导致连通分量增多的图节点。在上图中,割点是具有多种颜色的那些节点:节点 4、6 和 7。
扩展功能
基于线程的环境
使用 MATLAB® backgroundPool
在后台运行代码或使用 Parallel Computing Toolbox™ ThreadPool
加快代码运行速度。
版本历史记录
在 R2016b 中推出
MATLAB 命令
您点击的链接对应于以下 MATLAB 命令:
请在 MATLAB 命令行窗口中直接输入以执行命令。Web 浏览器不支持 MATLAB 命令。
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)