Kazalo:
Opredelitev - Kaj pomeni Acyclic?
Aciklič je pridevnik, ki se uporablja za opis grafa, v katerem ni cikla ali zaprte poti. Z drugimi besedami, gre za pot brez ponavljajočih se tock (vozlišč, ki tvorijo graf ali povezave med točki), razen začetnih in končnih tock.
V računalništvu se uporablja v stavku "usmerjeni aciklični graf" (DAG). Tehnično je DAG graf, oblikovan s povezovanjem različnih vertik z robovi, usmerjenimi na način, ki ne dovoljuje navigacije po zaporedju, ki lahko skozi njega poteka točko več kot dvakrat; zato zaprte poti ni.
Tehopedija razlaga Acyclic
Koncept DAG se uporablja za oblikovanje besednih iger, kot so Scrabble in aplikacije za znanstveno raziskovanje, ki temeljijo na biologiji in genetiki. DAG se uporablja tudi pri gradnji modelov iz matematike, računalništva, elektronskih vezij, operacij sestavljanja, računanja vrednosti, povezanih na obrazcih itd. DAG se uporabljajo v modelih za ponazoritev pretoka informacij skozi sistem. DAG je boljša alternativa drugim tehnikam v strukturah podatkov, saj zagotavlja optimizacijo uporabe pomnilnika in izboljšanje zmogljivosti.
Cikel je pot, ki poteka po zaporedju tock, tako da sta začetni in končni točki enaka točka. Če graf nima takšnih ciklov, ga imenujemo acikličen. Na primer, upoštevajte tri točke, X, Y in Z, povezane v grafu. Če se skozi katero od treh vrhov skozi njegovo strukturo premikate na različne možne načine, če se ne morete vrniti nazaj v isto začetno točko, ne da bi dvakrat obiskali točko (razen začetne točke ali točke), je to aciklični graf.
Dolžina najkrajšega cikla in obod acikličnega grafa sta opredeljena kot neskončnost. Primeri acikličnih grafov so Drevesa in Gozdovi. Acikličen in usmerjen graf s katerim koli dvema vozliščema, ki ju povezuje samo ena pot, se imenuje drevo. Družinsko drevo je dober primer koncepta usmerjenega acikličnega drevesa. Gozd je usmerjen graf, katerega podvrsta so drevesa.
