Ένα ελάχιστο εκτεινόμενο δέντρο ή ένα δέντρο που εκτείνεται ελάχιστου βάρους είναι ένα υποσύνολο των άκρων ενός συνδεδεμένου, μη κατευθυνόμενου γραφήματος με στάθμιση των ακμών που συνδέει όλες τις κορυφές μεταξύ τους, χωρίς κύκλους και με το ελάχιστο δυνατό συνολικό βάρος ακμής. Δηλαδή, είναι ένα εκτεινόμενο δέντρο του οποίου το άθροισμα των βαρών των άκρων είναι όσο το δυνατόν μικρότερο.
Τι είναι το ελάχιστο εκτεινόμενο δέντρο με παράδειγμα;
Ένα δέντρο ελάχιστης έκτασης είναι ένα ειδικό είδος δέντρου που ελαχιστοποιεί τα μήκη (ή τα «βάρη») των άκρων του δέντρου. Ένα παράδειγμα είναι μια εταιρεία καλωδίων που θέλει να κάνει γραμμή σε πολλές γειτονιές; ελαχιστοποιώντας την ποσότητα του καλωδίου που έχει τοποθετηθεί, η εταιρεία καλωδίων θα εξοικονομήσει χρήματα. Ένα δέντρο έχει ένα μονοπάτι που ενώνει οποιεσδήποτε δύο κορυφές.
Πώς βρίσκετε το ελάχιστο εκτεινόμενο δέντρο;
Βρείτε τον πλησιέστερο άχρωμο γείτονα στον κόκκινο υπογράφο (δηλαδή, την πλησιέστερη κορυφή σε οποιαδήποτε κόκκινη κορυφή). Σημειώστε το και την άκρη που συνδέει την κορυφή με το κόκκινο υπογράφημα με κόκκινο χρώμα. Επαναλάβετε το Βήμα 2 έως ότου όλες οι κορυφές σημειωθούν με κόκκινο χρώμα. Το κόκκινο υπογράφημα είναι ένα ελάχιστο εκτεινόμενο δέντρο.
Τι εννοείτε με τον όρο spanning tree και minimal spanning tree;
Ένα εκτεινόμενο δέντρο ενός γραφήματος είναι μια συλλογή από συνδεδεμένες ακμές που περιλαμβάνουν κάθε κορυφή του γραφήματος, αλλά δεν σχηματίζουν κύκλο. … Το ελάχιστο δέντρο που καλύπτει είναι αυτό του οποίου τα σωρευτικά βάρη άκρων έχουν τη μικρότερη τιμή, ωστόσο.
Ποια είναι η διαφορά μεταξύ ενός εκτεινόμενου δέντρου και ενός ελάχιστου δέντρου που εκτείνεται;
Αν το γράφημα είναιμε στάθμιση των άκρων, μπορούμε να ορίσουμε το βάρος ενός δέντρου που εκτείνεται ως το άθροισμα των βαρών όλων των άκρων του. Ένα ελάχιστο δέντρο που εκτείνεται είναι ένα δέντρο που καλύπτει το βάρος του οποίου είναι το μικρότερο από όλα τα δυνατά δέντρα που εκτείνονται.
