Σκατευθυνόμενο vs Μη κατευθυνόμενο γράφημα
Ένα γράφημα είναι μια μαθηματική δομή που αποτελείται από ένα σύνολο κορυφών και ακμών. Ένα γράφημα αντιπροσωπεύει ένα σύνολο αντικειμένων (που αντιπροσωπεύονται από κορυφές) που συνδέονται μέσω ορισμένων συνδέσμων (που αντιπροσωπεύονται από ακμές). Χρησιμοποιώντας μαθηματικούς συμβολισμούς, ένα γράφημα μπορεί να αναπαρασταθεί με G, όπου G=(V, E) και V είναι το σύνολο των κορυφών και E είναι το σύνολο των ακμών. Σε ένα μη κατευθυνόμενο γράφημα δεν υπάρχει κατεύθυνση που να σχετίζεται με τις ακμές που συνδέουν τις κορυφές. Σε ένα κατευθυνόμενο γράφημα υπάρχει μια κατεύθυνση που σχετίζεται με τις άκρες που συνδέουν τις κορυφές.
Μη κατευθυνόμενο γράφημα
Όπως αναφέρθηκε προηγουμένως, ένα μη κατευθυνόμενο γράφημα είναι ένα γράφημα στο οποίο δεν υπάρχει κατεύθυνση στις άκρες που συνδέουν τις κορυφές του γραφήματος. Το σχήμα 1 απεικονίζει ένα μη κατευθυνόμενο γράφημα με σύνολο κορυφών V={V1, V2, V3}. Το σύνολο ακμών στο παραπάνω γράφημα μπορεί να γραφτεί ως V={(V1, V2), (V2, V3), (V1, V3)}. Μπορεί επίσης να σημειωθεί ότι τίποτα δεν εμποδίζει να γράψουμε το σύνολο των ακμών ως V={(V2, V1), (V3, V2), (V3, V1)} αφού οι ακμές δεν έχουν κατεύθυνση. Επομένως, οι ακμές σε ένα μη κατευθυνόμενο γράφημα δεν είναι διατεταγμένα ζεύγη. Αυτό είναι το κύριο χαρακτηριστικό ενός μη κατευθυνόμενου γραφήματος. Τα μη κατευθυνόμενα γραφήματα μπορούν να χρησιμοποιηθούν για να αναπαραστήσουν συμμετρικές σχέσεις μεταξύ αντικειμένων που αντιπροσωπεύονται από κορυφές. Για παράδειγμα, ένα αμφίδρομο οδικό δίκτυο που συνδέει ένα σύνολο πόλεων μπορεί να αναπαρασταθεί χρησιμοποιώντας ένα μη κατευθυνόμενο γράφημα. Οι πόλεις μπορούν να αναπαρασταθούν από τις κορυφές στο γράφημα και οι ακμές αντιπροσωπεύουν τους αμφίδρομους δρόμους που συνδέουν τις πόλεις.
Κατευθυνόμενο γράφημα
Ένα κατευθυνόμενο γράφημα είναι ένα γράφημα στο οποίο οι ακμές του γραφήματος που συνδέουν τις κορυφές έχουν κατεύθυνση. Το σχήμα 2 απεικονίζει ένα κατευθυνόμενο γράφημα με σύνολο κορυφών V={V1, V2, V3}. Το σύνολο ακμών στο παραπάνω γράφημα μπορεί να γραφτεί ως V={(V1, V2), (V2, V3), (V1, V3)}. Οι ακμές σε ένα μη κατευθυνόμενο γράφημα είναι ταξινομημένα ζεύγη. Τυπικά, η ακμή e σε ένα κατευθυνόμενο γράφημα μπορεί να αναπαρασταθεί από το διατεταγμένο ζεύγος e=(x, y) όπου x είναι η κορυφή που ονομάζεται αρχή, πηγή ή το αρχικό σημείο της ακμής e και η κορυφή y ονομάζεται τέρμα, τερματική κορυφή ή τερματικό σημείο. Για παράδειγμα, ένα οδικό δίκτυο που συνδέει ένα σύνολο πόλεων χρησιμοποιώντας μονόδρομους δρόμους μπορεί να αναπαρασταθεί χρησιμοποιώντας ένα μη κατευθυνόμενο γράφημα. Οι πόλεις μπορούν να αναπαρασταθούν από τις κορυφές στο γράφημα και οι κατευθυνόμενες ακμές αντιπροσωπεύουν τους δρόμους που συνδέουν τις πόλεις λαμβάνοντας υπόψη την κατεύθυνση που ρέει η κυκλοφορία στο δρόμο.
Ποια είναι η διαφορά μεταξύ κατευθυνόμενου γραφήματος και μη κατευθυνόμενου γραφήματος;
Σε ένα κατευθυνόμενο γράφημα μια ακμή είναι ένα διατεταγμένο ζεύγος, όπου το διατεταγμένο ζεύγος αντιπροσωπεύει την κατεύθυνση της ακμής που συνδέει τις δύο κορυφές. Από την άλλη πλευρά, σε ένα μη κατευθυνόμενο γράφημα, μια ακμή είναι ένα μη ταξινομημένο ζεύγος, αφού δεν υπάρχει κατεύθυνση που να σχετίζεται με μια ακμή. Τα μη κατευθυνόμενα γραφήματα μπορούν να χρησιμοποιηθούν για να αναπαραστήσουν συμμετρικές σχέσεις μεταξύ αντικειμένων. Ο εσωτερικός και ο έξω βαθμός κάθε κόμβου σε ένα μη κατευθυνόμενο γράφημα είναι ίσοι, αλλά αυτό δεν ισχύει για ένα κατευθυνόμενο γράφημα. Όταν χρησιμοποιείται ένας πίνακας για την αναπαράσταση ενός μη κατευθυνόμενου γραφήματος, ο πίνακας γίνεται πάντα ένα συμμετρικό γράφημα, αλλά αυτό δεν ισχύει για τα κατευθυνόμενα γραφήματα. Ένα μη κατευθυνόμενο γράφημα μπορεί να μετατραπεί σε ένα κατευθυνόμενο γράφημα αντικαθιστώντας κάθε ακμή με δύο κατευθυνόμενες ακμές που πηγαίνουν σε αντίθετη κατεύθυνση. Ωστόσο, δεν είναι δυνατή η μετατροπή ενός κατευθυνόμενου γραφήματος σε μη κατευθυνόμενο γράφημα.
