„Irányított körmentes gráf” változatai közötti eltérés
| [nem ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
start |
fordítás folytatás |
||
1. sor:
[[Image:Directed_acyclic_graph.png|right|frame|A simple directed acyclic graph]]
A [[számítástudomány]]ban és a [[Matematika|matematikában]] a [[DAG]]-nak is nevezett '''irányított körmentes gráf''' egy [[irányított kör]]t 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és]]e, 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.
== Elnevezések ==
''Forrás'' a bejövő, ''nyelvő'' pedig a kimenő élt nem tartalmazó csúcs. Egy véges DAG-nak legalább egy forrást, és legalább egy nyelőt tartalmaznia kell.
Egy véges DAG ''hossza'' a leghosszabb irányított útja csúcsainak száma.
== Tulajdonságok ==
Minden irányított körmentes gráfnak van egy [[topológiai rendezés]]e, ami a csúcsainak egy olyan sorozata, amelyben minden csúcs a belőle elérhető csúcsok előtt szerepel. Ez a rendezés általában nem egyértelmű. Az azonos részleges rendezéssel reprezenált irányított körmentes gráfhoz tartozó topológiai rendezések halmaza is azonos.
{{csonk}}
| |||