Ordenação Topológica

Nesta lição, discutiremos sobre ordenação topológica e o Algoritmo de Kahn.

Em primeiro lugar, vamos definir o que é um grafo transposto. O grafo transposto de um grafo direcionado é outro grafo direcionado com o mesmo conjunto de vértices de com todas as arestas invertidas em comparação com a orientação das arestas correspondentes em . Nesta lição, iremos nos referir ao grafo transposto de como .

Agora, vamos falar sobre a teoria por detrás da ordenação topológica.

A ordenação topológica de um grafo é uma ordenação linear dos vértices tal que para cada aresta direcionada , o vértce vem antes de na ordenação.

Mas será que todos os grafos direcionados têm uma ordenação topológica? A resposta é "Não". Um grafo direcionado tem uma ordenação topológica se e somente se for acíclico (não tem um ciclo). Este tipo de grafo é conhecido como Grafo Acíclico Direcionado (DAG).

Suponha que temos um grafo com vértices e arestas direcionadas.

Se o nosso grafo tem um ciclo, não conseguimos encontrar uma ordenação topológica porque, em cada ordenação linear, se olharmos para um ciclo de , pelo menos uma aresta deste ciclo irá ignorar a nossa condição de que, para cada aresta direcionada , vem antes de na ordenação.

Agora, vamos provar que se for acíclico, ele tem uma ordenação topológica. Para provar esta afirmação, precisamos de provar a primeira propriedade dos DAG's:

Todo DAG tem pelo menos um vértice com grau de entrada igual a

Prova da propriedade: