condensation

Condensação de um dígrafo: cada componente fortemente conexo vira um nó.

Categoria: Mathematics > Graph and Network Algorithms

Sintaxe

C = condensation(G)

Descrição

Dois nós estão no mesmo componente fortemente conexo quando cada um alcança o outro. Colapsar cada componente em um único nó elimina todos os ciclos, então o resultado é sempre um grafo acíclico dirigido. Isso torna a condensação útil antes de uma etapa de ordenação ou escalonamento.

A pertinência de cada nó original a um componente vem de conncomp(G, 'Type', 'strong').

Argumentos de entrada

G

Um digraph.

Argumentos de saída

C

Um dígrafo com um nó por componente fortemente conexo de G, e uma aresta entre dois componentes quando G tem uma aresta de um para o outro.

Exemplo

Colapsando um ciclo

D = digraph([1 2 3 3 4], [2 3 1 4 5]);
C = condensation(D);
fprintf('%d nodes, %d edges, dag: %d\n', numnodes(C), numedges(C), isdag(C))

3 nodes, 2 edges, dag: 1

Veja também

conncomp isdag digraph hascycles