Δέντρο (θεωρία γράφων)

Δέντρο
Κορυφές
Ακμές
Χρωματικός αριθμός	2 (αν
Ιδιότητες	Διμερής γράφος
	Πίνακας γράφων και των παραμέτρων τους

Στην θεωρία γράφων, δέντρο είναι ένας μη-κατευθυνόμενος γράφος, στον οποίο οποιοιδήποτε δύο κόμβοι συνδέονται με ένα και μόνο απλό μονοπάτι. Με άλλα λόγια κάθε συνεκτικός γράφος χωρίς κύκλους είναι ένα δέντρο.^[1]^:13-16^[2]

Στην επιστήμη των υπολογιστών, πολλές δομές δεδομένων αναπαριστούν κατευθυνόμενα και μη-κατευθυνόμενα δέντρα.^[3]^[4]

Ισοδύναμοι ορισμοί δέντρου

Ένα δέντρο είναι ένας μη κατευθυνόμενος απλός γράφος G που ικανοποιεί οποιαδήποτε από τις παρακάτω ισοδύναμες συνθήκες:^[5]

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

Σχετικοί ορισμοί

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

Ένα δυαδικό δέντρο σχεδιασμένο έτσι, ώστε οι κορυφές που βρίσκονται στο ίδιο επίπεδο να βρίσκονται στην ίδια οριζόντια ευθεία. Η ρίζα βρίσκεται στο ανώτερο επίπεδο.

Ένα δέντρο ονομάζεται ριζωμένο εάν μία κορυφή έχει οριστεί ως ρίζα. Τότε λέμε ότι οι ακμές έχουν προσανατολισμό προς ή από τη ρίζα. Σε ένα ριζωμένο δέντρο, ο πατέρας μιας κορυφής είναι η αμέσως προηγούμενη κορυφή της διαδρομής από τη ρίζα σ' αυτήν. Κάθε κορυφή εκτός από τη ρίζα έχει ένα μοναδικό γονιό. Το παιδί μιας κορυφής είναι μια κορυφή της οποίας αυτή είναι πατέρας. Μία κορυφή χωρίς παιδιά λέγεται φύλλο. Μία τερματική κορυφή ενός δέντρου είναι μία κορυφή βαθμού 1. Σε ένα ριζωμένο δέντρο, όλα τα φύλλα είναι τερματικές κορυφές.

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

Ένα δάσος είναι ένας μη-κατευθυνόμενος γράφος, του οποίου όλες οι συνεκτικές συνιστώσες είναι δέντρα. Με άλλα λόγια, το δάσος αποτελείται από την ένωση ενός αριθμού ξένων μεταξύ τους δέντρων.

Ιδιότητες

Τα δέντρα είναι εξορισμού γράφοι συνεκτικοί και δεν περιέχουν κύκλους.
Κάθε δέντρο με $n$ κόμβους, έχει $n-1$ ακμές.
Κάθε δέντρο έχει τουλάχιστον έναν κόμβο βαθμού 1.

Χρωματισμός δέντρου με δύο χρώματα.

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

Σημαντικά είδη δέντρων

Αξίζει αναφορά σε συγκεκριμένα είδη δέντρων, καθώς εμφανίζονται συχνά σε εφαρμογές.

Δυαδικό δέντρο. Είναι δέντρα των οποίων κάθε κορυφή έχει το πολύ δύο παιδιά. Εμφανίζονται σε αλγόριθμους αναζήτησης, όπως η δυαδική αναζήτηση.
Β-Δέντρο. Πρόκειται για δομή δεδομένων που αποτελεί γενίκευση των δυαδικών δέντρων αναζήτησης. Κάθε κορυφή ενός Β-Δέντρου μπορεί να έχει πλήθος παιδιών ορισμένο σε ένα προκαθορισμένο εύρος. Αυτού του είδους τα δέντρα χρησιμοποιούνται στη κατασκευή ευρετηρίων για βάσεις δεδομένων.
Αστεροειδής γράφος. Γράφοι των οποίων ένας κόμβος είναι γειτονικός προς όλους τους υπόλοιπους και δεν υπάρχουν άλλες γειτνιάσεις. Αυτά τα γραφήματα χρησιμοποιούνται στη μοντελοποίηση δικτύων υπολογιστών με τοπολογία αστέρα.
Γράφος-μονοπάτι. Είναι γραφήματα των οποίων οι κόμβοι συνδέονται με ακμές σειριακά. Τα γραφήματα αυτά αποτελούν μονοπάτια.

Διάτρεξη δέντρων

Προδιατεταγμένη διάσχιση: Κ-Λ-Ζ-Α-Γ-Δ-Ι-Θ-Β-Ε-Η.
Μεταδιατεταγμένη διάσχιση: Ζ-Α-Λ-Δ-Θ-Β-Ι-Ε-Γ-Η-Κ.
Κατά επίπεδο: Κ-Λ-Γ-Η-Ζ-Α-Δ-Ι-Ε-Θ-Β

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

Προδιατεταγμένη διάσχιση

Κατά την προδιατεταγμένη διάσχιση, οι κόμβοι ενός δέντρου διατρέχονται με προτεραιότητα στον πατέρα έναντι του παιδιού. Ο κόμβος εκκίνησης είναι η ρίζα, ως πρόγονος όλων των κόμβων.

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

Μεταδιατεταγμένη διάσχιση

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

Διάταξη κατά επίπεδο

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

Η ενδοδιατεταγμένη διάσχιση στο παραπάνω δέντρο: Π-Α-Ρ-Α-Δ-Ε-Ι-Γ-Μ-Α.

Ενδοδιατεταγμένη διάσχιση

Στην ενδοδιατεταγμένη διάσχιση ενός δυαδικού δέντρου ο κόμβος εμφανίζεται στην διάταξη αφού πρώτα τελειώσει η διάσχιση στο αριστερό του παιδί (αν υπάρχει) και έπειτα συνεχίζει η διάσχιση στο δεξί του παιδί.

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

Δείτε επίσης

Δυαδικό δέντρο

Παραπομπές

↑ Diestel, Reinhard (2005). Graph Theory (3η έκδοση). Berlin, New York: Springer-Verlag. ISBN 978-3-540-26183-4.
↑ Flajolet, Philippe· Sedgewick, Robert (2009). Analytic Combinatorics. Cambridge University Press. ISBN 9780521898065.
↑ Μποζάνης, Παναγιώτης Δ. Δομές Δεδομένων. Εκδ. Τζιόλα.
↑ Knuth, Donald E. (1997). The Art of Computer Programming Volume 1: Fundamental Algorithms (3η έκδοση). Addison-Wesley Professional.
↑ Erickson, Jeff (2019). Algorithms (PDF). σελ. 207. ISBN 978-1792644832.

[1] Diestel, Reinhard (2005). Graph Theory (3η έκδοση). Berlin, New York: Springer-Verlag. ISBN 978-3-540-26183-4.

[2] Flajolet, Philippe· Sedgewick, Robert (2009). Analytic Combinatorics. Cambridge University Press. ISBN 9780521898065.

[3] Μποζάνης, Παναγιώτης Δ. Δομές Δεδομένων. Εκδ. Τζιόλα.

[4] Knuth, Donald E. (1997). The Art of Computer Programming Volume 1: Fundamental Algorithms (3η έκδοση). Addison-Wesley Professional.

[5] Erickson, Jeff (2019). Algorithms (PDF). σελ. 207. ISBN 978-1792644832.

[1]

[2]

[3]

[4]

[5]

Δέντρο

Κορυφές	$n$
Ακμές	$n-1$
Χρωματικός αριθμός	2 (αν $n\geq 2$
Ιδιότητες	Διμερής γράφος
Πίνακας γράφων και των παραμέτρων τους