# biconncomp
双连通图分量
函数库: TyMath
# 语法
bins,iC = biconncomp(G)
bins,iC = biconncomp(G,outputform)
# 说明
bins,iC = biconncomp(G) 以 bin 形式返回图 G 的双连通分量。bin 编号指示图中的每个边所属的双连通分量。G 中的每条边属于一个双连通分量，而 G 中的节点可以属于多个双连通分量。如果两个节点无论从图中删除哪一个都不会使它们断开连接，则说明它们属于同一个双连通分量。节点索引 iC，指示哪些节点是割点（也称为关节点）。示例
bins,iC = biconncomp(G,outputform) outputform 的默认值为 "vector"，以向量形式返回输出。指定为 "tuple" 时以元组形式返回输出，因此 bins[j] 包含分量 j 中所有节点的节点 ID。示例
# 示例
标识割点
标识图中的割点。
创建一个图。计算每条图边所属的双连通分量，其中第二个输出返回标识割点的向量。
using TyMath
G = Graph([1,1,4],[2,3,5],[1,1,1],6);
edgebins,iC = biconncomp(G)
edgebins = 3-element Vector{Int64}:
2
1
3
iC = 1-element Vector{Int64}:
1
以子图的形式提取双连通分量
此示例说明如何以子图的形式从图中提取双连通分量，然后使用原图中的节点索引标记每个子图中的节点。
创建一个图。
using TyMath
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);
bintuple = biconncomp(G, "tuple")[1];
n = length(bintuple);
for ii = 1:n
subgraph(G, bintuple[ii]);
end
突出显示双连通分量
根据每条边所属的双连通分量显示边的颜色。
using TyMath
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);
r = biconncomp(G)
r = r[1]
13-element Vector{Int64}:
4
4
4
4
4
3
⋮
3
2
1
1
1
# 输入参数
G - 输入图Graph 对象
输入图，指定为 Graph 对象。可使用 Graph 创建一个无向图对象。
示例： G = Graph(1,2)
outputform - 输出的类型"vector" （默认） | "tuple"
输出的类型，指定为 "vector"（默认值）或 "tuple"。outputform 指定为 "vector" 后 bins 是数值向量，指示每条边所属的双连通分量。指定为 "tuple" 后 bins 是元组，bins[j] 包含属于分量 j 的所有节点的节点 ID。
# 输出参数
bins - 双连通分量向量 | 元组
双连通分量，以向量或元组形式返回。bin 编号将图中的每个边或节点赋给一个双连通分量：
如果 outputform 是 "vector"（默认值），则 bins 是数值向量，指示每个边所属的连通分量 (bin)；
如果 outputform 是 "tuple"，则 bins 是元组，bins[j] 包含属于分量 j 的所有节点的节点 ID。
iC - 割点索引向量
割点索引，以节点 ID 的数值向量形式返回。
# 详细信息
双连通分量
图的双连通分量是指最大双连通子图。如果一个图中不包含任何割点，则它就是一个双连通图。
将一个图分解成双连通分量，可帮助我们判断该图的连通性。您可以将任何连通图分解成双连通分量树，称为块割点树。树中的各个块在共同的顶点处相连，这些顶点即为割点。
下图描绘了：
(a) 一个具有 11 个节点的无向图；
(b) 图的五个双连通分量，原图的割点通过不同颜色表示各自所属的分量；
(c) 图的块割点树，其中包含代表各个双连通分量的节点（用纯色大圆表示）和代表各个割点的节点（用多色小圆表示）。在块割点树中，每个割点与它所属的每个分量之间由一条边相连。
割点
割点也称为关节点，是指删除它之后会导致连通分量增多的图节点。在上图中，割点是具有多种颜色的那些节点：节点 4、6 和 7。