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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση
Θεωρία γράφων
Ταξινόμηση
Dewey 512
MSC2010 05Cxx
Γράφημα (σχέδιο) γράφου

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

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

Γράφος[Επεξεργασία | επεξεργασία κώδικα]

Κύριο λήμμα: Γράφος

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

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

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

Πλήρης γράφος με 5 κόμβους. Κάθε κόμβος συνδέεται με ακμή με κάθε άλλο κόμβο
Άκυκλος γράφος (δέντρο) έξι κόμβων
Κυκλικός γράφος (δακτύλιος) έξι κόμβων

Τυπολογικά παραδείγματα[Επεξεργασία | επεξεργασία κώδικα]

Μη κατευθυνόμενος γράφος[Επεξεργασία | επεξεργασία κώδικα]

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

Ο γράφος G είναι ένα διατεταγμένο ζεύγος G=<V(G), E(G)> όπου:

  • V(G)={v1,v2...vn} το σύνολο των κορυφών,
  • E(G)={e1,e2...em} το σύνολο των ακμών.

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

Κατευθυνόμενος γράφος[Επεξεργασία | επεξεργασία κώδικα]

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

Ο γράφος G είναι ένα διατεταγμένο ζεύγος G=<V(G), E(G)> όπου:

  • V(G)={v1,v2...vn} το σύνολο των κορυφών,
  • E(G)={e1,e2...em} το σύνολο των ακμών.

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

Ιστορία της θεωρίας γράφων[Επεξεργασία | επεξεργασία κώδικα]

Πρόβλημα της γέφυρας της Καινιξβέργης.

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

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

Σημειώσεις-παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. Μαυρονικόλας Μάριος 2002, vii.
  2. «Graph theory» στο Actano - glossary
  3. «graph» στο WordNet Search - 3.0.
  4. «graph» στο Actano.com.
  5. Δ. Σπινέλλης «Γράφοι», Οικονομικό Πανεπιστήμιο Αθηνών.
  6. Μαυρονικόλας Μάριος 2002, 11.
  7. Μαυρονικόλας Μάριος 2002, 13.
  8. Biggs, N.; Lloyd, E. and Wilson, R. (1986). Graph Theory, 1736-1936. Oxford University Press. 
  9. Cauchy, A.L. (1813). "Recherche sur les polyèdres - premier mémoire". Journal de l'Ecole Polytechnique 9 (Cahier 16): 66–86. 
  10. L'Huillier, S.-A.-J. (1861). "Mémoire sur la polyèdrométrie". Annales de Mathématiques 3: 169–189. 
  11. Cayley, A. (1875). "Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen". Berichte der deutschen Chemischen Gesellschaft 8: 1056–1059. doi:10.1002/cber.18750080252. .

Βιβλιογραφία[Επεξεργασία | επεξεργασία κώδικα]

  • Biggs, N.; Lloyd, E. and Wilson, R. 1986, Graph Theory, 1736-1936. Oxford University Press ISBN 978-0-19-853916-2
  • Cauchy, A.L. (1813). "Recherche sur les polyèdres - premier mémoire". Journal de l'Ecole Polytechnique 9 (Cahier 16): 66–86.
  • Cayley, A. (1875). "Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen". Berichte der deutschen Chemischen Gesellschaft 8: 1056–1059
  • L'Huillier, S.-A.-J. (1861). "Mémoire sur la polyèdrométrie". Annales de Mathématiques 3: 169–189.
  • Μαυρονικόλας Μάριος 2002, Διακριτά Μαθηματικά και Μαθηματική Λογική: Θεωρία Γράφων, Ε.Α.Π., Πάτρα ISBN 960-538-461-2

Δικτυακοί τόποι[Επεξεργασία | επεξεργασία κώδικα]

Online κείμενα[Επεξεργασία | επεξεργασία κώδικα]

Άλλες πηγές[Επεξεργασία | επεξεργασία κώδικα]