`transclosure`

Fecho transitivo de um grafo direcionado.

Categoria: Mathematics > Graph and Network Algorithms

Sintaxe

T = transclosure(G)

Retorna um digraph com uma aresta de u para v sempre que v é alcançável a partir de u em G.

Descrição

O fecho transitivo responde diretamente a perguntas de alcançabilidade: se existe um caminho de qualquer comprimento do nó u ao nó v, o fecho tem a aresta u -> v. As arestas já existentes em G são mantidas.

Em termos da matriz de adjacência, o fecho é o padrão de não zeros da soma de suas potências até o número de nós. Use adjacency(T) para lê-lo como matriz.

Argumentos de entrada

G: Um objeto digraph.

Argumentos de saída

T: Um digraph com os mesmos nós de G e as arestas adicionais implícitas pela alcançabilidade.

Exemplo

Fecho de uma cadeia 1 -> 2 -> 3

G = digraph([1 2], [2 3]);
T = transclosure(G);
full(adjacency(T))

Saída

ans = 3×3

     0     1     1
     0     0     1
     0     0     0

Veja também

transreduction digraph adjacency toposort conncomp