Δομή Δεδομένων: Γράφοι (Graphs)

Θεωρία για τους Γράφους

Οι γράφοι (graphs) είναι μια μη γραμμική δομή δεδομένων που αποτελείται από ένα σύνολο κόμβων (vertices) και ακμών (edges) που συνδέουν τους κόμβους.

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

  • Κόμβοι και Ακμές: Οι γράφοι αποτελούνται από κόμβους και ακμές που συνδέουν τους κόμβους.
  • Κατευθυνόμενοι vs Μη Κατευθυνόμενοι:
    • Κατευθυνόμενοι Γράφοι: Οι ακμές έχουν κατεύθυνση (π.χ. από τον κόμβο Α στον κόμβο Β).
    • Μη Κατευθυνόμενοι Γράφοι: Οι ακμές δεν έχουν κατεύθυνση.
  • Βάρος Ακμών: Οι ακμές μπορούν να έχουν βάρη (π.χ. απόσταση μεταξύ δύο κόμβων).
  • Κύκλοι: Ένας γράφος μπορεί να περιέχει κύκλους (cycles).
  • Συνεκτικότητα: Ένας γράφος μπορεί να είναι συνεκτικός (όλοι οι κόμβοι είναι συνδεδεμένοι) ή μη συνεκτικός.

Βασικοί Όροι

  • Κόμβος (Vertex): Ένα βασικό στοιχείο του γράφου.
  • Ακμή (Edge): Μια σύνδεση μεταξύ δύο κόμβων.
  • Βαθμός Κόμβου (Degree): Ο αριθμός των ακμών που συνδέονται με έναν κόμβο.
  • Μονοπάτι (Path): Μια ακολουθία κόμβων όπου κάθε ζεύγος διαδοχικών κόμβων συνδέεται με μια ακμή.
  • Κύκλος (Cycle): Ένα μονοπάτι που ξεκινά και τελειώνει στον ίδιο κόμβο.
  • Συνεκτικός Γράφος (Connected Graph): Ένας γράφος όπου υπάρχει μονοπάτι μεταξύ οποιωνδήποτε δύο κόμβων.
  • Μη Κατευθυνόμενος Γράφος (Undirected Graph): Οι ακμές δεν έχουν κατεύθυνση.
  • Κατευθυνόμενος Γράφος (Directed Graph): Οι ακμές έχουν κατεύθυνση.

Αναπαράσταση Γράφων

  • Μήτρα Γειτνίασης (Adjacency Matrix):
    • Ένας πίνακας όπου κάθε κελί (i, j) δείχνει αν υπάρχει ακμή μεταξύ του κόμβου i και j.
    • Καλή για πυκνούς γράφους (πολλές ακμές).
  • Λίστα Γειτνίασης (Adjacency List):
    • Μια λίστα όπου κάθε κόμβος έχει μια λίστα με τους γειτονικούς του κόμβους.
    • Καλή για αραιούς γράφους (λίγες ακμές).

Εφαρμογές Γράφων

  • Δίκτυα υπολογιστών.
  • Δίκτυα κοινωνικής δικτύωσης.
  • Χάρτες και συστήματα πλοήγησης (π.χ. GPS).
  • Αλγόριθμοι βέλτιστου μονοπατιού (π.χ. Dijkstra, A*).
  • Διαχείριση εργασιών και πόρων.

Διάγραμμα Γράφου

Α
Β
Γ
Δ
Ε
Ζ

Παραστάσεις ενός μη κατευθυνόμενου γράφου με 6 κόμβους (Α, Β, Γ, Δ, Ε, Ζ).

Θεωρητικά Παραδείγματα Γράφων

Παραδείγματα Γράφων

Παρακάτω παρουσιάζονται θεωρητικά παραδείγματα γράφων και πώς μπορούν να χρησιμοποιηθούν.

Παράδειγμα 1: Δίκτυο Υπολογιστών

Ένας γράφος μπορεί να αναπαραστήσει ένα δίκτυο υπολογιστών, όπου οι κόμβοι είναι υπολογιστές και οι ακμές είναι συνδέσεις μεταξύ τους: 

          Υπολογιστής Α
         /   |   \
  Υπολογιστής Β  Υπολογιστής Γ  Υπολογιστής Δ
       \   / \   /
        Υπολογιστής Ε

Εδώ, οι υπολογιστές είναι συνδεδεμένοι μεταξύ τους μέσω καβελίων ή ασύρματων συνδέσεων.

Παράδειγμα 2: Δίκτυο Κοινωνικής Δικτύωσης

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

          Χρήστης Α
         /   |   \
  Χρήστης Β  Χρήστης Γ  Χρήστης Δ
       \   / \   /
        Χρήστης Ε

Εδώ, οι χρήστες είναι συνδεδεμένοι μέσω φιλιών.

