Main Content

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

transclosure

传递闭包

说明

示例

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

示例

全部折叠

创建并绘制一个有向图。

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

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

查找图 G 的传递闭包,并绘制所得的图。H 包含与 G 相同的节点,但具有其他边。

H = transclosure(G);
plot(H)

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

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

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

N = successors(H,1)
N = 7×1

     2
     3
     5
     6
     7
     8
     9

创建并绘制一个有向图。

s = [1 1 2 2 3 4 4 5];
t = [2 4 3 4 5 5 6 6];
G = digraph(s,t);
plot(G,'Layout','subspace')

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

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

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

     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 到达:

find(R(3,:))
ans = 1×2

     5     6

输入参数

全部折叠

输入图,指定为 digraph 对象。使用 digraph 创建有向图对象。

示例: G = digraph([1 2],[2 3])

输出参数

全部折叠

G 的传递闭包,以 digraph 对象形式返回。表 G.Nodes 被复制到 H,但 G.Edges 中的所有属性被删除。

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

详细信息

全部折叠

传递闭包

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

版本历史记录

在 R2015b 中推出