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

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

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

Γράφος 

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

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

Τυπολογικά παραδείγματα

Μη κατευθυνόμενος γράφος 
Ως μαθηματική έκφραση, ο ορισμός του μη κατευθυνόμενου γράφου έχει ως εξής:

Ο γράφος G είναι ένα διατεταγμένο ζεύγος G=<V(G), E(G)> όπου:
 V(G)={v1,v2...vn} το σύνολο των κορυφών,
 E(G)={e1,e2...em} το σύνολο των ακμών.

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

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

Ως μαθηματική έκφραση, ο ορισμός του κατευθυνόμενου γράφου έχει ως εξής:

Ο γράφος G είναι ένα διατεταγμένο ζεύγος G=(V(G), E(G)) όπου:
 V(G)={v1,v2...vn} το σύνολο των κορυφών,
 E(G)={e1,e2...em} το σύνολο των ακμών.

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

Βαθμός κορυφής (degvi ) 
Βαθμός (deg) της κορυφής vi  είναι ο αριθμός που εκφράζει το πλήθος των ακμών που καταλήγουν σε αυτήν την κορυφή.

Διαδρομή 
Σε ένα συνεκτικό γράφο, διαδρομή καλείται ένα υποσύνολο κορυφών V'(G)={v1,v2...vm}, m≤n , με 0 < deg vi ≤ 2. Στην ελληνική βιβλιογραφία η διαδρομή αναφέρεται και ως μονοπάτι από την αγγλική λέξη path.

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

Ιστορία της θεωρίας γράφων 

Για την ιστορία της θεωρίας γράφων θεωρείται σημαντική η μελέτη του Λέοναρντ Όιλερ για τις Επτά Γέφυρες του Κένιγκσμπεργκ το 1736  Η συγκεκριμένη δημοσίευση, όπως και εκείνη που γράφτηκε από τον Γάλλο χημικό Αλεξάντρ-Τεοφίλ Βαντερμόντ (Alexandre-Théophile Vandermonde) στο μαθηματικό πρόβλημα του Ίππου στη σκακιέρα που κατευθύνεται με την ανάλυση θέσης που εισήγαγε ο Γκότφριντ Βίλχελμ Λάιμπνιτς. Ο τύπος του Όιλερ, σχετικά με τον αριθμό των ακμών, των κορυφών και των εδρών ενός κυρτού πολυέδρου μελετήθηκε από τον Ωγκυστέν-Λουί Κωσύ και τον Σιμόν Αντουάν Ζαν Λ' Ουιγιέ (Simon Antoine Jean L'Huillier) και είναι αρχή της τοπολογίας.

Σχεδόν εκατό χρόνια μετά τη μελέτη του Όιλερ και την εισαγωγή της τοπολογίας από τον Γιόχαν Μπένεντικτ Λίστινγκ (Johann Benedict Listing), ο Άρθουρ Κέιλι (Arthur Cayley) μελέτησε μια ιδιαίτερη κατηγορία γράφων, τα δέντρα. Η μελέτη αυτών των ιδιαίτερων γράφων είχε πολλές εφαρμογές στη θεωρητική χημεία. Οι τεχνικές που αναπτύχθηκαν είχαν να κάνουν κυρίως με την απαρίθμηση γράφων που παρουσίαζαν κάποιες ιδιαίτερες ιδιότητες. Η απαριθμητική θεωρία γράφων ήταν ένα από τα συμπεράσματα του Κέιλι και δημοσιεύτηκε από τον (Γκιόργκι) Τζορτζ Πόλια (George Pólya) μεταξύ των ετών 1935 και 1937, ενώ η γενίκευση των συμπερασμάτων εκδόθηκε από τον Νίκλας Γκόβερτ ντε Μπρούιν (Nicolaas Govert de Bruijn) το 1959. Ο Κέιλι συνέδεσε τα συμπεράσματά του για τα δέντρα με τις σύγχρονες μελέτες για τη χημική σύνθεση. Η σύνθεση των μαθηματικών και των χημικών εννοιών είναι το αρχικό τμήμα της στερεότυπης (standard) ορολογίας της θεωρίας γράφων.

Περαιτέρω ανάγνωση

Online κείμενα 
 
 Η θεωρία γράφων με εφαρμογές (1976) - Bondy and Murty
 Εισαγωγή στους Γράφους (2006) Hartmann and Weigt
 Διγράφοι: Θεωρία αλγόριθμοι και εφαρμογές 2007 - Jorgen Bang-Jensen and Gregory Gutin
 Θεωρία γράφων - Reinhard Diestel

Σημειώσεις

Βιβλιογραφία

Εξωτερικοί σύνδεσμοι 
 Εγχειρίδιο θεωρίας γράφων 
 Φωτοθήκη: γράφοι
 Συνοπτικός κατάλογος πηγών για τη θεωρία γράφων
 Graph Theory Software

Ελληνικά άρθρα

Παραπομπές