Διαφορά μεταξύ κατεύθυνσης και μη κατευθυνόμενου γραφήματος

Κατεύθυνση έναντι κατεύθυνσης

Ένα γράφημα είναι μια μαθηματική δομή που αποτελείται από σύνολο κορυφών και άκρων. Ένα γράφημα αντιπροσωπεύει ένα σύνολο αντικειμένων (που αντιπροσωπεύονται από κορυφές) που συνδέονται μέσω ορισμένων συνδέσμων (που αντιπροσωπεύονται από άκρα). Χρησιμοποιώντας μαθηματικές σημειώσεις, ένα γράφημα μπορεί να αναπαρασταθεί από το 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 ονομάζεται τερματικό, τερματικό σημείο ή σημείο τερματισμού. Για παράδειγμα, ένα οδικό δίκτυο που συνδέει ένα σύνολο πόλεων που χρησιμοποιούν δρόμους μονής κατεύθυνσης μπορεί να αναπαρασταθεί χρησιμοποιώντας ένα μη κατευθυνόμενο γράφημα. Οι πόλεις μπορούν να εκπροσωπούνται από τις κορυφές του γραφήματος και οι κατευθυντήριες άκρες αντιπροσωπεύουν τους δρόμους που συνδέουν τις πόλεις, λαμβάνοντας υπόψη την κατεύθυνση που η κυκλοφορία ρέει στο δρόμο.

Ποια είναι η διαφορά μεταξύ του Κατευθυνόμενου Γράφου και του Μη Καθοδηγούμενου Γράφου;

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