Θεωρία γράφων
πεδίο των μαθηματικών που μελετά γράφους, δηλαδή μαθηματικές δομές που αναπαριστούν τις σχέσεις μεταξύ αντικειμένων / From Wikipedia, the free encyclopedia
Η θεωρία γράφων (ή θεωρία γραφημάτων) είναι το πεδίο των διακριτών μαθηματικών που μελετάει γράφους (ή γραφήματα), δομές που αναπαριστούν σχέσεις μεταξύ αντικείμενων. Πιο συγκεκριμένα, οι γράφοι αποτελούνται από ένα σύνολο κόμβων (ή κορυφών) και ένα σύνολο ακμών που συνδέουν κάποιους από τους κόμβους μεταξύ τους. Ανάλογα με την δομή που αναπαριστούν, οι ακμές μπορεί να έχουν διεύθυνση οδηγώντας σε κατευθυνόμενους ή μη κατευθυνόμενους γράφους, αντίστοιχα.
Οι γράφοι βρίσκουν αρκετές εφαρμογές στην πληροφορική, στις επιστήμες μηχανικών, στη χημεία, στην κοινωνιολογία κ.α. Για παράδειγμα, στα συστήματα πλοήγησης το οδικό δίκτυο μοντελοποιείται ως γράφος, όπου οι δρόμοι είναι οι ακμές και διασταυρώσεις είναι οι κόμβοι. Σε αυτόν τον γράφο, χρησιμοποιώντας διάφορους αλγορίθμους όπως αυτός του Ντάικστρα, μπορεί να βρει κανείς το συντομότερο μονοπάτι μεταξύ δύο σημείων.
Ένα άλλο παράδειγμα είναι οι σχέσεις φιλίας σε ένα κοινωνικό δίκτυο (όπως το Facebook) που μπορούν να αναπαρασταθούν ως ένας (μη κατευθυνόμενος) γράφος, όπου οι κόμβοι είναι οι χρήστες και οι ακμές δηλώνουν αν υπάρχει φιλία μεταξύ τους. Σε άλλα δίκτυα όπως το X, ο γράφος μεταξύ των ακόλουθων είναι κατευθυνόμενος, καθώς ο χρήστης Γιώργος μπορεί να ακολουθεί την Μαρία, αλλά η Μαρία μπορεί να μην ακολουθεί τον Γιώργο.
Αν και οι απαρχές της θεωρίας γράφων θεμελιώθηκαν κατά τον 18ο αιώνα, αναπτύχθηκε μετά τον δεύτερο παγκόσμιο πόλεμο ως ξεχωριστό πεδίο των εφαρμοσμένων μαθηματικών.[1]:vii Ο κλάδος της πληροφορικής ασχολήθηκε με την ανάπτυξη γρήγορων αλγορίθμων (δηλαδή αυτοματοποιημένων διαδικασιών), που επιτρέπουν την επίλυση ορισμένων προβλημάτων σε γράφους, όπως αυτό της εύρεσης του συντομότερου μονοπατιού μεταξύ δύο κόμβων.
Στην ελληνική ορολογία οι όροι θεωρία γραφημάτων και θεωρία γράφων χρησιμοποιούνται ως ισοδύναμοι. Προτιμάται ο όρος γράφος, για να διακρίνεται από το γράφημα συνάρτησης. Ανάμεσα στους ποικίλους ορισμούς που απαντώνται, ένας σχετικά πλήρης ορίζει πως η θεωρία γράφων είναι η μελέτη των γράφων (γραφημάτων) και των σχέσεών τους.