Δέντρο (θεωρία γράφων): Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Vevek (συζήτηση | συνεισφορές) |
Vevek (συζήτηση | συνεισφορές) μ →Ορισμοί: τυπογραφικό |
||
Γραμμή 46:
'''Δάσος''' είναι ένας μη κατευθυνόμενος γράφος, του οποίου όλες οι [[Γράφος#Συνεκτικότητα και συνιστώσες|συνεκτικές συνιστώσες]] είναι δέντρα. Με άλλα λόγια, το δάσος αποτελείται από την ένωση ενός αριθμού ξένων μεταξύ τους δέντρων. Ένα [[πολυδέντρο]] ή ένα προσανατολισμένο δέντρο είναι ένας κατευθυνόμενος γράφος με το πολύ ένα μη-κατευθυνόμενο μονοπάτι μεταξύ δύο οποιωνδήποτε κορυφών. Δηλαδή ένα προσανατολισμένο δέντρο είναι ένας [[Κατευθυνόμενος Άκυκλος Γράφος|άκυκλος κατευθυνόμενος γράφος]]. Ένα κατευθυνόμενο δέντρο προκύπτει όταν από ένα [[Κατευθυνόμενος Γράφος|κατευθυνόμενο γράφο]] αφαιρέσουμε τις κατευθύνεσεις των ακμών του.
[[File:ArbolCompleto.jpg|thumb|left|Ένα [[δυαδικό δέντρο]] σχεδιασμένο έτσι, ώστε οι κορυφές που βρίσκονται στο ίδιο επίπεδο να βρίσκονται στην ίδια
Οι κόμβοι ενός δέντρου μπορούν να χωριστούν σε '''επίπεδα''', με την έννοια ότι κόμβοι που απέχουν το ίδιο από τη ρίζα βρίσκονται στο ίδιο επίπεδο. Πιο αυστηρά, όλοι οι κόμβοι των οποίων τα μονοπάτια από τη ρίζα προς αυτά έχουν το ίδιο μήκος, ανήκουν στο ίδιο επίπεδο.
|