Τύποι γραφημάτων στη δομή δεδομένων με παραδείγματα

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

Τα γραφήματα μπορούν να είναι πολλαπλών τύπων, ανάλογα με τη θέση των κόμβων και των ακμών. Ακολουθούν ορισμένοι σημαντικοί τύποι Γραφημάτων:

Σκηνοθετημένη Γράφημα

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

Ακολουθεί ένα παράδειγμα του Directed Graph.

• Μπορούμε να πάμε από τον Κόμβο Α στον Δ.
• Ωστόσο, δεν μπορούμε να πάμε από τον κόμβο D στον κόμβο A καθώς η άκρη δείχνει από το A στο D.
• Καθώς το γράφημα δεν έχει βάρη, το ταξίδι από την κορυφή Α στο D θα κοστίσει το ίδιο με το ταξίδι από το D στο F.

Μη κατευθυνόμενο γράφημα

Το μη κατευθυνόμενο γράφημα περιέχει άκρες χωρίς δείκτες. Σημαίνει ότι μπορούμε να ταξιδέψουμε αντίστροφα μεταξύ δύο κορυφών.

Ακολουθεί ένα απλό παράδειγμα του μη κατευθυνόμενου γραφήματος.

Στο παραπάνω γράφημα,

• Μπορούμε να μετακινηθούμε από το Α στο Β
• Μπορούμε επίσης να μετακινηθούμε από το Β στο Α
• Οι άκρες δεν περιέχουν οδηγίες.

Είναι ένα παράδειγμα μη κατευθυνόμενου γραφήματος που έχει πεπερασμένο αριθμό κορυφών και ακμών χωρίς βάρη.

Σταθμισμένο γράφημα

Το γράφημα που περιέχει βάρη ή κόστη στις άκρες ονομάζεται σταθμισμένο γράφημα. Η αριθμητική τιμή αντιπροσωπεύει γενικά το κόστος μετακίνησης από μια κορυφή σε μια άλλη κορυφή. Τόσο το Directed όσο και το Undirected Graph μπορούν να έχουν βάρη στις άκρες τους.

Ακολουθεί ένα παράδειγμα σταθμισμένου γραφήματος (κατευθυνόμενο).

• Το Α στο Β, υπάρχει μια άκρη και το βάρος είναι 5, που σημαίνει ότι η μετακίνηση από το Α στο Β θα μας κοστίσει 5.
• Ένα σημείο στο Β, αλλά σε αυτό το γράφημα, το Β δεν έχει άμεση ακμή έναντι του Α. Επομένως, δεν μπορούμε να ταξιδέψουμε από το Β στο Α.
• Ωστόσο, εάν θέλουμε να μετακινηθούμε από το Α στο F, υπάρχουν πολλαπλά μονοπάτια. Τα μονοπάτια είναι ADF, ABF. Ο ADF θα κοστίζει (10+11) ή 21.
• Εδώ, η διαδρομή ABF θα κοστίζει (5+15) ή 20. Εδώ προσθέτουμε το βάρος κάθε άκρου στη διαδρομή.

Ακολουθεί ένα παράδειγμα μη κατευθυνόμενου γραφήματος με βάρη:

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

Γράφημα διπλής κατεύθυνσης

Τα αμφίδρομα και τα μη κατευθυνόμενα γραφήματα έχουν μια κοινή ιδιότητα. Αυτό είναι

• Γενικά, το μη κατευθυνόμενο Γράφημα μπορεί να έχει ένα άκρο μεταξύ δύο κορυφών.

Για παράδειγμα:

• Εδώ, η μετακίνηση από το Α στο Δ ή το Δ στο Α θα κοστίσει 10.
• Σε ένα αμφίδρομο γράφημα, μπορούμε να έχουμε δύο ακμές μεταξύ δύο κορυφών.

Εδώ είναι ένα παράδειγμα:

Το να ταξιδέψουμε από το Α στο Δ θα μας κοστίσει 17, αλλά το να ταξιδέψουμε από το Δ στο Α θα μας κοστίσει 12. Επομένως, δεν μπορούμε να εκχωρήσουμε δύο διαφορετικά βάρη εάν είναι ένα μη κατευθυνόμενο γράφημα.

Άπειρο γράφημα

Το Γράφημα θα περιέχει έναν άπειρο αριθμό ακμών και κόμβων. Εάν ένα γράφημα είναι Άπειρο και είναι επίσης ένα συνδεδεμένο γράφημα, τότε θα περιέχει επίσης έναν άπειρο αριθμό ακμών. Εδώ, οι εκτεταμένες ακμές σημαίνουν ότι περισσότερες άκρες μπορεί να συνδεθούν σε αυτούς τους κόμβους μέσω ακμών.

Ακολουθεί ένα παράδειγμα του άπειρου γραφήματος:

Μηδενικό γράφημα

Το Null Graph περιέχει μόνο κόμβους ή κορυφές αλλά χωρίς ακμές. Αν δοθεί ένα γράφημα G = (V, E), όπου V είναι κορυφές και E είναι ακμές, θα είναι μηδενικό εάν ο αριθμός των ακμών E είναι μηδέν.

Ακολουθεί ένα παράδειγμα μηδενικού γραφήματος:

Ασήμαντο γράφημα

Μια δομή δεδομένων γραφήματος θεωρείται ασήμαντη εάν υπάρχει μόνο μία κορυφή ή κόμβος χωρίς ακμές.

Ακολουθεί ένα παράδειγμα ενός ασήμαντου γραφήματος:

Πολλαπλό γράφημα

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

Ακολουθεί ένα παράδειγμα πολλαπλού γραφήματος:

