A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
A számítógéptudományban és a matematikában az angol neve (directed acyclic graph) után DAG-nak is nevezett irányított körmentes gráf egyetlen irányított kört sem tartalmazó irányított gráf; ami azt jelenti, hogy egyetlen v csúcsához sincs abbó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észbenrendezé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észbenrendezé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
A forrás a bejövő élt nem tartalmazó, a nyelő 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 bejárható (irányított) út csúcsainak száma.
Tulajdonságok
Minden irányított körmentes gráfnak van egy topológiai sorrendje, 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 reprezentált irányított körmentes gráfhoz tartozó topológiai rendezések halmaza is azonos.
A DAG-ok fák általánosításának is tekinthetők abból a szempontból, hogy a DAG-okban az egyes részfák a gráf különböző részein többször is előfordulhatnak. Egy sok azonos részfát tartalmazó fa esetén ez a struktúra méretének drasztikus csökkenését okozhatja. Ugyanakkor viszont a DAG-ok erdőkké bővíthetők a következő algoritmussal:
- Amíg létezik 1-nél nagyobb n bemeneti fokszámú v csúcs,
- Hozzuk létre a v csúcs n darab másolatát úgy, hogy minden példány ugyanazokkal a kimeneti élekkel rendelkezzen, de bemenő élek nélkül,
- Csatoljuk az eredeti v csúcs bemenő éleiből egyet-egyet az előbbi lépésben "másolt" csúcsokhoz,
- Töröljük az eredeti v csúcsot.
Ha a gráfot változtatás, vagy a csúcsok egyenlőségének vizsgálata nélkül járjuk be, akkor a fenti módon létrejött erdő azonosnak fog tűnni a kiinduló DAG-gal.
Egyes algoritmusok sokkal egyszerűbbek általános gráfok helyett DAG-okra alkalmazva. Például a mélységi keresésen 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 ciklusba 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[1] adja meg: eszerint az n csúcsú, nem izomorf DAG-ok száma egyenlő a csak 0-t és 1-et tartalmazó n × n-es mátrixok számával, melyek sajátértékei pozitív valós számok. A sejtést McKay és társai bizonyították be.[2]
Alkalmazások
Az irányított körmentes gráfokat sokféleképpen használja a számítástudomány:
- Bayes-hálók
- A 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áfja
- Objektumorientált programozási nyelvekben az öröklődéssel létrehozott osztályok 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 Wikipédia kategóriarendszere is DAG-gal ábrázolható, amennyiben a kategóriaszervezési irányelvek tiltják az önmagukat tartalmazó kategórialáncok kialakítását, viszont engedélyezik, hogy egy kategória több fő-kategóriának is al-kategóriája lehessen.
Jegyzetek
- ↑ Weisstein, Eric W.: Weisstein's Conjecture (angol nyelven). Wolfram MathWorld
- ↑ 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 or http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html
Külső hivatkozások
- Weisstein, Eric W.: Acyclic Digraph (angol nyelven). Wolfram MathWorld
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.
Analóg multiméterek túlterhelés elleni védelme
Egyenáram
Egyenáram mérése
Egyenirányítós lengőtekercses műszer
Elektromágnes (fizika)
Elektromos feszültség
Elektromos térerősség
Fáziseltolódás
Fázismutató
Fajlagos ellenállás
Feszültséggenerátor
Feszültségváltó
Forgó mágneses tér
Háromfázisú hálózat
Hőelektromosság
Hatásos ellenállás
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.