Tartalomjegyzék:
Meghatározás - Mit jelent az aciklikus?
Az aciklikus melléknév egy olyan grafikon leírására szolgál, amelyben nincs ciklus vagy zárt út. Más szavakkal, ez egy olyan út, amely nem tartalmaz ismétlődő csúcsokat (csomópontok, amelyek a gráfot alkotják, vagy a csúcsok közötti kapcsolatokat tartalmazzák), kivéve a kezdő és a vég csúcsokat.
A számítástechnikában a „irányított aciklikus gráf” (DAG) kifejezésben használják. Technikai szempontból a DAG egy olyan grafikon, amelyet különféle csúcsok és élek összekapcsolásával hoznak létre, és amelyek olyan irányba vannak irányítva, amely nem teszi lehetővé a navigációt egy olyan szekvencián, amelynél egy csúcs több mint kétszer áthaladhat; ezért nincs zárt út.
A Techopedia magyarázza az Acyclic-t
A DAG koncepcióját olyan szójátékok tervezésére használják, mint a Scrabble, valamint a biológián és genetikán alapuló tudományos kutatási alkalmazásokat. A DAG-t a modellek építéséhez használják a matematikában, a számítógépes tudományban, az elektronikus áramkörökben, a műveletek összeállításában, az űrlapokhoz kapcsolódó értékek kiszámításában stb. A DAG-kat a modellekben használják az információáramlás illusztrálására egy rendszeren keresztül. A DAG jobb alternatívája más adatszerkezetekben alkalmazott technikáknak, mivel a memóriahasználatot optimalizálja és javítja a teljesítményt.
A ciklus egy csúcsok sorozatán áthaladó út, oly módon, hogy mind a kezdő, mind a végcsúcsok azonos pontok. Ha egy gráfnak nincsenek ilyen ciklusai, akkor aciklikusnak hívják. Például vegyük figyelembe a grafikonban összekapcsolt három csúcsot, az X, Y és Z csúcsot. Miközben a három csúcs bármelyikéből a lehetséges szerkezeteken keresztül halad, ha az ember nem tud visszatérni ugyanahhoz a kezdő csúcshoz anélkül, hogy bármely csúcsot kétszer meglátogatna (kivéve a kezdő csúcsot vagy egy pontot), akkor ez egy aciklikus gráf.
A legrövidebb ciklus hosszát és egy aciklikus gráf kerületét végtelennek tekintik. Az aciklikus grafikonokra példák a fák és az erdők. Egy aciklusos és irányítatlan gráfot, amelynek bármelyik csúcsa csak egy úton kapcsolódik, fanak nevezzük. A családfa jó példa az irányított aciklikus fa koncepciójára. Az erdő egy irányítatlan gráf, amelynek részhalmaza fák.