Παράδειγμα 3: Χάρτης Πόλεων

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

          Αθήνα
         /   |   \
  Θήβα   Λάρισα   Βόλος
       \   / \   /
        Χαλκίδα

Εδώ, οι πόλεις είναι συνδεδεμένες μέσω δρόμων.

Παράδειγμα 4: Κατευθυνόμενος Γράφος

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

          Εργασία Α → Εργασία Β → Εργασία Γ
                          ↓
                       Εργασία Δ

Εδώ, οι εργασίες πρέπει να εκτελεστούν με την σειρά που δείχνουν τα βέλη.

Παράδειγμα 5: Γράφος με Βάρη

Ένας γράφος με βάρη στις ακμές μπορεί να αναπαραστήσει αποστάσεις μεταξύ πόλεων: 

          Αθήνα
         / |50km| \
  Θήβα(40km)   Λάρισα(100km)

Εδώ, οι ακμές έχουν βάρη που αναπαριστούν τις αποστάσεις μεταξύ των πόλεων.

Quiz

Ερώτηση 1: Ποιο είναι το βασικό στοιχείο ενός γράφου;

Ερώτηση 2: Ποια είναι η διαφορά μεταξύ ενός κατευθυνόμενου και ενός μη κατευθυνόμενου γράφου;

Ερώτηση 3: Ποιος από τους παρακάτω όρους περιγράφει έναν γράφο όπου υπάρχει μονοπάτι μεταξύ οποιωνδήποτε δύο κόμβων;

Ερώτηση 4 (Θεωρητική): Ποια είναι η διαφορά μεταξύ ενός δέντρου και ενός γράφου;

Ερώτηση 5 (Θεωρητική): Ποια από τις παρακάτω μεθόδους αναπαράστασης γράφων είναι πιο αποδοτική για πυκνούς γράφους;

Ερώτηση 6 (Θεωρητική): Ποιος από τους παρακάτω αλγορίθμους χρησιμοποιείται για την εύρεση του συντομότερου μονοπατιού σε έναν γράφο;

Ασκήσεις

Άσκηση 1: Να σχεδιάσετε έναν μη κατευθυνόμενο γράφο που να περιέχει τους ακόλουθους κόμβους και ακμές:
  • Κόμβοι: Α, Β, Γ, Δ, Ε
  • Ακμές: (Α, Β), (Α, Γ), (Β, Δ), (Γ, Δ), (Δ, Ε)
Στη συνέχεια, να καταγράψετε:
  1. Ποιος είναι ο βαθμός του κόμβου Δ;
  2. Υπάρχει κύκλος στον γράφο; Αν ναι, να τον καταγράψετε.
  3. Είναι ο γράφος συνεκτικός;
Άσκηση 2: Να σχεδιάσετε έναν κατευθυνόμενο γράφο που να περιέχει τους ακόλουθους κόμβους και ακμές:
  • Κόμβοι: Α, Β, Γ, Δ
  • Ακμές: (Α → Β), (Α → Γ), (Β → Δ), (Γ → Δ)
Στη συνέχεια, να καταγράψετε:
  1. Ποιος είναι ο βαθμός εισόδου και ο βαθμός εξόδου του κόμβου Α;
  2. Υπάρχει κύκλος στον γράφο; Αν ναι, να τον καταγράψετε.
  3. Είναι ο γράφος συνεκτικός;
Άσκηση 3: Να σχεδιάσετε έναν γράφο με βάρη που να περιέχει τους ακόλουθους κόμβους και ακμές:
  • Κόμβοι: Α, Β, Γ, Δ
  • Ακμές: (Α, Β, 5), (Α, Γ, 10), (Β, Δ, 3), (Γ, Δ, 7)
Στη συνέχεια, να καταγράψετε:
  1. Ποιο είναι το συντομότερο μονοπάτι από τον κόμβο Α στον κόμβο Δ;
  2. Ποιο είναι το συνολικό βάρος του συντομότερου μονοπατιού;
Άσκηση 4: Να σχεδιάσετε έναν γράφο που να αναπαριστά ένα δίκτυο πόλεων με τις ακόλουθες συνδέσεις:
  • Πόλεις: Αθήνα, Θήβα, Λάρισα, Βόλος, Χαλκίδα
  • Συνδέσεις: (Αθήνα, Θήβα), (Αθήνα, Λάρισα), (Αθήνα, Βόλος), (Θήβα, Χαλκίδα), (Λάρισα, Βόλος), (Λάρισα, Χαλκίδα)
Στη συνέχεια, να καταγράψετε:
  1. Ποιος είναι ο βαθμός του κόμβου Αθήνα;
  2. Υπάρχει κύκλος στον γράφο; Αν ναι, να τον καταγράψετε.
  3. Είναι ο γράφος συνεκτικός;

Animation: Γράφοι

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

Α Β Γ Δ Ε Ζ