Irányított körmentes gráf

1. Sablon:Label Az irányított körmentes gráf (angolul Directed Acyclic Graph, röviden DAG) egy speciális gráf, amely irányított élekből áll, és nem tartalmaz köröket. A DAG fontos szerepet játszik számos alkalmazási területen, például a számítógépes tudományban, az ütemezésben és a verziókezelésben.

Alapfogalmak

Gráf

Egy gráf $G=(V,E)$, ahol:

• $V$: a csúcsok halmaza
• $E$: az élek halmaza, amelyek rendezett csúcspárokat kötnek össze

Kör

Egy gráfban kör akkor van, ha egy út ugyanabba a csúcsba tér vissza, ahonnan indult, az élek irányát követve.

Irányított körmentes gráf

Egy gráf akkor irányított körmentes gráf (DAG), ha:

• Az élek irányítottak.
• Nem tartalmaz köröket, azaz nincs olyan csúcspont, amelyből kiindulva vissza lehetne jutni ugyanabba a csúcspontba az élek irányát követve.

Tulajdonságok

Topologikus rendezés

Egy DAG-ra létezik olyan lineáris sorrend, amelyben minden él $(u,v)\in E$ esetén $u$ megelőzi $v$-t. Ezt a sorrendet topologikus rendezésnek nevezzük.

Gyökér és levelek

• Gyökér: Egy olyan csúcs, amelybe nem mutat él.
• Levél: Egy olyan csúcs, amelyből nem indul él.

Források és nyelők

• Forrás: Egy csúcs, amelynek nincs bejövő éle.
• Nyelő: Egy csúcs, amelynek nincs kimenő éle.

Átmérő

A DAG átmérője a leghosszabb út hossza bármely két csúcs között, ahol az út az élek irányát követi.

Fontos tételek

Topologikus rendezés tétele

Egy gráf pontosan akkor topologikusan rendezhető, ha DAG. A topologikus rendezés léte egyértelmű bizonyítéka annak, hogy a gráf körmentes.

DAG felbontási tétele

Bármely irányított gráf felbontható DAG komponensekre úgy, hogy az eredeti gráf erős összefüggő komponensei alkotják ezeket a DAG-okat.

Algoritmusok

Topologikus rendezés keresése

1. Számítsuk ki minden csúcs bejövő fokát (indegree). 2. Helyezzük a bejövő fok nélküli csúcsokat egy sorba. 3. Távolítsuk el az ilyen csúcsokat a gráfból, és csökkentsük a hozzájuk kapcsolódó csúcsok bejövő fokát. 4. Ismételjük, amíg minden csúcsot feldolgoztunk.

Kör keresése DAG-ban

Egy DAG-ban a körök jelenlétét egyszerűen topologikus rendezéssel ellenőrizhetjük. Ha a rendezés nem lehetséges, akkor a gráf nem DAG.

Hosszú út keresése

Egy DAG-ban a leghosszabb út keresése dinamikus programozási technikával hatékonyan elvégezhető, mivel a körmentesség miatt az alproblémák jól definiáltak.

Alkalmazások

• Ütemezés: DAG-ok használatosak projektek tevékenységeinek ütemezésére (például PERT diagramok).
• Adatfolyamok: Egyes számítógépes programok adatfüggőségeinek ábrázolására DAG-okat alkalmaznak.
• Verziókezelés: Verziókezelő rendszerekben a DAG-ok mutatják a változások hierarchiáját és kapcsolatait.
• Fordítás: A fordítóprogramok DAG-okat használnak az optimalizáció során, például az utasítások újrarendezéséhez.

Példák

PERT hálózat

A PERT hálózat egy DAG, amely tevékenységek és azok sorrendiségének ábrázolására szolgál. A tevékenységek csúcsok, az élek pedig az időbeli függőségeket jelölik.

Verziókezelő gráf

A verziókezelő rendszerek, mint a Git, DAG-ot használnak a különböző commitok és ágaik kapcsolatrendszerének leírására.

• Sablon:En: Sablon:T+
• Sablon:Ru: Sablon:T+