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

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

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

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

*Ο ''G'' είναι '''συνεκτικός''' και δεν έχει '''κύκλους'''.

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

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

'''Δάσος''' είναι ένας μη κατευθυνόμενος γράφος, του οποίου όλες οι '''[[Γράφος#Συνεκτικότητα και συνιστώσες|συνεκτικές συνιστώσες''']] είναι δέντρα. Με άλλα λόγια, οτο γράφοςδάσος αποτελείται από την ένωση ενός αριθμού ξένων μεταξύ τους δέντρων. Ένα '''[[πολυδέντρο''']] ή ένα '''προσανατολισμένο δέντρο''' είναι ένας κατευθυνόμενος γράφος με το πολύ ένα μη-κατευθυνόμενο μονοπάτι μεταξύ δύο οποιωνδήποτε κορυφών. Δηλαδή ένα πολυδέντροπροσανατολισμένο δέντρο είναι ένας '''[[Κατευθυνόμενος Άκυκλος Γράφος|άκυκλος κατευθυνόμενος γράφος''']]. Ένα κατευθυνόμενο δέντρο προκύπτει όταν από ένα [[Κατευθυνόμενος Γράφος|κατευθυνόμενο γράφο]] αφαιρέσουμε τις κατευθύνεσεις των ακμών του.

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