Irányított körmentes gráf
A Wikipédiából, a szabad lexikonból.
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.
Tartalomjegyzék |
[szerkesztés] Elnevezések
Forrás a bejövő, 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 irányított útja csúcsainak száma.
[szerkesztés] Tulajdonságok
Minden irányított körmentes gráfnak van egy topológiai rendezése, 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.
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 v n másolatát úgy, hogy minden példány ugyanazokkal a kimeneti élekkel rendelkezzen, de bemenő élet nélkül,
- Csatoljuk v bemenő életinek egyikét minden ily módon létrejött csúcshoz,
- Töröljük v-t.
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 a csak 0-t és 1-et tartalmazó, kizárólag pozitív valós sajátértékekkel rendelkező, n x n -es mátrixok számával azonos. A sejtést McKay és társai bizonyították be. [2].
[szerkesztés] Alkalmazások
Az irányított körmentes gráfokat sokféleképp 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.
[szerkesztés] Referenciák
- ^ Sablon: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
[szerkesztés] Külső hivatkozások
- Sablon:MathWorld
- Sablon:PlanetMath



Based on work by