Main Content

transreduction

传递归约

全页折叠

语法

H = transreduction(G)

说明

H = transreduction(G) 将图 G 的传递归约以新图 H 形式返回。H 中的节点与 G 中的节点相同，但 H 具有不同的边。H 包含最少的边数，因此，如果 G 中存在一条从节点 i 到节点 j 的路径，则 H 中也会有一条从节点 i 到节点 j 的路径。

示例

示例

全部折叠

打开实时脚本

创建并绘制一个完整的四阶图。

G = digraph([1 1 1 2 2 2 3 3 3 4 4 4],[2 3 4 1 3 4 1 2 4 1 2 3]);
plot(G)

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

查找传递归约并绘制所得的图。由于整个图中的可达性相当广泛，理论上有几个可能的传递归约，因为通过四个节点的任何循环都是一个候选传递归约。

H = transreduction(G);
plot(H)

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

两个具有相同可达性的图也具有相同的传递归约。因此，四个节点的任何循环会生成与 H 相同的传递归约。

创建一个包含不同的四节点循环的有向图：(1,3,4,2,1)。

G1 = digraph([1 3 4 2],[3 4 2 1]);
plot(G1)

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

查找 G1 的传递归约。将 G1 中的循环重新排序，以使传递归约 H 和 H1 具有相同的循环 (1,2,3,4,1)。

H1 = transreduction(G1);
plot(H1)

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

打开实时脚本

创建并绘制一个有向无环图。

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

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

确认 G 不包含任何循环。

tf = isdag(G)
tf = logical
   1

查找图的传递归约。由于图不包含循环，传递归约是唯一的且是 G 的子图。

H = transreduction(G);
plot(H)

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

输入参数

全部折叠

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

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

输出参量

全部折叠

G 的传递归约，以 digraph 对象形式返回。表 G.Nodes 被复制到 H，但 G.Edges 中的所有属性被删除。H 可能包含 G 中不存在的新边。

H 包含仍保留图 G 的可达性的最少数量的边。换言之，transclosure(H) 与 transclosure(G) 相同。

如果 isdag(G) 为 true，则 H 是唯一的且是 G 的子图。

详细信息

全部折叠

传递归约

图 G 的传递归约指与 G 具有相同可达性但边数最少的图。因此，在具有与 G 相同的传递闭包的所有图中，传递归约是边数最少的图。如果两个有向图具有相同的传递闭包，它们也具有相同的传递归约。

版本历史记录

在 R2015b 中推出

另请参阅

| |