Υπάρχουν δύο άκρες από το Β έως το Α. Επιπλέον, η κορυφή Ε έχει έναν αυτο-βρόχο. Το παραπάνω γράφημα είναι ένα κατευθυνόμενο γράφημα χωρίς βάρη στις άκρες.

Πλήρες γράφημα

Ένα γράφημα είναι πλήρες εάν κάθε κορυφή έχει κατευθυνόμενες ή μη κατευθυνόμενες ακμές με όλες τις άλλες κορυφές.

Ας υποθέσουμε ότι υπάρχει ένας συνολικός αριθμός V κορυφών και κάθε κορυφή έχει ακριβώς ακμές V-1. Τότε, αυτό το γράφημα θα ονομάζεται Πλήρες Γράφημα. Σε αυτόν τον τύπο γραφήματος, κάθε κορυφή συνδέεται με όλες τις άλλες κορυφές μέσω ακμών.

Ακολουθεί ένα παράδειγμα πλήρους γραφήματος με πέντε κορυφές:

Μπορείτε να δείτε στην εικόνα ότι ο συνολικός αριθμός των κόμβων είναι πέντε και όλοι οι κόμβοι έχουν ακριβώς τέσσερις άκρες.

Συνδεδεμένο γράφημα

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

Ακολουθεί ένα παράδειγμα συνδεδεμένου γραφήματος:

Ακολουθεί κάποια εξήγηση του παραπάνω γραφήματος «πλήρους παραδείγματος γραφήματος»:

• Υποθέτοντας ότι δεν υπάρχει ακμή μεταξύ C και F, δεν μπορούμε να ταξιδέψουμε από το A στο G. Ωστόσο, η ακμή C στο F μας δίνει τη δυνατότητα να ταξιδέψουμε σε οποιονδήποτε κόμβο από έναν δεδομένο κόμβο.
• Ένα πλήρες Γράφημα είναι ένα Συνδεδεμένο Γράφημα επειδή μπορούμε να μετακινηθούμε από έναν κόμβο σε οποιονδήποτε άλλο κόμβο στο δεδομένο Γράφημα.

Κυκλικό Γράφημα

Ένα γράφημα λέγεται ότι είναι κυκλικό εάν υπάρχουν ένας ή περισσότεροι κύκλοι στο γράφημα.

Ακολουθεί ένα παράδειγμα κυκλικού γραφήματος:

Εδώ, οι κορυφές Α, Β και Γ σχηματίζουν έναν κύκλο.

Ένα γράφημα μπορεί να έχει πολλούς κύκλους μέσα του.

Κατευθυνόμενο ακυκλικό γράφημα (DAG)

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

Ακολουθεί ένα απλό παράδειγμα Κατευθυνόμενου Ακυκλικού Γραφήματος (DAG):

Γράφημα κύκλου

Το κυκλικό γράφημα δεν είναι το ίδιο με το κυκλικό γράφημα. Στο Cycle Graph, κάθε κόμβος θα έχει ακριβώς δύο άκρες συνδεδεμένες, που σημαίνει ότι κάθε κόμβος θα έχει ακριβώς δύο μοίρες.

Ακολουθεί ένα παράδειγμα γραφήματος κύκλου:

Διμερές γράφημα

Αυτά τα είδη Διαγράμματα είναι ειδικά είδη Γραφημάτων όπου οι κορυφές εκχωρούνται σε δύο σύνολα.

Το διμερές γράφημα πρέπει να ακολουθεί τον κανόνα:

• Δύο σύνολα κορυφών πρέπει να είναι διακριτά, πράγμα που σημαίνει ότι όλες οι κορυφές πρέπει να χωριστούν σε δύο ομάδες ή σύνολα.
• Οι κορυφές του ίδιου συνόλου δεν πρέπει να σχηματίζουν ακμές.

Γράφημα Euler

Οι δομές δεδομένων γραφημάτων θεωρούνται Γράφημα Euler εάν όλες οι κορυφές έχουν ζυγό βαθμό. Ο όρος βαθμός κορυφών σημαίνει τον αριθμό των ακμών που δείχνουν ή δείχνουν από μια συγκεκριμένη κορυφή.

Ακολουθεί ένα παράδειγμα γραφήματος Euler:

Όλες οι κορυφές έχουν ζυγές μοίρες. Οι κορυφές Α, Δ, Ε και Η έχουν δύο μοίρες. Εδώ, ο κόμβος C έχει τέσσερις μοίρες, οι οποίες είναι άρτιες.

Γράφημα Hamilton

Το Hamilton Graph είναι ένα Γράφημα Connect, όπου μπορείτε να επισκεφθείτε όλες τις κορυφές από μια δεδομένη κορυφή χωρίς να επισκεφτείτε ξανά τον ίδιο κόμβο ή να χρησιμοποιήσετε την ίδια άκρη. Αυτό το είδος Συνδεδεμένου Γραφήματος είναι γνωστό ως «Γράφημα Χάμιλτον». Η διαδρομή που επισκέπτεστε για να επαληθεύσετε εάν το δεδομένο Γράφημα είναι Γράφημα Χάμιλτον ή όχι είναι γνωστό ως Διαδρομή Χάμιλτον.

Ακολουθεί ένα απλό παράδειγμα γραφήματος ενός Hamilton:

Σε αυτήν την εικόνα, μπορούμε να επισκεφτούμε όλες τις κορυφές από οποιονδήποτε κόμβο στο παραπάνω Γράφημα. Ένα από τα μονοπάτια μπορεί να είναι ADCHBE. Είναι επίσης δυνατό να βρείτε έναν κύκλο Hamilton. Ο Κύκλος Χάμιλτον ξεκινά και τελειώνει στην ίδια κορυφή. Έτσι, θα είναι ο Κύκλος Χάμιλτον ADCHBEA.