Πίνακας περιεχομένων:
Ορισμός - Τι σημαίνει Acyclic;
Το Acyclic είναι ένα επίθετο που χρησιμοποιείται για να περιγράψει ένα γράφημα στο οποίο δεν υπάρχει κύκλος ή κλειστή διαδρομή. Με άλλα λόγια, είναι μια διαδρομή χωρίς επαναλαμβανόμενες κορυφές (κόμβοι που σχηματίζουν το γράφημα ή συνδέσεις μεταξύ κορυφών), εξαιρουμένων των κορυφών εκκίνησης και λήξης.
Στην επιστήμη των υπολογιστών, χρησιμοποιείται στη φράση "κατευθυνόμενο ακυκλικό γράφημα" (DAG). Τεχνικά, το DAG είναι ένα γράφημα που σχηματίζεται με τη σύνδεση διαφορετικών κορυφών με ακμές που κατευθύνονται κατά τρόπο που δεν επιτρέπει την περιήγηση σε μια ακολουθία που μπορεί να έχει μια κορυφή που διέρχεται από αυτό πέρα από δύο φορές. επομένως, δεν υπάρχει κλειστή διαδρομή.
Η Techopedia εξηγεί το Acyclic
Η έννοια του DAG χρησιμοποιείται για το σχεδιασμό παιχνιδιών λέξεων όπως το Scrabble και εφαρμογές επιστημονικής έρευνας που βασίζονται στη βιολογία και τη γενετική. Το DAG χρησιμοποιείται επίσης για την οικοδόμηση μοντέλων στα μαθηματικά, την επιστήμη των υπολογιστών, τα ηλεκτρονικά κυκλώματα, τις εργασίες σύνταξης, τις υπολογιστικές τιμές που σχετίζονται με τις φόρμες κλπ. Τα DAG χρησιμοποιούνται σε μοντέλα για την απεικόνιση της ροής πληροφοριών μέσω ενός συστήματος. Το DAG είναι μια καλύτερη εναλλακτική λύση από άλλες τεχνικές στις δομές δεδομένων, παρέχοντας βελτιστοποίηση της χρήσης της μνήμης και βελτίωση της απόδοσης.
Ένας κύκλος είναι μια διαδρομή που διασχίζεται μέσω μιας ακολουθίας κορυφών, έτσι ώστε τόσο οι αρχικές όσο και οι τελικές κορυφές να είναι το ίδιο σημείο. Εάν ένα γράφημα δεν έχει τέτοιους κύκλους, τότε αναφέρεται ως ακυκλικό. Για παράδειγμα, εξετάστε τις τρεις κορυφές X, Y και Z που είναι συνδεδεμένες σε ένα γράφημα. Ενώ διασχίζετε από οποιαδήποτε από τις τρεις κορυφές μέσω της δομής του με διαφορετικούς τρόπους, αν δεν μπορεί κανείς να επιστρέψει στην ίδια κορυφαία κορυφή χωρίς να επισκεφθεί οποιαδήποτε κορυφή (εκτός από την κορυφή ή το σημείο εκκίνησης) δύο φορές, τότε είναι ένα γράφημα Acyclic.
Το μήκος του μικρότερου κύκλου και η περιφέρεια ενός ακυκλικού γραφήματος ορίζεται ως άπειρο. Παραδείγματα ακυκλικών γραφημάτων είναι δέντρα και δάση. Ένα μη κυκλικό και μη κατευθυνόμενο γράφημα με οποιεσδήποτε δύο κορυφές που συνδέονται με μία μόνο διαδρομή ονομάζεται δέντρο. Ένα οικογενειακό δέντρο είναι ένα καλό παράδειγμα της ιδέας ενός κατευθυνόμενου ακυκλικού δέντρου. Ένα δάσος είναι ένα μη κατευθυνόμενο γράφημα του οποίου τα υποσύνολα είναι δέντρα.
