Sadržaj:
Definicija - Što znači Acyclic?
Aciklič je pridjev koji se koristi za opisivanje grafa u kojem nema ciklusa ili zatvorenog puta. Drugim riječima, to je put bez opetovanih vrhova (čvorovi koji tvore graf ili veze između vrhova), isključujući početne i završne vrhove.
U informatičkoj znanosti koristi se u izrazu "usmjereni aciklički graf" (DAG). Tehnički gledano, DAG je graf nastao povezivanjem različitih vrhova s rubovima koji su usmjereni na način koji ne dopušta kretanje sekvencom koja kroz nju može proći više od dva puta; dakle, nema zatvorenog puta.
Tehopedija objašnjava Acikliku
Koncept DAG koristi se za izradu igara riječi poput Scrabble-a i znanstveno-istraživačkih aplikacija temeljenih na biologiji i genetici. DAG se također koristi u izgradnji modela iz matematike, informatike, elektroničkih sklopova, operacija sastavljanja, računanja vrijednosti povezanih na obrascima itd. DAG-ovi se koriste u modelima za ilustraciju protoka informacija kroz sustav. DAG je bolja alternativa drugim tehnikama u strukturama podataka pružajući optimizaciju korištenja memorije i poboljšanje performansi.
Ciklus je put koji prolazi kroz niz vertikala, tako da su i početni i krajnji vrhovi ista točka. Ako graf nema takve cikluse, tada se naziva acikličkim. Na primjer, razmotrite tri vertika, X, Y i Z povezane u grafu. Ako se kroz bilo koju od triju vrhova kroz njegovu strukturu kreće na različite moguće načine, ako se ne može vratiti natrag na istu početnu vršku bez da je dvaput posjetio nijednu vršku (isključujući početnu i sljedeću točku), to je aciklički graf.
Duljina najkraćeg ciklusa i opseg acikličkog grafa definirani su kao beskonačnost. Primjeri acikličkih grafova su Drveće i Šume. Aciklički i neizravni graf s bilo koja dva vrha povezana samo jednim putem naziva se stablo. Obiteljsko stablo je dobar primjer koncepta usmjerenog acikličkog stabla. Šuma je usmjerni grafikon čija su podvrsta stabla.
