Taula de continguts:
Definició: què significa Acyclic?
Acyclic és un adjectiu usat per descriure un gràfic en el qual no hi ha cap cicle ni un camí tancat. És a dir, és una ruta sense vèrtexs repetits (nodes que formen el gràfic o enllaços entre vèrtexs), excloent els vèrtexs inicial i final.
En informàtica s’utilitza en la frase “graf acíclic dirigit” (DAG). Tècnicament, DAG és un gràfic format connectant diferents vèrtexs amb arestes dirigides de manera que no permet navegar per una seqüència que pot tenir un vèrtex que hi passa més de dues vegades; per tant, no hi ha cap camí tancat.
Techopedia explica Acyclic
El concepte de DAG s’utilitza per dissenyar jocs de paraules com Scrabble i aplicacions de recerca científica basades en biologia i genètica. DAG també s'utilitza en la construcció de models en matemàtiques, informàtica, circuits electrònics, recopilació d'operacions, computació de valors relacionats amb formularis, etc. Els DAG s'utilitzen en models per il·lustrar el flux d'informació a través d'un sistema. DAG és una millor alternativa a altres tècniques en estructures de dades, proporcionant una optimització d'ús de la memòria i una millora del rendiment.
Un cicle és un camí recorregut a través d'una seqüència de vèrtexs, de manera que els vèrtexs d'inici i final són el mateix punt. Si un gràfic no té aquests cicles, es coneix com a acíclic. Per exemple, considerem els tres vèrtexs, X, Y i Z enllaçats en un gràfic. Mentre es desplaça des de qualsevol dels tres vèrtexs a través de la seva estructura de diferents maneres possibles, si un no pot tornar al mateix vèrtex inicial sense visitar cap vèrtex (excepte el vèrtex o punt d'inici) dues vegades, llavors és un gràfic acíclic.
La longitud del cicle més curt i la circumferència d’un gràfic acíclic es defineixen com a infinit. Exemples de gràfics acíclics són els arbres i els boscos. Un gràfic acíclic i no dirigit amb dos vèrtexs connectats per un sol camí s'anomena arbre. Un arbre genealògic és un bon exemple del concepte d’arbre acíclic dirigit. Un bosc és un gràfic no dirigit els subconjunts són arbres.
