Κατευθυνόμενος άκυκλος γράφος
 |
Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. |
Στην Επιστήμη Υπολογιστών, ένας γράφος ονομάζεται κατευθυνόμενος άκυκλος γράφος αν είναι κατευθυνόμενος και δεν περιέχει κύκλους. Δηλαδή, οι ακμές του δεν είναι αμφίδρομες, αλλά έχουν κατεύθυνση, και για κανένα κόμβο δεν υπάρχει μονοπάτι (πέρα από το τετριμμένο) που να ξεκινά από αυτόν και να καταλήγει σ' αυτόν.
Ένας κατευθυνόμενος άκυκλος γράφος μπορεί να χρησιμεύσει στη μοντελοποίηση διαφόρων δομών. Για παράδειγμα, μιας ροής εργασιών, ή ενός προγράμματος σπουδών όπου κάποια μαθήματα έχουν προαπαιτούμενα μαθήματα, ή μιας μερικής διάταξης στα στοιχεία ενός συνόλου.
Τοπολογική ταξινόμηση[Επεξεργασία | επεξεργασία κώδικα]
Κάθε κατευθυνόμενος άκυκλος γράφος έχει μια τοπολογική ταξινόμηση κι αυτό συμβαίνει επειδή αυτό το είδος γραφημάτων δεν έχει κύκλους. Η τοπολογική ταξινόμηση ενός κατευθυνόμενου άκυκλου γράφου (δηλαδή με n κορυφές) γίνεται γραμμικά στο μέγεθος του γράφου.
Ευρεση συντομότερων διαδρομών από κοινή αφετηρία[Επεξεργασία | επεξεργασία κώδικα]
 |
Αυτό το λήμμα σχετικά με την Πληροφορική χρειάζεται επέκταση. Μπορείτε να βοηθήσετε την Βικιπαίδεια επεκτείνοντάς το. |