In mathematics, a directed acyclic graph (briefly, DAG), more precisely called a acyclic directed graph or acyclic digraph, is a directed graph with no directed cycles; that is, for any vertex v, there is no directed path of length greater than zero that starts and ends on v.

PropertyValue
dbpedia-owl:thumbnail
dbpprop:abstract
  • In mathematics, a directed acyclic graph (briefly, DAG), more precisely called a acyclic directed graph or acyclic digraph, is a directed graph with no directed cycles; that is, for any vertex v, there is no directed path of length greater than zero that starts and ends on v. Note that a "directed acyclic graph" is not an acyclic graph that has been directed; although any direction of edges of an acyclic graph is a acyclic digraph, there are other acyclic digraphs, such as a cycle with any noncyclic orientation. The reachability relation in a DAG forms a partial order, and any finite partial order may be represented by a DAG using reachability. DAGs may also be used to model processes in which information flows in a consistent direction through a network of processors, and to provide space-efficient data structures for representing sets of sequences.
  • Dans la théorie des graphes, un graphe acyclique orienté (en anglais directed acyclic graph ou DAG) identifie un graphe qui ne possède pas de cycle, et dont les arcs sont orientés. La notion est usuelle dans plusieurs domaines de l’informatique, en particulier pour la représentation des termes avec partage, pour l'organisation des démonstrations en déduction naturelle ou pour la théorie des langages de l’orientation objet, en ce qui concerne la classification des types. On peut toujours trouver un sous-graphe couvrant d’un DAG qui est un arbre (plus précisément une forêt). Pourtant, elle est en fait beaucoup plus générale, et exprime formellement un outil traditionnel d’analyse, dont on trouve des exemples dans tous les modèles par couches, tel que le Modèle OSI, le modèle des fonctions du langage, de Bühler, ou la Pyramide des besoins de Maslow.
  • A számítógéptudományban és a matematikában a DAG-nak is nevezett irányított körmentes gráf egy irányított kört nem tartalmazó irányított gráf; ami azt jelenti, hogy egyetlen v csúcsához sincs v-ből induló és ugyanott végződő irányított út. DAG-ok alapvetően az olyan modellekben fordulnak elő, amelyben önmagába záródó úttal rendelkező csúcsnak nincs értelme, például ha egy u→v él azt jelenti, hogy v egy része u-nak, tehát ilyen út azt jelentené, hogy u önmaga része, ami értelmetlen. Minden irányított körmentes gráfhoz megfeleltethető a csúcsai egy részleges rendezése, amelyben u ≤ v pontosan akkor áll fenn, ha a gráfban létezik u-ból v-be menő irányított út. Ugyanakkor egy ilyen részleges rendezést sok különböző irányított körmentes gráf is reprezentálhat. Ezek között a legkevesebb élt a tranzitív redukált, a legtöbbet a tranzitív lezárt tartalmazza.
  • Skierowany graf acykliczny (dag – z ang. directed acyclic graph) to graf skierowany, w którym nie ma cykli. Jest to w informatyce bardzo ważna struktura, łącząca zalety drzew i ogólnych grafów skierowanych. Np. jeśli chcemy przedstawić pewne obliczenia za pomocą drzewa, może ono nam się wykładniczo rozrosnąć: b = a + a c = b + b d = c + c e = d + d f = e + e g = f + f h = g + g Drzewo dla h ma już 128 liści, operowanie na tej postaci nie jest więc wygodne. Z drugiej strony dla ogólnych grafów skierowanych trudno jest stworzyć algorytm wyliczania wartości wyrażeń, gdyż łatwo jest się zapętlić. Jeśli skorzystamy ze skierowanych grafów acyklicznych i programowania dynamicznego, otrzymamy wyliczenia (załóżmy że a=10): h = g + g (brak g, wyliczmy najpierw g) g = f + f (brak f, wyliczmy najpierw f) f = e + e (brak e, wyliczmy najpierw e) e = d + d (brak d, wyliczmy najpierw d) d = c + c (brak c, wyliczmy najpierw c) c = b + b (brak b, wyliczmy najpierw b) b = a + a = 10 + 10 = 20 c = b + b = 20 + 20 = 40 d = c + c = 40 + 40 = 80 e = d + d = 80 + 80 = 160 f = e + e = 160 + 160 = 320 g = f + f = 320 + 320 = 640 h = g + g = 640 + 640 = 1280 Na zasadzie skierowanych grafów acyklicznych działa m. in. algorytm unifikacji, działający w czasie liniowym (a którego wynik przedstawiony jako drzewo ma potencjalnie wykładniczy rozmiar).
  • Em matemática, um grafo acíclico dirigido,, é 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 u→v indica que v é parte de u, tal ligação indicaria que u é parte de si mesmo, o que é impossível.
  • Файл:Directed acyclic graph. png 250px Направленный ациклический граф — случай направленного графа, в котором отсутствуют направленные циклы, то есть пути, начинающиеся и кончающиеся в одной и той же вершине. Направленный ациклический граф является обобщением дерева (точнее, их объединения — леса).
dbpprop:hasPhotoCollection
dbpprop:relatedInstance
dbpprop:title
  • Acyclic Digraph
  • Weisstein's Conjecture
dbpprop:urlname
  • AcyclicDigraph
  • WeissteinsConjecture
dbpprop:wikiPageUsesTemplate
rdf:type
rdfs:comment
  • In mathematics, a directed acyclic graph (briefly, DAG), more precisely called a acyclic directed graph or acyclic digraph, is a directed graph with no directed cycles; that is, for any vertex v, there is no directed path of length greater than zero that starts and ends on v.
  • Dans la théorie des graphes, un graphe acyclique orienté (en anglais directed acyclic graph ou DAG) identifie un graphe qui ne possède pas de cycle, et dont les arcs sont orientés. La notion est usuelle dans plusieurs domaines de l’informatique, en particulier pour la représentation des termes avec partage, pour l'organisation des démonstrations en déduction naturelle ou pour la théorie des langages de l’orientation objet, en ce qui concerne la classification des types.
  • A számítógéptudományban és a matematikában a DAG-nak is nevezett irányított körmentes gráf egy irányított kört nem tartalmazó irányított gráf; ami azt jelenti, hogy egyetlen v csúcsához sincs v-ből induló és ugyanott végződő irányított út.
  • Skierowany graf acykliczny (dag – z ang. directed acyclic graph) to graf skierowany, w którym nie ma cykli. Jest to w informatyce bardzo ważna struktura, łącząca zalety drzew i ogólnych grafów skierowanych. Np. jeśli chcemy przedstawić pewne obliczenia za pomocą drzewa, może ono nam się wykładniczo rozrosnąć: b = a + a c = b + b d = c + c e = d + d f = e + e g = f + f h = g + g Drzewo dla h ma już 128 liści, operowanie na tej postaci nie jest więc wygodne.
  • Em matemática, um grafo acíclico dirigido,, é 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 u→v indica que v é parte de u, tal ligação indicaria que u é parte de si mesmo, o que é impossível.
  • Файл:Directed acyclic graph. png 250px Направленный ациклический граф — случай направленного графа, в котором отсутствуют направленные циклы, то есть пути, начинающиеся и кончающиеся в одной и той же вершине.
rdfs:label
  • Directed acyclic graph
  • Gerichteter azyklischer Graph
  • Graphe acyclique orienté
  • Irányított körmentes gráf
  • Skierowany graf acykliczny
  • Grafos acíclicos dirigidos
  • Направленный ациклический граф
owl:sameAs
skos:subject
foaf:depiction
foaf:page
is dbpprop:redirect of
is owl:sameAs of