Στα γραϕήματα που οι ακμές αποτελούνται απο απλές γραμμές χωρίς κατευ-

θύνσεις και δεν περιέχονται βρόγχοι, δηλαδή ακμές με αρχή και τέλος την ίδια

κορυϕή, το γράϕημα ονομάζεται μη κατευθυνόμενο. Ωστόσο, σε ορισμένες σχέσεις

η ύπαρξη κατευθύνσεων από μια κορυϕή σε μια άλλη είναι απαραίτητη. Σε αυ-

τές τις περιπτώσεις η ιδιότητα των κατευθύνσεων προστίθεται στις ακμές και το

γράϕημα ονομάζεται κατευθυνόμενο. Οι ακμές επίσης μπορούν να συσχετιστούν με

αριθμούς οι οποίοι καλούνται βάρη. Τα γραϕήματα που περιέχουν τέτοιες ακμές

ανήκουν στην κατηγορία των βεβαρημένων γραϕημάτων.

2.5

Δενδρική δομή

Στη θεωρία γραϕημάτων, ως δενδρική δομή ή δέντρο ορίζεται ένα συνεκτικό

και μη κατευθυνόμενο γράϕημα το οποίο δεν περιέχει κύκλους. Η δενδρική δόμή

είναι ένας τρόπος να παραστήσουμε γραϕικά την ιεραρχία μιας δομής. Είναι η δομή

δεδομένων που αποτελείται από ένα σύνολο κόμβων που συνδέονται με ακμές. Σε

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

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

διακλαδόνονται περαιτέρω ονομάζονται ϕύλλα του δέντρου. Οι κόμβοι μεταξύ τους

έχουν σχέσεις γονιού - παιδιού. Κάθε παιδί έχει μόνον ένα γονιό. Στο σχήμα 2.2

εμϕανίζεται ένα παράδειγμα ενός δέντρου.

Σχήμα 2.2: Παράδειγμα ενός δέντρου. Ο κόμβος Α αποτελεί την ρίζα του δέντρου.

21