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

Βασική ορολογία

Ένα τόξο  κατευθύνεται από  το   προς  το . Το   ονομάζεται  κεφαλή και το  ονομάζεται ουρά του βέλους. Το  είναι ο  άμεσος απόγονος του , και το  είναι ο άμεσος πρόγονος του . Έαν υπάρχει ένα μονοπάτι από ένα ή περισσότερα διαδοχικά τόξα που συνδέει το  με το  , τότε λέμε ότι το  είναι  απόγονος του , και ότι το  είναι  πρόγονος του . Το τόξο  είναι το  ανεστραμμένο.
Ένας κατευθυνόμενος γράφος G ονομάζεται συμμετρικός αν, για κάθε τόξο που ανήκει στο G, το αντίστοιχο ανεστραμμένο τόξο ανήκει επίσης στο G. Ένας συμμετρικός κατευθυνόμενος γράφος που δεν περιέχει βρόχους είναι ισοδύναμος με έναν μη κατευθυνόμενο γράφο όπου κάθε ζευγάρι από ανεστραμμένα τόξα έχει αντικατασταθεί από μία ακμή. Έτσι ο αριθμός των ακμών του μη κατευθυνόμενου γράφου είναι  ίσος με το μισό του αριθμού των τόξων του κατευθυνόμενου γράφου.
Ένας  προσανατολισμός ενός απλού μη κατευθυνόμενου γράφου μπορεί να προκύψει αν προσθέσουμε σε κάθε ακμή του και μία κατεύθυνση.  Κάθε κατευθυνόμενος γράφος που προκύπτει με τον τρόπο αυτό ονομάζεται κατευθυνόμενος γράφος.  Μία διαφορά ανάμεσα σε έναν απλό κατευθυνόμενο γράφο και σε έναν προσανατολισμένο γράφο είναι ότι αν οι  και   είναι κορυφές, τότε σε έναν απλό κατευθυνόμενο γράφο επιτρέπεται να υπάρχουν και η ακμή  αλλά και  η ακμή  , ενώ σε έναν προσανατολισμένο γράφο επιτρέπεται να υπάρχει μόνο μία από τις ακμές αυτές.
Ένας  κατευθυνόμενος γράφος με βάρη είναι ένας κατευθυνόμενος γράφος στον οποίο έχουμε συσχετίσει με κάθε ακμή ένα βάρος.
Ένας κατευθυνόμενος γράφος με βάρη ονομάζεται δίκτυο.
Ο πίνακας γειτνίασης ενός κατευθυνόμενου γράφου (με βρόχους και πολλαπλά τόξα) είναι ένας πίνακας ακεραίων με γραμμές και στήλες που αντιστοιχούν στις κορυφές, όπου το στοιχείο  του πίνακα αντιστοιχεί στο πλήθος των τόξων από την κορυφή i στην κορυφή j, ενώ τα στοιχεία της διαγωνίου  αντιστοιχούν στον αριθμό των βρόχων της κορυφής i. 
Ένας άλλος πίνακας περιγραφής ενός κατευθυνόμενου γράφου είναι ο πίνακας αντιστοιχιών.

Η συνδεσιμότητα των κατευθυνόμενων γράφων

Ένας κατευθυνόμενος γράφος G ονομάζεται χαλαρά συνεκτικός (ή απλά συνεκτικός) εάν ο μη κατευθυνόμενος γράφος που προκύπτει αν αντικαταστήσουμε όλες τις κατευθυνόμενες ακμές του G με μη κατευθυνόμενες ακμές είναι ένας  συνεκτικός γράφος.  Ένας κατευθυνόμενος  γράφος είναι ισχυρά συνεκτικός εάν για κάθε ζευγάρι κορυφών u,v υπάρχει ένα κατευθυνόμενο μονοπάτι από την κορυφή u στην κορυφή v καθώς και ένα κατευθυνόμενο μονοπάτι από την κορυφή v στην κορυφή u.  Οι ισχυρές συνιστώσες ενός γράφου είναι τα μέγιστα ισχυρά συνεκτικά του υπογραφήματα.

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

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