Κατευθυνόμενος γράφος
γράφος με προσανατολισμένες ακμές / From Wikipedia, the free encyclopedia
Οι γράφοι είναι μαθηματικές κατασκευές χρήσιμες για τη μοντελοποίηση αντικειμένων που με κάποιο τρόπο σχετίζονται μεταξύ τους. Τα αντικείμενα απεικονίζονται από τους κόμβους του γράφου και οι ακμές του απεικονίζουν τις σχέσεις που έχουν τα αντικείμενα αυτά μεταξύ τους. Για παράδειγμα, ένας γράφος μπορεί να μοντελοποιεί ένα δίκτυο υπολογιστών, όπου τα αντικείμενα είναι οι υπολογιστές και οι σχέσεις μεταξύ τους είναι οι διασυνδέσεις μεταξύ των υπολογιστών, ή ένα οδικό δίκτυο μιας περιοχής, όπου οι κόμβοι του γραφήματος απεικονίζουν τις πόλεις και οι ακμές μεταξύ των κόμβων απεικονίζουν την ύπαρξη δρόμου που συνδέει άμεσα δύο πόλεις.
Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. |
Σε κάποιες περιπτώσεις, οι σχέσεις μεταξύ των αντικειμένων είναι αμφίδρομες. Για παράδειγμα, σε ένα γράφημα που μοντελοποιεί ένα δίκτυο γνωριμιών, οι κόμβοι του γράφου απεικονίζουν ανθρώπους και οι ακμές του απεικονίζουν γνωριμία μεταξύ δύο ανθρώπων. Προφανώς, αν ο Νίκος γνωρίζει την Άννα, τότε και η Άννα γνωρίζει το Νίκο, επομένως η έννοια της κατεύθυνσης δεν έχει νόημα στην περίπτωση των γνωριμιών. Για τέτοιους σκοπούς, χρησιμοποιούνται μη κατευθυνόμενα γραφήματα.
Σε άλλες περιπτώσεις, οι σχέσεις μεταξύ των αντικειμένων δεν είναι αμφίδρομες και έχει νόημα η κατεύθυνση της σχέσης που τα συνδέει. Μια τέτοια περίπτωση, για παράδειγμα, είναι μια ροή εργασιών. Ή το σύνολο των τηλεφωνημάτων που έγιναν σε κάποια περιοχή για μια χρονική ζώνη είναι επίσης μία περίπτωση όπου η κατεύθυνση έχει νόημα: αν ο Νίκος πήρε τηλέφωνο την Άννα, αυτό δεν σημαίνει απαραίτητα ότι κι η Άννα πήρε τηλέφωνο το Νίκο. Στις περιπτώσεις αυτές, χρησιμοποιούνται κατευθυνόμενα γραφήματα.