Grafos acíclicos dirigidos

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Um gráfico dirigido acíclico.

Em matemática, um grafo acíclico dirigido, (em inglês: directed acyclic graph, ou simplesmente um dag ou DAG), é um grafo dirigido sem ciclo (teoria de grafos); isto é, para qualquer vértice v, não há nenhuma ligação dirigida começando e acabando em v. Estes grafos aparecem em modelos onde não faz sentido que um vértice tenha uma ligação com si próprio. Por exemplo se uma linha uv indica que v é parte de u, tal ligação indicaria que u é parte de si mesmo, o que é impossível.

Terminologia[editar | editar código-fonte]

Uma origem (inglês: source: fonte) é um vértice sem ligações que lhe chegam, enquanto que um sorvedouro (inglês: sink: pia) é um vértice sem ligações que partem dele.

Um gad (grafo acíclico dirigido) finito tem pelo menos uma origem e pelo menos um afundamento.

A extensão de um gad finito é a extensão (número de linhas) do caminho dirigido mais extenso de todos.

Aplicações[editar | editar código-fonte]

Grafos dirigidos acíclicos têm muitas aplicações importantes na informática, incluindo:

  • A estrutura de directoria num típico sistema de ficheiros UNIX
  • A parse tree construída por um compilador
  • Rede Bayesiana