Δέντρο (θεωρία γράφων): Διαφορά μεταξύ των αναθεωρήσεων

|header2 =

|label2 = Dewey

|header3 =

|label3 = MSC2010

|header4 =

|label4 =

}}

[[Image:Tree graph.svg|180px|thumb|Ένα δέντρο με 6 κορυφές και 5 πλευρές]]

 

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

== Ορισμοί ==

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

*Ο ''G'' είναι συνεκτικός, αλλά παύει να είναι αν αφαιρεθεί έστω και μία ακμή του.

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

== Παράδειγμα ==

* [[Donald E. Knuth]]. ''The Art of Computer Programming Volume 1: Fundamental Algorithms''. Addison-Wesley Professional; 3rd edition (November 14, 1997).

 

 

[[cs:Strom (graf)]]