Wikipédia

„Irányított körmentes gráf” változatai közötti eltérés

Laptörténet interaktív böngészése
[ellenőrzött változat][ellenőrzött változat]
← Régebbi szerkesztésÚjabb szerkesztés →
Tartalom törölve Tartalom hozzáadva
VizuálisWikiszöveges
MerlIwBot (vitalap | szerkesztései)
112 810 szerkesztés
a Bot: következő eltávolítása: fr:Graphe acyclique orienté (strong connection between (2) hu:Irányított körmentes gráf and fr:Graphe orienté acyclique)
Nincs szerkesztési összefoglaló
1. sor:
[[Kép:Directed acyclic graph.png|jobbra|frame|Egyszerű irányított körmentes gráf]]
 
A [[számítógéptudomány]]ban és a [[Matematikamatematika|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.
24. sor:
Egyes algoritmusok sokkal egyszerűbbek általános gráfok helyett DAG-okra alkalmazva. Például a [[mélységi keresés]]en alapuló gráfalgoritmusok futtatásakor általában nyilván kell tartanunk a már bejárt csúcsokat. Erre azért van szükség, mert enélkül egy kör bejárásakor [[végtelen ciklus]]ba juthatnánk. DAG-ok esetében nincsenek ilyen körök.
 
Az ''n'' csúcsú, nem-[[izomorf]] DAG-ok számát a ''Weisstein-sejtés'' <ref>{{MathWorld | urlname=WeissteinsConjecture | title=Weisstein's Conjecture}}</ref> adja meg: eszerint az ''n'' csúcsú, nem izomorf DAG-ok száma egyenlő a csak 0-t és 1-et tartalmazó ''n'' ''x''× ''n'' -es mátrixok számával, melyek [[sajátérték]]ei [[pozitív számok|pozitív]] [[valós számok|valós]]ak. A sejtést McKay és társai bizonyították be.<ref>McKay, B. D.; Royle, G. F.; Wanless, I. M.; Oggier, F. E.; Sloane, N. J. A.; and Wilf, H. "Acyclic Digraphs and Eigenvalues of (0,1)-Matrices." J. Integer Sequences 7, Article 04.3.3, 1-5, 2004. [http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.pdf http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.pdf] or [http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html]</ref>
 
== Alkalmazások ==
31. sor:
* [[Bayes-hálók]]
* A [[Szemétgyűjtés (számítástudomány)|szemétgyűjtő]] algoritmusok általában DAG-okkal tartják nyilván a referenciákat
* Parancs-ütemezés és [[makefile]]-ok [[függőségi gráf]]ja
* [[Objektumorientált]] [[programozási nyelv]]ekben az [[öröklődés]]sel létrehozott [[osztály]]ok függőségi gráfjai
* Irányított körmentes szó-gráfok használhatóak [[sztring]]-halmazok (szó-halmazok) memóriatakarékos tárolására
A lap eredeti címe: „https://hu.wikipedia.org/wiki/Irányított_körmentes_gráf”