background image

2.6

Συνδεδεμένο στοιχείο (Connected Component)

Στη θεωρία των γράϕων, ένα συνδεδεμένο στοιχείο ενός μη κατευθυνόμενου

γραϕήματος είναι ένα υπογράϕημα στο οποίο οποιεσδήποτε δύο κορυϕές συνδέο-

νται μεταξύ τους με μονοπάτια. Για παράδειγμα, το γράϕημα που παρουσιάζεται

στο σχήμα 2.3 έχει τρία συνδεδεμένα στοιχεία. Ένα γράϕημα που είναι συνδεδε-

μένο έχει ακριβώς ένα συνδεδεμένο στοιχείο, το οποίο αποτελείται από ολόκληρο

το γράϕημα.

Σχήμα 2.3: Ένα γράϕημα με τρία συνδεδεμένα συστατικά.

2.7

Ελάχιστο γεννητικό δέντρο (Minimum Spanning Tree)

Το ελάχιστο γεννητικό δέντρο (Minimum Spanning Tree, MST) ή γεννητικό δέ-

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

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

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

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

των ακμών του γράϕου είναι διάϕορα μεταξύ τους, τότε το ελάχιστο γεννητικό δέ-

ντρο του είναι μοναδικό. Διαϕορετικά, αν υπάρχουν ακμές με το ίδιο βάρος, τότε

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

2.4 ϕαίνεται σχηματικα το ελάχιστο γεννητικό δέντρο ενός γράϕου.

22