Κατευθυνόμενος άκυκλος γράφος
Στην θεωρία γράφων, ένας γράφος ονομάζεται κατευθυνόμενος άκυκλος γράφος αν είναι κατευθυνόμενος και δεν περιέχει κύκλους, δηλαδή απλά μονοπάτια που ξεκινάνε και τελειώνουν στον ίδιο κόμβο.
Ένας κατευθυνόμενος άκυκλος γράφος μπορεί να χρησιμεύσει στη μοντελοποίηση διαφόρων δομών. Για παράδειγμα, μπορεί να μοντελοποιήσει εργασίες όπου κάποιες μπορούν να εκτελεστούν μόνο εφόσον όλες οι άλλες έχουν εκτελεστεί, ενός προγράμματος σπουδών όπου κάποια μαθήματα έχουν προαπαιτούμενα μαθήματα, ή μιας μερικής διάταξης στα στοιχεία ενός συνόλου.
Τοπολογική ταξινόμηση
ΕπεξεργασίαΚάθε κατευθυνόμενος άκυκλος γράφος έχει μια (ή παραπάνω) τοπολογικές ταξινομήσεις, δηλαδή υπάρχει μία διάταξη των κορυφών έτσι ώστε για κάθε ακμή στον γράφο, ισχύει ότι .[1]:612-615[2]:339-342
Υπάρχει αλγόριθμος που βρίσκει την τοπολογική ταξινόμηση σε χρόνο , όπου είναι το πλήθος των κόμβων και το πλήθος των ακμών.
Αλγοριθμικά προβλήματα
ΕπεξεργασίαΓια αρκετά υπολογιστικά προβλήματα, υπάρχουν αποδοτικοί αλγόριθμοι για κατευθυνόμενους άκυκλους γράφους, ενώ για γενικούς γράφους μόνο λιγότερο αποδοτικοί αλγόριθμοι είναι γνωστοί. Για παράδειγμα, το συντομότερο μονοπάτι μπορεί να βρεθεί σε χρόνο, ενώ σε γενικούς γράφους ο αλγόριθμος του Ντάικστρα είναι πιο αργός. Αντίστοιχα, το πρόβλημα της εύρεσης του μακρύτερου μονοπατιού μπορεί να βρεθεί σε χρόνο,[1]: 404 ενώ στην γενική περίπτωση είναι NP-Hard πρόβλημα.[1]: 1048
Δείτε επίσης
ΕπεξεργασίαΠαραπομπές
Επεξεργασία- ↑ 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.
- ↑ Τσίχλας, Κωνσταντίνος· Γούναρης, Αναστάσιος· Μανωλόπουλος, Ιωάννης. Σχεδίαση και ανάλυση αλγορίθμων.
Αυτό το μαθηματικό λήμμα χρειάζεται επέκταση. Μπορείτε να βοηθήσετε την Βικιπαίδεια επεκτείνοντάς το. |