Переходное закрытие
H = transclosure(G)G как новый график, H. Узлы в H те же, что и в G, но H имеет дополнительные ребра. Если есть путь от узла i к узлу j в G, тогда есть ребро между узлами i и узловые j в H. Для мультиграфиков с несколькими ребрами между этими же двумя узлами график выхода заменяет их одним ребром.
Создайте и постройте ориентированного графа.
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)
Найдите переходное закрытие графика G и постройте график результатов. H содержит те же узлы, что и G, но имеет дополнительные ребра.
H = transclosure(G); plot(H)
Информация о переходном закрытии в H может использоваться, чтобы ответить на вопросы о достижимости исходного графика, G.
Определите узлы в G до которого можно добраться из узла 1. Эти узлы являются преемниками узла 1 в графике переходного закрытия, H.
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')
Вычислите матрицу смежности транзитивного закрытия 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
conncomp | digraph | predecessors | successors | transreduction