Κατευθυνόμενος γράφος

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

Οι γράφοι είναι μαθηματικές κατασκευές χρήσιμες για τη μοντελοποίηση αντικειμένων που με κάποιο τρόπο σχετίζονται μεταξύ τους. Τα αντικείμενα απεικονίζονται από τους κόμβους του γράφου και οι ακμές του απεικονίζουν τις σχέσεις που έχουν τα αντικείμενα αυτά μεταξύ τους. Για παράδειγμα, ένας γράφος μπορεί να μοντελοποιεί ένα δίκτυο υπολογιστών, όπου τα αντικείμενα είναι οι υπολογιστές και οι σχέσεις μεταξύ τους είναι οι διασυνδέσεις μεταξύ των υπολογιστών, ή ένα οδικό δίκτυο μιας περιοχής, όπου οι κόμβοι του γραφήματος απεικονίζουν τις πόλεις και οι ακμές μεταξύ των κόμβων απεικονίζουν την ύπαρξη δρόμου που συνδέει άμεσα δύο πόλεις.

Σε κάποιες περιπτώσεις, οι σχέσεις μεταξύ των αντικειμένων είναι αμφίδρομες. Για παράδειγμα, σε ένα γράφημα που μοντελοποιεί ένα δίκτυο γνωριμιών, οι κόμβοι του γράφου απεικονίζουν ανθρώπους και οι ακμές του απεικονίζουν γνωριμία μεταξύ δύο ανθρώπων. Προφανώς, αν ο Νίκος γνωρίζει την Άννα, τότε και η Άννα γνωρίζει το Νίκο, επομένως η έννοια της κατεύθυνσης δεν έχει νόημα στην περίπτωση των γνωριμιών. Για τέτοιους σκοπούς, χρησιμοποιούνται μη κατευθυνόμενα γραφήματα.

Σε άλλες περιπτώσεις, οι σχέσεις μεταξύ των αντικειμένων δεν είναι αμφίδρομες και έχει νόημα η κατεύθυνση της σχέσης που τα συνδέει. Μια τέτοια περίπτωση, για παράδειγμα, είναι μια ροή εργασιών. Ή το σύνολο των τηλεφωνημάτων που έγιναν σε κάποια περιοχή για μια χρονική ζώνη είναι επίσης μία περίπτωση όπου η κατεύθυνση έχει νόημα: αν ο Νίκος πήρε τηλέφωνο την Άννα, αυτό δεν σημαίνει απαραίτητα ότι κι η Άννα πήρε τηλέφωνο το Νίκο. Στις περιπτώσεις αυτές, χρησιμοποιούνται κατευθυνόμενα γραφήματα.

Ορισμός

Ένας κατευθυνόμενος γράφος είναι ένα ζευγάρι $G=(V,A)$ (ή $G=(V,E)$) από:

• ένα σύνολο V, του οποίου τα στοιχεία καλούνται κορυφές ή κόμβοι,
• ένα σύνολο A από διατεταγμένα ζεύγη κορυφών, που ονομάζονται τόξα, κατευθυνόμενες ακμές ή βέλη.

Διαφέρει από έναν μη κατευθυνόμενο γράφο στο ότι ο τελευταίος αποτελείται από ένα σύνολο μη διατεταγμένων ζευγών από κορυφές, οι οποίες ονομάζονται συνήθως ακμές.

Βασική ορολογία

Ένα τόξο $e=(x,y)$ κατευθύνεται από το $x$ προς το $y$. Το $y$ ονομάζεται κεφαλή και το $x$ ονομάζεται ουρά του βέλους. Το $y$ είναι ο άμεσος απόγονος του $x$, και το $x$ είναι ο άμεσος πρόγονος του $y$. Έαν υπάρχει ένα μονοπάτι από ένα ή περισσότερα διαδοχικά τόξα που συνδέει το $x$ με το $y$, τότε λέμε ότι το $y$ είναι απόγονος του $x$, και ότι το $x$ είναι πρόγονος του $y$. Το τόξο $(y,x)$ είναι το $(x,y)$ ανεστραμμένο.

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

