ordenação topológica
Sign in to saveAlso known as topological ordering, topological sort
uma ordenação dos vértices de um grafo direcionado para a qual cada aresta é direcionada de um vértice que vem antes para um que vem depois na ordenação
Wikidata facts
- Instance of
- computational problem
- Subclass of
- sorting
Show 3 more facts
- facet of
- directed acyclic graph
- maintained by WikiProject
- WikiProject Mathematics
Sources (3)
via Wikidata · CC0
Article · Português
Em teoria dos grafos, uma ordenação topológica de um digrafo acíclico (DAG) é uma ordem linear de seus nós em que cada nó vem antes de todos nós para os quais este tenha arestas de saída. Cada DAG tem uma ou mais ordenações topológicas. Mais formalmente, define-se a relação acessibilidade R sobre os nós do DAG tal que xRy se e somente se existe um caminho dirigido de x para y. Então, R é uma ordem parcial, e uma ordenação topológica é uma desta ordem parcial, isto é, uma ordem total compatível com a ordem parcial.
Abstract from DBpedia / Wikipedia · CC BY-SA