Κατευθυνόμενος άκυκλος γράφος

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Ένα παράδειγμα ενός κατευθυνόμενου άκυκλου γράφου.

Στην θεωρία γράφων, ένας γράφος ονομάζεται κατευθυνόμενος άκυκλος γράφος αν είναι κατευθυνόμενος και δεν περιέχει κύκλους, δηλαδή απλά μονοπάτια που ξεκινάνε και τελειώνουν στον ίδιο κόμβο.

Ένας κατευθυνόμενος άκυκλος γράφος μπορεί να χρησιμεύσει στη μοντελοποίηση διαφόρων δομών. Για παράδειγμα, μπορεί να μοντελοποιήσει εργασίες όπου κάποιες μπορούν να εκτελεστούν μόνο εφόσον όλες οι άλλες έχουν εκτελεστεί, ενός προγράμματος σπουδών όπου κάποια μαθήματα έχουν προαπαιτούμενα μαθήματα, ή μιας μερικής διάταξης στα στοιχεία ενός συνόλου.

Τοπολογική ταξινόμηση[Επεξεργασία | επεξεργασία κώδικα]

Κάθε κατευθυνόμενος άκυκλος γράφος έχει μια (ή παραπάνω) τοπολογικές ταξινομήσεις, δηλαδή υπάρχει μία διάταξη των κορυφών έτσι ώστε για κάθε ακμή στον γράφο, ισχύει ότι .[1]:612-615[2]:339-342

Υπάρχει αλγόριθμος που βρίσκει την τοπολογική ταξινόμηση σε χρόνο , όπου είναι το πλήθος των κόμβων και το πλήθος των ακμών.

Αλγοριθμικά προβλήματα[Επεξεργασία | επεξεργασία κώδικα]

Για αρκετά υπολογιστικά προβλήματα, υπάρχουν αποδοτικοί αλγόριθμοι για κατευθυνόμενους άκυκλους γράφους, ενώ για γενικούς γράφους μόνο λιγότερο αποδοτικοί αλγόριθμοι είναι γνωστοί. Για παράδειγμα, το συντομότερο μονοπάτι μπορεί να βρεθεί σε χρόνο, ενώ σε γενικούς γράφους ο αλγόριθμος του Ντάικστρα είναι πιο αργός. Αντίστοιχα, το πρόβλημα της εύρεσης του μακρύτερου μονοπατιού μπορεί να βρεθεί σε χρόνο,[1]: 404  ενώ στην γενική περίπτωση είναι NP-Hard πρόβλημα.[1]: 1048 

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. 1,0 1,1 1,2 Cormen, Thomas H.· Leiserson, Charles Eric· Rivest, Ronald Linn· Stein, Clifford. Introduction to algorithms (3η έκδοση). Cambridge, Massachusetts London, England: MIT Press. ISBN 9780262033848. 
  2. Τσίχλας, Κωνσταντίνος· Γούναρης, Αναστάσιος· Μανωλόπουλος, Ιωάννης. Σχεδίαση και ανάλυση αλγορίθμων.