# transclosure

传递闭包

函数库: TyMath

# 语法

H = transclosure(G)

# 说明

H = transclosure(G) 将图 G 的传递闭包以新图 H 形式返回。H 中的节点与 G 中的节点相同，但 H 有其他边。如果 G 中有从节点 i 到节点 j 的路径，则 H 中的节点 i 和节点 j 之间有一条边。对于在同样两个节点之间具有多条边的多重图来说，输出图将用单条边代替它们。示例

# 示例

图的传递闭包

创建一个有向图。

using TyMath
G = DiGraph([1, 2, 3, 4, 4, 4, 5, 5, 5, 6, 7, 8], [2, 3, 5, 1, 3, 6, 6, 7, 8, 9, 9, 9]);

查找图 G 的传递闭包。H 包含与 G 相同的节点，但具有其他边。

H = transclosure(G);

H 中的传递闭包信息可用于回答有关原始图形 G 的可达性问题。

确定 G 中可从节点 1 到达的节点。这些节点是传递闭包图 H 中节点 1 的后继节点。

N = successors(H,1)

N = 7-element Vector{Int64}:
 2
 3
 5
 6
 7
 8
 9

计算可达性矩阵

创建一个有向图。

using TyMath
s = [1,1,2,2,3,4,4,5];
t = [2,4,3,4,5,5,6,6];
G = DiGraph(s,t);

计算 G 的传递闭包的邻接矩阵。结果将获得一个可达性矩阵，该矩阵具有非零值以指示从每个节点可到达哪些节点。

D = transclosure(G);
R = full(adjacency(D))

R = 6×6 Matrix{Bool}:
 0  1  1  1  1  1
 0  0  1  1  1  1
 0  0  0  0  1  1
 0  0  0  0  1  1
 0  0  0  0  0  1
 0  0  0  0  0  0

例如，要回答问题“哪些节点可从节点 3 到达？”，您可以查看矩阵中的第三行。该行指示只有节点 5 和 6 可从节点 3 到达：

findall(==(true),R[3,:])

# 输入参数

G - 输入图

DiGraph 对象

输入图，指定为 DiGraph 对象。可使用 DiGraph 创建有向图对象。

示例： G = DiGraph([1,2],[2,3])

# 输出参数

H - G 的传递闭包

DiGraph 对象

G 的传递闭包，以 DiGraph 对象形式返回。 G.Nodes 被复制到 H，但 G.Edges 中的权重、属性将被删除。

使用 successors(H,n) 确定 G 中可从节点 n 到达的节点。

# 详细信息

传递闭包

图的传递闭包描述各节点之间的路径。如果图中存在从节点 i 到节点 j 的路径，则在该图的传递闭包中节点 i 和节点 j 之间存在一条边。因此，对于图中的给定节点，传递闭包会将任何可达节点视为该节点的直接后继节点（后代）。

# 另请参阅

DiGraph | transreduction | conncomp | successors | predecessors