Δέντρο (Θεωρία Γράφων)

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση
Δέντρο (Θεωρία Γράφων)
Ταξινόμηση
Dewey 512
MSC2010 05Cxx
Ένα δέντρο με 6 κορυφές και 5 πλευρές

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

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

Ορισμοί[Επεξεργασία | επεξεργασία κώδικα]

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

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

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

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

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

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

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

Ιδιότητες[Επεξεργασία | επεξεργασία κώδικα]

Τα δέντρα είναι εξορισμού γράφοι συνεκτικοί και δεν περιέχουν κύκλους. Συνέπεια των ιδιοτήτων αυτών είναι ότι αν ένα δέντρο έχει n κορυφές, τότε έχει n-1 ακμές. Επιπλέον, κάθε δέντρο έχει τουλάχιστον έναν κόμβο βαθμού 1. Βαθμός ενός κόμβου είναι το πλήθος των προσκείμενων σ' αυτόν ακμών.

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

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

Σημαντικά είδη δέντρων[Επεξεργασία | επεξεργασία κώδικα]

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

Διάτρεξη δέντρων[Επεξεργασία | επεξεργασία κώδικα]

Προδιάταξη: A-B-D-F-C-G-E. Μεταδιάταξη: D-F-B-G-E-C-A. Κατά επίπεδο: A-B-C-E-D-F-G

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

Προδιάταξη[Επεξεργασία | επεξεργασία κώδικα]

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

Μεταδιάταξη[Επεξεργασία | επεξεργασία κώδικα]

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

Διάταξη κατά επίπεδο[Επεξεργασία | επεξεργασία κώδικα]

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

Αναφορές[Επεξεργασία | επεξεργασία κώδικα]

Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Tree (graph theory) της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).