Κεφάλαιο 2 Κατευθυνόμενα γραφήματα

Ένα κατευθυνόμενο γράφημα D είναι μια διατεταγμένη τριάδα (V(D) , A(D) , ψ_D ) , η οποία αποτελείται (i) από ένα σύνολο V(D), όπου V(D) , τα στοιχεία του οποίου ονομάζονται κορυφές, (ii) ένα σύνολο A(D) , όπου A(D) V(D) , τα στοιχεία του οποίου ονομάζονται τόξα και (iii) από μια συνάρτηση ψ_D , βάσει της οποίας σε κάθε τόξο του D αντιστοιχεί ένα διατεταγμένο ζεύγος κορυφών του D.
Κάθε κατευθυνόμενο γράφημα D μπορεί να απεικονισθεί ως εξής: Κάθε κορυφή απεικονίζεται μ' ένα σημείο στο επίπεδο και κάθε στοιχείο α του A(D) μ' ένα τόξο, το οποίο κατευθύνεται από την κορυφή x προς την κορυφή y, όπου ψ_D = ( x,y ). Έστω τόξο α και κορυφές x , y , έτσι ώστε ψ_D = ( x,y ). Τότε λέμε ότι η x αποτελεί την ουρά , ενώ η y την κεφαλή του α .
Ο έσω - βαθμός (u) μιας κορυφής u είναι ο αριθμός των τόξων που έχουν για κεφαλή την u, ενώ ο έξω-βαθμός (u) της u είναι ο αριθμός των τόξων που έχουν για ουρά την u. Ο ελάχιστος και μέγιστος έσω-βαθμός και έξω-βαθμός του D συμβολίζεται με δ^-( D ) , Δ^-( D ) και δ⁺( D ) , Δ⁺( D ) αντίστοιχα. Ο αριθμός των κορυφών του D συμβολίζεται με ν ( D ), ενώ ο αριθμός των τόξων με ε ( D ).
Ένας κατευθυνόμενος περίπατος στο D είναι μια πεπερασμένη ακολουθία W = u_oα₁u₁ . . . α_k u_k, της οποίας οι όροι είναι αλληλοδιαδόχως κορυφές και τόξα όπου i=1,2, . . . ,k το τόξο α_i έχει για κεφαλή την u_i και για ουρά την u_i-1. Ένας κατευθυνόμενος περίπατος ονομάζεται κλειστός, εάν έχει την ίδια κορυφή για αρχή και τέλος.
Κατευθυνόμενο μονοπάτι είναι ένας κατευθυνόμενος περίπατος του οποίου όλες οι κορυφές είναι διαφορετικές. Κατευθυνόμενο κύκλο ονομάζουμε ένα κλειστό κατευθυνόμενο περίπατο, όπου εκτός της ταύτισης αρχής και τέλους δεν παρατηρείται άλλη επανάληψη κορυφών.
Θεώρημα 2.1: Για κάθε κατευθυνόμενο γράφημα D ισχύει ότι

Απόδειξη: Κάθε τόξο "συνεισφέρει" τον αριθμό 1 στον έξω-βαθμό της ουράς του και τον αριθμό 1 στον έσω-βαθμό της κεφαλής του. Άρα

Ασκήσεις στην Θεωρία Γραφημάτων

Προηγούμενο

Ευρετήριο