Spanning Tree και Minimum Spanning Tree

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

Πριν μάθουμε για την έκταση των δέντρων, πρέπει να κατανοήσουμε δύο γραφήματα: μη κατευθυνόμενα γραφήματα και συνδεδεμένα γραφήματα.

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

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

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

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

Δέντρο που εκτείνεται

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

Οι άκρες μπορεί να έχουν ή όχι να έχουν βάρη.

Ο συνολικός αριθμός δέντρων με nκορυφές που μπορούν να δημιουργηθούν από ένα πλήρες γράφημα είναι ίσος με .n(n-2)

Αν έχουμε n = 4, ο μέγιστος αριθμός πιθανών δέντρων είναι ίσος με . Έτσι, μπορούν να σχηματιστούν 16 δέντρα που εκτείνονται από ένα πλήρες γράφημα με 4 κορυφές.44-2 = 16

Παράδειγμα ενός εκτεταμένου δέντρου

Ας καταλάβουμε το εκτεταμένο δέντρο με παραδείγματα παρακάτω:

Αφήστε το αρχικό γράφημα να είναι:

Κανονικό γράφημα

Μερικά από τα πιθανά δέντρα που μπορούν να δημιουργηθούν από το παραπάνω γράφημα είναι:

Ένα δέντρο που εκτείνεται Ένα δέντρο που εκτείνεται Ένα δέντρο που εκτείνεται Ένα δέντρο που εκτείνεται Ένα δέντρο που εκτείνεται Ένα δέντρο που εκτείνεται

Ελάχιστο δέντρο έκτασης

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

Παράδειγμα ενός εκτεταμένου δέντρου

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

Το αρχικό γράφημα είναι:

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

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

Ελάχιστο δέντρο έκτασης - 1 Ελάχιστο δέντρο έκτασης - 2 Ελάχιστο δέντρο έκτασης - 3 Ελάχιστο δέντρο έκτασης - 4

Το ελάχιστο δέντρο έκτασης από τα παραπάνω δέντρα είναι:

Ελάχιστο δέντρο έκτασης

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

1. Αλγόριθμος Prim
2. Αλγόριθμος του Kruskal

Εφαρμογές Spanning Tree

• Πρωτόκολλο δρομολόγησης δικτύου υπολογιστών
• Ανάλυση συμπλέγματος
• Πολιτικός σχεδιασμός δικτύων

Ελάχιστες Εφαρμογές Δένδρου

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