Ελάχιστο γεννητικό δέντρο
Ένας αριθμός προβλημάτων από τη θεωρία γραφημάτων ονομάζεται Ελάχιστο δέντρο διάσχισης. Στη θεωρία γραφημάτων, ένα δέντρο είναι ένας τρόπος σύνδεσης όλων των κορυφών μεταξύ τους, έτσι ώστε να υπάρχει ακριβώς ένα μονοπάτι από οποιαδήποτε κορυφή, σε οποιαδήποτε άλλη κορυφή του δέντρου. Αν το γράφημα αναπαριστά έναν αριθμό πόλεων που συνδέονται με δρόμους, θα μπορούσε κανείς να επιλέξει έναν αριθμό δρόμων, έτσι ώστε κάθε πόλη να είναι προσβάσιμη από κάθε άλλη, αλλά να μην υπάρχουν περισσότεροι από ένας δρόμοι για να ταξιδέψει κανείς από τη μία πόλη στην άλλη.
Ένας γράφος μπορεί να έχει περισσότερα από ένα δέντρα, όπως ακριβώς μπορεί να υπάρχουν περισσότεροι από ένας τρόποι επιλογής των δρόμων μεταξύ των πόλεων.
Τις περισσότερες φορές, τα γραφήματα είναι σταθμισμένα- κάθε σύνδεση μεταξύ δύο πόλεων έχει ένα βάρος: μπορεί να κοστίζει κάτι να ταξιδέψει κανείς σε έναν συγκεκριμένο δρόμο, ή μια σύνδεση μπορεί να είναι μεγαλύτερη από την άλλη, πράγμα που σημαίνει ότι χρειάζεται περισσότερος χρόνος για να ταξιδέψει κανείς σε αυτή τη σύνδεση. Στη γλώσσα της θεωρίας γραφημάτων, οι συνδέσεις ονομάζονται ακμές.
Ένα ελάχιστο δέντρο είναι ένα δέντρο. Διαφέρει από τα άλλα δέντρα στο ότι ελαχιστοποιεί το σύνολο των βαρών που συνδέονται με τις ακμές. Ανάλογα με τη μορφή του γραφήματος, μπορεί να υπάρχουν περισσότερα από ένα ελάχιστα δέντρα. Σε ένα γράφημα όπου όλες οι ακμές έχουν το ίδιο βάρος, κάθε δέντρο είναι ένα ελάχιστο δένδρο. Εάν όλες οι ακμές έχουν διαφορετικά βάρη (δηλαδή: δεν υπάρχουν δύο ακμές με το ίδιο βάρος), υπάρχει ακριβώς ένα ελάχιστο δένδρο.
Το ελάχιστο δέντρο κάλυψης ενός επίπεδου γραφήματος. Κάθε ακμή επισημαίνεται με το βάρος της, το οποίο εδώ είναι περίπου ανάλογο του μήκους της.
Εύρεση του ελάχιστου δέντρου εξάπλωσης
Μια πρώτη προσπάθεια
Μπορεί να είναι πολύ απλό να φτιάξετε έναν αλγόριθμο που θα ανακαλύψει ένα ελάχιστο δέντρο:
συνάρτηση MST(G,W): T = {} ενώ το T δεν σχηματίζει δένδρο διάσχισης: βρείτε την ελάχιστη σταθμισμένη ακμή στο E που είναι ασφαλής για το T T = T union {(u,v)} return TΣε αυτή την περίπτωση, "ασφαλές" σημαίνει ότι η συμπερίληψη της ακμής δεν σχηματίζει κύκλο στο γράφημα. Κύκλος σημαίνει ότι ξεκινάμε από μια κορυφή, ταξιδεύουμε σε έναν αριθμό άλλων κορυφών και καταλήγουμε ξανά στο σημείο εκκίνησης χωρίς να χρησιμοποιήσουμε την ίδια ακμή δύο φορές.
Ιστορία
Ο Τσέχος επιστήμονας Otakar Borůvka ανέπτυξε τον πρώτο γνωστό αλγόριθμο για την εύρεση ενός ελάχιστου δέντρου, το 1926. Ήθελε να λύσει το πρόβλημα της εύρεσης μιας αποτελεσματικής κάλυψης της Μοραβίας με ηλεκτρικό ρεύμα. Σήμερα, ο αλγόριθμος αυτός είναι γνωστός ως αλγόριθμος του Borůvka. Δύο άλλοι αλγόριθμοι χρησιμοποιούνται συνήθως σήμερα. Ο ένας από αυτούς αναπτύχθηκε από τον Vojtěch Jarník το 1930 και τέθηκε σε εφαρμογή από τον Robert Clay Prim το 1957. Ο Edsger Wybe Dijkstra τον ανακάλυψε εκ νέου το 1959 και τον ονόμασε αλγόριθμο του Prim. Ο άλλος αλγόριθμος ονομάζεται αλγόριθμος του Kruskal και αναπτύχθηκε από τον Joseph Kruskal το 1956. Και οι τρεις αλγόριθμοι είναι άπληστοι και εκτελούνται σε πολυωνυμικό χρόνο.
Ο γρηγορότερος αλγόριθμος ελάχιστου δέντρου που έχει αναπτυχθεί μέχρι σήμερα αναπτύχθηκε από τον Bernard Chazelle. Ο αλγόριθμος βασίζεται στον μαλακό σωρό, μια προσεγγιστική ουρά προτεραιότητας. Ο χρόνος λειτουργίας του είναι O(m α(m,n)), όπου m είναι ο αριθμός των ακμών, n είναι ο αριθμός των κορυφών και α είναι η κλασική αντίστροφη συνάρτηση Ackermann. Η συνάρτηση α αυξάνεται εξαιρετικά αργά, έτσι ώστε για όλους τους πρακτικούς σκοπούς μπορεί να θεωρηθεί σταθερά όχι μεγαλύτερη από 4. Έτσι, ο αλγόριθμος του Chazelle χρειάζεται πολύ κοντά σε γραμμικό χρόνο.
Ποιος είναι ο ταχύτερος δυνατός αλγόριθμος για το πρόβλημα αυτό; Αυτό είναι ένα από τα παλαιότερα ανοικτά ερωτήματα στην επιστήμη των υπολογιστών. Υπάρχει σαφώς ένα γραμμικό κατώτερο όριο, αφού πρέπει τουλάχιστον να εξετάσουμε όλα τα βάρη. Εάν τα βάρη των ακμών είναι ακέραιοι αριθμοί με περιορισμένο μήκος bit, τότε είναι γνωστοί ντετερμινιστικοί αλγόριθμοι με γραμμικό χρόνο εκτέλεσης. Για γενικά βάρη, υπάρχουν τυχαιοποιημένοι αλγόριθμοι των οποίων ο αναμενόμενος χρόνος εκτέλεσης είναι γραμμικός.
Το πρόβλημα μπορεί επίσης να προσεγγιστεί με κατανεμημένο τρόπο. Αν κάθε κόμβος θεωρείται υπολογιστής και κανένας κόμβος δεν γνωρίζει τίποτα άλλο εκτός από τους δικούς του συνδεδεμένους συνδέσμους, μπορεί κανείς να υπολογίσει το κατανεμημένο ελάχιστο δένδρο.
Ερωτήσεις και απαντήσεις
Ερ: Τι είναι το ελάχιστο δέντρο διάσχισης στη θεωρία γραφημάτων;
A: Ένα ελάχιστο δένδρο που εκτείνεται είναι ένα δέντρο που ελαχιστοποιεί τα συνολικά βάρη που συνδέονται με τις ακμές στη θεωρία γραφημάτων.
Ερ: Τι είναι ένα δέντρο στη θεωρία γραφημάτων;
A: Ένα δέντρο είναι ένας τρόπος σύνδεσης όλων των κορυφών μεταξύ τους στη θεωρία γραφημάτων, έτσι ώστε να υπάρχει μόνο ένα μονοπάτι από οποιαδήποτε κορυφή σε οποιαδήποτε άλλη κορυφή του δέντρου.
Ερ: Ποιος είναι ο σκοπός της επιλογής δρόμων σε ένα σενάριο της θεωρίας γράφων που αναπαριστά πόλεις;
Α: Ο σκοπός της επιλογής δρόμων σε ένα σενάριο της θεωρίας γράφων που αναπαριστά πόλεις είναι να καταστεί δυνατή η πρόσβαση σε κάθε πόλη από κάθε άλλη πόλη, αλλά με όχι περισσότερους από έναν πιθανούς τρόπους για να ταξιδέψει κανείς από τη μία πόλη στην άλλη.
Ερ: Μπορεί ένας γράφος να έχει περισσότερα από ένα δέντρα διάσχισης;
Α: Ναι, ένας γράφος μπορεί να έχει περισσότερα από ένα δέντρα διάσχισης.
Ερ: Ποια είναι η διαφορά μεταξύ ενός ελάχιστου δέντρου διάσχισης και άλλων δέντρων στη θεωρία γραφημάτων;
Α: Ένα ελάχιστο δένδρο διασποράς ελαχιστοποιεί τα συνολικά βάρη που συνδέονται με τις ακμές, ενώ άλλα δένδρα δεν έχουν αυτό το χαρακτηριστικό.
Ερ: Τι είναι οι ακμές στη θεωρία γραφημάτων;
Α: Οι ακμές είναι οι συνδέσεις μεταξύ δύο κορυφών στη θεωρία γραφημάτων.
Ερ: Μπορούν να υπάρχουν περισσότερα από ένα ελάχιστα δέντρα σε ένα γράφημα με διαφορετικές σταθμισμένες ακμές;
Α: Ναι, ανάλογα με το πώς μοιάζει ο γράφος, μπορεί να υπάρχουν περισσότερα από ένα ελάχιστα δέντρα.
