θεωρία γράφων

Γράφος (Graph)

Γράφος είναι το διατεταγμένο ζεύγος G = (V, E), όπου V σύνολο σημείων και E διμελής σχέση πάνω στο V.

G = ({α, β, γ}, {{α, β}, {β, γ}})

Κορυφές (Vertices, Nodes)

Τα στοιχεία του V καλούνται κορυφές ή κόμβοι.

V(G) = {α, β, γ}

Ακμές (Edges)

Τα στοιχεία του Ε καλούνται ακμές οι οποίες είναι γραμμές και κάθε γραμμή συνδέει δύο στοιχεία του συνόλου V. Για παράδειγμα (V1, V2).

Ε(G) = {{α, β}, {β, γ}}

Ισχύει:

Ε(G) ⊆ {{u, v} : u, v ∈ V(G)}

Παρακείμενες κορυφές (Adjacent)

Δυο κορυφές λέγονται παρακείμενες εφόσον υπάρχει ακμή που να συνδέει αυτές.

Βρόχος (Loop)

Μια ακμή που έχει την ίδια κορυφή ως αρχή και τέλος καλείται βρόγχος.

Κατευθυνόμενος γράφος (Directed graph)

Όταν όλα τα στοιχεία του Ε είναι διατεταγμένα ζεύγη (v1, v2), ο γράφος ονομάζεται κατευθυνόμενος (ή προσανατολισμένος) γράφος.

Μη κατευθυνόμενος γράφος

Όταν όλα τα στοιχεία του Ε είναι μη διατεταγμένα ζεύγη {v1, v2}, ο γράφος ονομάζεται μη κατευθυνόμενος γράφος.

Ψευδογράφος (pseudograph)

Γράφος που περιέχει πολλαπλές ακμές ή/και βρόγχους.

Συνεκτικός (connected)

Ένας ψευδογράφος καλείται συνεκτικός (connected), αν κάθε ζεύγος κορυφών του vi, vj μπορεί να συνδεθεί με μια διαδρομή.

Τάξη (order)

Ο αριθμός των κορυφών ενός γράφου καλείται τάξη (order) του γράφου.

n = |V(G)|

Βαθμός κορυφής

Είναι ο αριθμός που εκφράζει το πλήθος των παρακείμενων κορυφών.

degG(v) = |NG(v)|

Δ(G) και δ(G) εκφράζουν μέγιστο και ελάχιστο βαθμό κορυφής σε ένα γράφο G.

Μέγεθος (size)

Είναι ο συνολικός αριθμός των ακμών ενός γράφου.

Πλήρης γράφος

Ονομάζεται ο γράφος του οποίου κάθε κορυφή είναι παρακείμενη σε όλες τις άλλες.

Κλίκα (clique)

Κλίκα ενός γράφου έστω G καλείται ένας υπογράφος έστω Q που είναι πλήρης.

Περίπατος (Walk)

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

Διαδρομή (path)

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

Μονοπάτι (trail)

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

Μήκος διαδρομής

Ο αριθμός των ακμών που περιλαμβάνει μια διαδρομή.

Κλειστή διαδρομή

Η διαδρομή της οποίας η αρχή και το τέλος συμπίπτουν στην ίδια κορυφή.

Κύκλωμα (Circuit)

Είναι μια διαδρομή που: α) είναι κλειστή και β) μία ή περισσότερες κορυφές μπορεί να επαναλαμβάνονται.

Κύκλος (Cycle)

Ένα κύκλωμα που καμία κορυφή της διαδρομής δεν επαναλαμβάνεται (κλειστό μονοπάτι).

ή ισοδύναμα:

Κύκλος είναι ένα μονοπάτι (trail) όπου οι κορυφές που επαναλαμβάνονται είναι η πρώτη και η τελευταία.

Δένδρο (tree)

Τα δένδρα είναι μη κατευθυνόμενοι άκυκλοι συνδεδεμένοι γράφοι.

ή ισοδύναμα:

Ένας μη κατευθυνόμενος γράφος που δύο κορυφές είναι συνδεδεμένες με ακριβώς μια διαδρομή.

Δάσος (forest)

Δάσος είναι ένας γράφος που έχει ως συνιστώσες δένδρα.

Δένδρα με Αφετηρία

Ένα δένδρο με αφετηρία είναι ένα δένδρο του οποίου μια κορυφή έχει ονομαστεί αφετηρία, ή ρίζα.

Δυαδικό δένδρο (binary tree)

Δυαδικό (binary) καλείται ένα δένδρο του οποίου κάθε κορυφή έχει το πολύ δυο τέκνα.

Φύλλο (leaf)

Μια κορυφή έστω v ενός δέντρου T καλείται φύλλο όταν: degΤ(v) = 1.