Cuprins:
Definiție - Ce înseamnă Acyclic?
Acyclic este un adjectiv folosit pentru a descrie un grafic în care nu există un ciclu sau o cale închisă. Cu alte cuvinte, este o cale fără vârfuri repetate (noduri care formează graficul, sau legături între vârfuri), excluzând vârfurile de început și de încheiere.
În informatică, este utilizat în sintagma „graf aciclic direcționat” (DAG). Tehnic, DAG este un grafic format prin conectarea diferitelor vârfuri cu muchii care sunt direcționate într-o manieră care nu permite navigarea printr-o secvență care poate avea un vertex care trece prin el mai mult de două ori; prin urmare, nu există o cale închisă.
Techopedia explică Acyclic
Conceptul de DAG este folosit pentru a proiecta jocuri de cuvinte precum Scrabble și aplicații de cercetare științifică bazate pe biologie și genetică. DAG este, de asemenea, utilizat în construirea de modele în matematică, informatică, circuite electronice, compilarea operațiunilor, calcularea valorilor legate de formulare, etc. DAG-urile sunt utilizate în modele pentru a ilustra fluxul de informații printr-un sistem. DAG este o alternativă mai bună la alte tehnici din structurile de date, oferind optimizarea utilizării memoriei și o îmbunătățire a performanței.
Un ciclu este o cale parcursă printr-o secvență de vârfuri, astfel încât atât vertexurile de început cât și cele de sfârșit sunt același punct. Dacă un grafic nu are astfel de cicluri, atunci este denumit aciclic. De exemplu, luați în considerare cele trei vârfuri, X, Y și Z legate într-un grafic. În timp ce parcurgeți oricare dintre cele trei vârfuri prin structura sa în diferite moduri posibile, dacă nu se poate întoarce înapoi la același vertex de pornire fără a vizita vreun vertex (excluzând vertexul sau punctul de pornire) de două ori, atunci este un grafic aciclic.
Lungimea celui mai scurt ciclu și circumferința unui grafic aciclic este definită a fi infinită. Exemple de grafice aciclice sunt Arbori și Păduri. Un grafic aciclic și nedirecționat cu oricare două vârfuri conectate printr-o singură cale este numit arbore. Un arbore genealogic este un bun exemplu al conceptului de arbore aciclic direcționat. O pădure este un grafic nedirectat ale cărui subseturi sunt arbori.
