Τι είναι ένα προσανατολισμένο γράφο και ποια είναι τα χαρακτηριστικά του;

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

Χαρακτηριστικά:

• Κατευθυνόμενες ακμές: Η κίνηση κατά μήκος της ακμής είναι δυνατή μόνο σε μία κατεύθυνση, που υποδεικνύεται από ένα βέλος.
• Βαθμός κορυφής: Για ένα προσανατολισμένο γράφημα, ορίζεται ο εισερχόμενος βαθμός (ο αριθμός των ακμών που καταλήγουν στη κορυφή) και ο εξερχόμενος βαθμός (ο αριθμός των ακμών που ξεκινούν από τη κορυφή).
• Διαδρομές και κύκλοι: Μια διαδρομή είναι μια ακολουθία κορυφών που συνδέονται με ακμές στη σωστή κατεύθυνση. Ένας κύκλος είναι μια διαδρομή που ξεκινά και τελειώνει στην ίδια κορυφή. Τα προσανατολισμένα γράφημα μπορούν να περιέχουν προσανατολισμένους κύκλους.
• Συνδεσιμότητα: Διακρίνονται η αδύναμη συνδεσιμότητα (αγνοώντας τις κατευθύνσεις των ακμών, το γράφημα είναι συνδεδεμένο ως μη προσανατολισμένο) και η ισχυρή συνδεσιμότητα (για οποιαδήποτε δύο κορυφές A και B, υπάρχει προσανατολισμένη διαδρομή από A σε B και από B σε A).
• Παρουσίαση: Μπορούν να αναπαρασταθούν με λίστες γειτνίασης ή μήτρες γειτνίασης, όπου για ένα προσανατολισμένο γράφημα, η μήτρα γενικά δεν είναι συμμετρική.

Παράδειγμα αναπαράστασης με λίστα γειτνίασης:

# Γράφημα G = (V, E), όπου V = {0, 1, 2}, E = {(0, 1), (1, 2), (2, 0)}

graf = {
    0: [1],
    1: [2],
    2: [0]
}

Παράδειγμα αναπαράστασης με μήτρα γειτνίασης:

# Γράφημα G = (V, E), όπου V = {0, 1, 2}, E = {(0, 1), (1, 2), (0, 2)}

μήτρα = [
    [0, 1, 1],  # 0 -> 1, 0 -> 2
    [0, 0, 1],  # 1 -> 2
    [0, 0, 0]   # καμία έξοδος από το 2
]