Grafos acíclicos dirigidos

Origem: Wikipédia, a enciclopédia livre.
Um grafo 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; 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.

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

Um grafo é formado por vértices e por bordas que conectam pares de vértices, onde estes podem ser qualquer tipo de objeto que está conectado em pares por bordas. No caso de um grafo direcionado, cada borda tem uma orientação, de um vértice a outro vértice. Um caminho em um grafo direcionado é uma sequência de bordas tendo a propriedade de que o vértice final de cada borda na sequência é o mesmo que o vértice inicial da próxima borda na sequência; um caminho forma um ciclo se o vértice inicial de sua primeira borda é igual ao vértice final de sua última borda. Um grafo acíclico dirigido é um grafo direcionado que não tem ciclos.[1][2][3]

Um vértice v de um grafo direcionado é dito ser alcançável a partir de outro vértice u quando existe um caminho que começa em você e termina em v. Como um caso especial, cada vértice é considerado alcançável a partir de si mesmo (por um caminho com bordas zero). Se um vértice pode alcançar-se através de um caminho não trivial (um caminho com uma ou mais bordas), então esse caminho é um ciclo, então outra maneira de definir grafos acíclicos direcionados é que eles são os grafos em que nenhum vértice pode alcançar-se através de um caminho não trivial.[4]

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: afundamento) é 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 sorvedouro.

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:

Referências[editar | editar código-fonte]

  1. Thulasiraman, K. (1992). Graphs : theory and algorithms. M. N. S. Swamy. New York: Wiley. OCLC 24468032 
  2. Bang-Jensen, Jørgen (2009). Digraphs : theory, algorithms and applications. Gregory Gutin 2nd ed ed. London, UK: Springer. OCLC 315139743 
  3. Kay, E.; Christofides, N. (1976). «Graph Theory: An Algorithmic Approach». Operational Research Quarterly (1970-1977) (4). 1027 páginas. ISSN 0030-3623. doi:10.2307/3009122. Consultado em 13 de agosto de 2021 
  4. Mitrani, I. (1982). Simulation techniques for discrete event systems. Cambridge: Cambridge University Press. OCLC 8473950