Ένας προσανατολισμός ενός απλού μη κατευθυνόμενου γράφου μπορεί να προκύψει αν προσθέσουμε σε κάθε ακμή του και μία κατεύθυνση. Κάθε κατευθυνόμενος γράφος που προκύπτει με τον τρόπο αυτό ονομάζεται κατευθυνόμενος γράφος. Μία διαφορά ανάμεσα σε έναν απλό κατευθυνόμενο γράφο και σε έναν προσανατολισμένο γράφο είναι ότι αν οι $x$ και $y$ είναι κορυφές, τότε σε έναν απλό κατευθυνόμενο γράφο επιτρέπεται να υπάρχουν και η ακμή $(x,y)$ αλλά και η ακμή $(y,x)$ , ενώ σε έναν προσανατολισμένο γράφο επιτρέπεται να υπάρχει μόνο μία από τις ακμές αυτές.

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

Ο πίνακας γειτνίασης ενός κατευθυνόμενου γράφου (με βρόχους και πολλαπλά τόξα) είναι ένας πίνακας ακεραίων με γραμμές και στήλες που αντιστοιχούν στις κορυφές, όπου το στοιχείο $a_{ij}$ του πίνακα αντιστοιχεί στο πλήθος των τόξων από την κορυφή i στην κορυφή j, ενώ τα στοιχεία της διαγωνίου $a_{ii}$ αντιστοιχούν στον αριθμό των βρόχων της κορυφής i. Ένας άλλος πίνακας περιγραφής ενός κατευθυνόμενου γράφου είναι ο πίνακας αντιστοιχιών.

Βαθμός εισόδου και βαθμός εξόδου

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

Για κάθε κορυφή, ο αριθμός των τόξων που καταλήγουν στην κορυφή ονομάζεται βαθμός εισόδου της κορυφής, ενώ ο αριθμός των τόξων που ξεκινούν από την κορυφή ονομάζεται βαθμός εξόδου.

Ο βαθμός εισόδου συμβολίζεται $\deg ^{-}(v)$ και ο βαθμός εξόδου $\deg ^{+}(v).$ Μία κορυφή με $\deg ^{-}(v)=0$ ονομάζεται πηγή (source), καθώς ξεκινούν από αυτήν όλες οι γειτονικές της ακμές. Παρόμοια, μία κορυφή με $\deg ^{+}(v)=0$ ονομάζεται καταβόθρα (sink).

Ο τύπος του αθροίσματος των βαθμών, για έναν κατευθυνόμενο γράφο είναι,

$\sum _{v\in V}\deg ^{+}(v)=\sum _{v\in V}\deg ^{-}(v)=|A|\,.$

Εάν για κάθε κορυφή $v$, $\deg ^{+}(v)=\deg ^{-}(v)$, τότε ο γράφος ονομάζεται ισορροπημένος κατευθυνόμενος γράφος.

Η συνδεσιμότητα των κατευθυνόμενων γράφων

Ένας κατευθυνόμενος γράφος G ονομάζεται χαλαρά συνεκτικός (ή απλά συνεκτικός) εάν ο μη κατευθυνόμενος γράφος που προκύπτει αν αντικαταστήσουμε όλες τις κατευθυνόμενες ακμές του G με μη κατευθυνόμενες ακμές είναι ένας συνεκτικός γράφος. Ένας κατευθυνόμενος γράφος είναι ισχυρά συνεκτικός εάν για κάθε ζευγάρι κορυφών u,v υπάρχει ένα κατευθυνόμενο μονοπάτι από την κορυφή u στην κορυφή v καθώς και ένα κατευθυνόμενο μονοπάτι από την κορυφή v στην κορυφή u. Οι ισχυρές συνιστώσες ενός γράφου είναι τα μέγιστα ισχυρά συνεκτικά του υπογραφήματα.

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

Ένας απλός κατευθυνόμενος άκυκλος γράφος

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

Αναφορές

• Bang-Jensen, Jørgen; Gutin, Gregory (2000), Digraphs: Theory, Algorithms and Applications, Springer, ISBN 1-85233-268-9, http://www.cs.rhul.ac.uk/books/dbook/ 
  (the corrected 1st edition of 2007 is now freely available on the authors' site; the 2nd edition appeared in 2009 ISBN 1848009976).
• Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, ISBN 0-444-19451-7, http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html, ανακτήθηκε στις 2012-01-08 .
• Diestel, Reinhard (2005), Graph Theory (3rd έκδοση), Springer, ISBN 3-540-26182-6, http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/  (the electronic 3rd edition is freely available on author's site).
• Harary, Frank; Norman, Robert Z.; Cartwright, Dorwin (1965), Structural Models: An Introduction to the Theory of Directed Graphs, New York: Wiley .
• Number of directed graphs (or digraphs) with n nodes., http://oeis.org/A000273