Irányított körmentes gráf

A Wikipédiából, a szabad enciklopédiából
Egyszerű irányított körmentes gráf

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 uv é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 uv 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[szerkesztés | forrásszöveg szerkesztése]

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.

Tulajdonságok[szerkesztés | forrásszöveg szerkesztése]

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 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 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 egyenlő a csak 0-t és 1-et tartalmazó n x n -es mátrixok számával, melyek sajátértékei pozitív valósak. A sejtést McKay és társai bizonyították be.[2]

Alkalmazások[szerkesztés | forrásszöveg szerkesztése]

Az irányított körmentes gráfokat sokféleképp használja a számítástudomány:

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  1. Weisstein, Eric W.: Weisstein's Conjecture. MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/WeissteinsConjecture.html (angolul)
  2. 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[szerkesztés | forrásszöveg szerkesztése]