транссокращение

Переходное сокращение

Синтаксис

H = transreduction(G)

Описание

пример

H = transreduction(G) возвращает переходное сокращение графика G как новый график, H. Узлы в H совпадают с теми в G, но H имеет другие края. H содержит наименьшее количество количества ребер, таким образом что, если существует путь от узла i к узлу j в G, то существует также путь от узла i к узлу j в H.

Примеры

свернуть все

Создайте и постройте полный график порядка четыре.

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)

Найдите переходное сокращение и постройте получившийся график. Поскольку достижимость в полном графике обширна, существует теоретически несколько возможных переходных сокращений, когда любой цикл через эти четыре узла является кандидатом.

H = transreduction(G);
plot(H)

Два графика с той же достижимостью также имеют то же переходное сокращение. Поэтому любой цикл четырех узлов производит то же переходное сокращение как H.

Создайте ориентированного графа, который содержит различные четыре цикла узла: (1,3,4,2,1).

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

Найдите переходное сокращение G1. Цикл в G1 переупорядочивается так, чтобы переходные сокращения H и H1 имели тот же цикл, (1,2,3,4,1).

H1 = transreduction(G1);
plot(H1)

Создайте и постройте направленный граф без петель.

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

Подтвердите, что G не содержит циклов.

tf = isdag(G)
tf = logical
   1

Найдите переходное сокращение графика. Поскольку график не содержит циклы, переходное сокращение уникально и является подграфом G.

H = transreduction(G);
plot(H)

Входные параметры

свернуть все

Введите график, заданный как объект 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

Для просмотра документации необходимо авторизоваться на сайте