Ελάχιστο γεννητικό δέντρο

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

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

Αλλιώς, το πρόβλημα μπορεί να διατυπωθεί ως πρόβλημα για την εύρεση ενός υποσυνόλου των ακμών του γραφήματος, ώστε το νέο υπογράφημα που προκύπτει να είναι συνεκτικό και το άθροισμα των βαρών των ακμών του να είναι το ελάχιστο δυνατό. Εδώ, δεν είναι σαφές αν η λύση του προβλήματος αποτελεί δέντρο. Όμως, αν το υπογράφημα που προκύπτει ως λύση έχει κύκλο, τότε αφαιρώντας μια ακμή από τον κύκλο (την βαρύτερη) το υπογράφημα παραμένει συνεκτικό και το άθροισμα των βαρών των ακμών του είναι ακόμη μικρότερο (αφού έχουμε αφαιρέσει μια ακμή). Επομένως, δεν γίνεται η λύση του προβλήματος να περιέχει κύκλο, γιατί τότε δεν θα έχει το ελάχιστο δυνατό άθροισμα βαρών. Και αφού επιπλέον το υπογράφημα πρέπει να είναι συνεκτικό, εξορισμού προκύπτει ότι η λύση θα είναι ένα δέντρο.

Ύπαρξη και μοναδικότητα

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

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

Αλγόριθμοι

Οι δύο γνωστότεροι αλγόριθμοι για την επίλυση αυτού του προβλήματος είναι ο αλγόριθμος του Prim και αυτός του Kruskal.