Obsah:
Definícia - Čo znamená acyklický?
Acyklický je prídavné meno, ktoré sa používa na opis grafu, v ktorom neexistuje cyklus alebo uzavretá cesta. Inými slovami, je to cesta bez opakovaných vrcholov (uzly, ktoré tvoria graf alebo spojenia medzi vrcholmi), bez začiatočných a koncových vrcholov.
V informatike sa používa vo fráze „smerovaný acyklický graf“ (DAG). Technicky je DAG graf tvorený spojením rôznych vrcholov s hranami, ktoré sú nasmerované takým spôsobom, ktorý neumožňuje navigáciu cez sekvenciu, ktorá môže mať vrchol, ktorý ním prechádza viac ako dvakrát; preto neexistuje žiadna uzavretá cesta.
Techopedia vysvetľuje Acyclic
Koncept DAG sa používa na návrh slovných hier, ako je Scrabble a aplikácií vedeckého výskumu založených na biológii a genetike. DAG sa používa aj pri vytváraní modelov v matematike, počítačovej vede, elektronických obvodoch, kompilácii, výpočte súvisiacich hodnôt na formulároch atď. DAG sa používajú v modeloch na ilustráciu toku informácií cez systém. DAG je lepšou alternatívou k iným technikám v dátových štruktúrach tým, že poskytuje optimalizáciu využitia pamäte a zlepšenie výkonu.
Cyklus je cesta prechádzajúca sekvenciou vrcholov, takže počiatočný aj koncový vrchol sú rovnaké. Ak graf nemá také cykly, potom sa označuje ako acyklický. Napríklad, zvážte tri vrcholy, X, Y a Z spojené v grafe. Ak sa z ktorejkoľvek z týchto troch vrcholov prechádza rôznymi spôsobmi rôznymi spôsobmi, ak sa človek nemôže vrátiť späť do toho istého počiatočného vrcholu bez toho, aby dvakrát navštívil akýkoľvek vrchol (okrem počiatočného vrcholu alebo bodu), ide o acyklický graf.
Dĺžka najkratšieho cyklu a obvod acyklického grafu sú definované ako nekonečno. Príkladmi acyklických grafov sú stromy a lesy. Acyklický a nepriamy graf s akýmikoľvek dvoma vrcholmi spojenými iba jednou cestou sa nazýva strom. Rodinný strom je dobrým príkladom konceptu riadeného acyklického stromu. Les je nepriamym grafom, ktorého podmnožinou sú stromy.
