Θεωρία γράφων
Η θεωρία γράφων είναι ένα γνωστικό πεδίο των διακριτών μαθηματικών, με εφαρμογές στην πληροφορική, στις επιστήμες μηχανικών, στη χημεία, στην κοινωνιολογία κ.α. Αν και οι απαρχές της θεωρίας θεμελιώθηκαν κατά τον 18ο αιώνα, αναπτύχθηκε μεταπολεμικά ως ξεχωριστό πεδίο των εφαρμοσμένων μαθηματικών[1].
Στην ελληνική ορολογία οι όροι θεωρία γραφημάτων και θεωρία γράφων χρησιμοποιούνται ως ισοδύναμοι. Προτιμάται ο όρος γράφος, για να διακρίνεται από το γράφημα συνάρτησης. Ανάμεσα στους ποικίλους ορισμούς που απαντώνται, ένας σχετικά πλήρης ορίζει πως η θεωρία γράφων είναι η μελέτη των γράφων (γραφημάτων) και των σχέσεών τους. Οι μαθηματικοί υπολογισμοί επί των γράφων υλοποιούνται με συγκεκριμένους αλγόριθμους. Με γράφους μπορούν να μοντελοποιηθούν πολλές διαφορετικές φυσικές ή τεχνολογικές δομές, όπως π.χ. τα δίκτυα υπολογιστών, όπου το διάγραμμα ενός δικτύου μοντελοποιείται ως ένας απλός κατευθυνόμενος γράφος[2].
Γράφος Επεξεργασία
Ο γράφος στον απλούστερο ορισμό του είναι η οπτική αναπαράσταση των σχέσεων που αναπτύσσουν ορισμένες ποσότητες, σχεδιασμένες σε σχέση με ένα σύνολο αξόνων.[3] Ένας άλλος ορισμός που κινείται στο ίδιο εννοιολογικό πλαίσιο της οπτικής αναπαράστασης αναγνωρίζει τον γράφο ως απεικόνιση αποτελούμενη από ένα σύνολο σημείων (κορυφών ή κόμβων) που συνδέονται με γραμμές (ακμές). Στους κατευθυνόμενους ή προσανατολισμένους γράφους οι ακμές απεικονίζονται διανυσματικά.[4]
Σε μία άλλη εκδοχή είναι ένα σύνολο από κόμβους (κορυφές) που ενώνονται μεταξύ τους με ακμές και ορίζεται από τον τρόπο με τον οποίο συνδέονται οι κορυφές (κόμβοι). Αν οι ακμές προσανατολίζονται οριζόμενες από διατεταγμένα ζεύγη κόμβων, τότε ο γράφος αποκαλείται κατευθυνόμενος. Αν οι ακμές δεν προσανατολίζονται, οριζόμενες απλώς από διμελή σύνολα και όχι διατεταγμένα ζεύγη, τότε αποκαλείται μη κατευθυνόμενος. Επιπλέον στοιχεία για τον ορισμό ενός γράφου είναι η σύνδεση των ακμών του με κάποια αξία, οπότε αποκαλείται σταθμισμένος.
Με τη σειρά του πλήρης αποκαλείται ο γράφος που περιέχει ακμές για κάθε ζεύγος κόμβων, αραιός εκείνος που περιέχει λίγες ακμές ή αντίστροφα πυκνός.[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]
Βαθμός κορυφής (degvi ) Επεξεργασία
Βαθμός (deg) της κορυφής vi είναι ο αριθμός που εκφράζει το πλήθος των ακμών που καταλήγουν σε αυτήν την κορυφή.
Διαδρομή Επεξεργασία
Σε ένα συνεκτικό γράφο, διαδρομή καλείται ένα υποσύνολο κορυφών V'(G)={v1,v2...vm}, m≤n , με 0 < deg vi ≤ 2. Στην ελληνική βιβλιογραφία η διαδρομή αναφέρεται και ως μονοπάτι από την αγγλική λέξη path.
Συνεκτικός γράφος[8] Επεξεργασία
Συνεκτικός γράφος λέγεται ο γράφος του οποίου κάθε ζεύγος κορυφών συνδέεται με μια τουλάχιστον διαδρομή.
Ιστορία της θεωρίας γράφων Επεξεργασία
Για την ιστορία της θεωρίας γράφων θεωρείται σημαντική η μελέτη του Λέοναρντ Όιλερ για τις Επτά Γέφυρες του Κένιγκσμπεργκ το 1736 [9] Η συγκεκριμένη δημοσίευση, όπως και εκείνη που γράφτηκε από τον Γάλλο χημικό Αλεξάντρ-Τεοφίλ Βαντερμόντ (Alexandre-Théophile Vandermonde) στο μαθηματικό πρόβλημα του Ίππου στη σκακιέρα που κατευθύνεται με την ανάλυση θέσης που εισήγαγε ο Γκότφριντ Βίλχελμ Λάιμπνιτς. Ο τύπος του Όιλερ, σχετικά με τον αριθμό των ακμών, των κορυφών και των εδρών ενός κυρτού πολυέδρου μελετήθηκε από τον Ωγκυστέν-Λουί Κωσύ[10] και τον Σιμόν Αντουάν Ζαν Λ' Ουιγιέ (Simon Antoine Jean L'Huillier)[11] και είναι αρχή της τοπολογίας.
Σχεδόν εκατό χρόνια μετά τη μελέτη του Όιλερ και την εισαγωγή της τοπολογίας από τον Γιόχαν Μπένεντικτ Λίστινγκ (Johann Benedict Listing), ο Άρθουρ Κέιλι (Arthur Cayley) μελέτησε μια ιδιαίτερη κατηγορία γράφων, τα δέντρα. Η μελέτη αυτών των ιδιαίτερων γράφων είχε πολλές εφαρμογές στη θεωρητική χημεία. Οι τεχνικές που αναπτύχθηκαν είχαν να κάνουν κυρίως με την απαρίθμηση γράφων που παρουσίαζαν κάποιες ιδιαίτερες ιδιότητες. Η απαριθμητική θεωρία γράφων ήταν ένα από τα συμπεράσματα του Κέιλι και δημοσιεύτηκε από τον (Γκιόργκι) Τζορτζ Πόλια (George Pólya) μεταξύ των ετών 1935 και 1937, ενώ η γενίκευση των συμπερασμάτων εκδόθηκε από τον Νίκλας Γκόβερτ ντε Μπρούιν (Nicolaas Govert de Bruijn) το 1959. Ο Κέιλι συνέδεσε τα συμπεράσματά του για τα δέντρα με τις σύγχρονες μελέτες για τη χημική σύνθεση.[12] Η σύνθεση των μαθηματικών και των χημικών εννοιών είναι το αρχικό τμήμα της στερεότυπης (standard) ορολογίας της θεωρίας γράφων.
Περαιτέρω ανάγνωση Επεξεργασία
Online κείμενα Επεξεργασία
- Νικολόπουλος, Σταύρος· Γεωργιάδης, Λουκάς· Παληός, Λεωνίδας. Αλγοριθμική θεωρία γραφημάτων. Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις. ISBN 978-960-603-365-0.
- Η θεωρία γράφων με εφαρμογές (1976) - Bondy and Murty
- Εισαγωγή στους Γράφους (2006) Hartmann and Weigt
- Διγράφοι: Θεωρία αλγόριθμοι και εφαρμογές 2007 - Jorgen Bang-Jensen and Gregory Gutin
- Θεωρία γράφων - Reinhard Diestel
Σημειώσεις Επεξεργασία
- Θηλυκός, Δημήτριος Μ. (2021). «Σημειώσεις στη θεωρία γραφημάτων» (PDF). Τμήμα Μαθηματικών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών. Ανακτήθηκε στις 15 Οκτωβρίου 2023.
Βιβλιογραφία Επεξεργασία
- Biggs, Norman· Lloyd, Edward Keith· Wilson, Robin J.· Wilson, Robin James (1986). Graph theory: 1736 - 1936 (1η έκδοση). Oxford: Clarendon Press. ISBN 978-0-19-853916-2.
- Cauchy, A.L. (1813). «Recherche sur les polyèdres - premier mémoire». Journal de l'Ecole Polytechnique 16 (9): 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.
- Λευτέρης Κυρούσης· Χρήστος Μπούρας· Παύλος Σπυράκης· Γιάννης Σταματίου (2004). Εισαγωγή στους Γράφους Θεωρία, προβλήματα και λύσεις (2η έκδοση). Gutenberg. ISBN 978-960-01-0815-6.
Εξωτερικοί σύνδεσμοι Επεξεργασία
- Εγχειρίδιο θεωρίας γράφων Αρχειοθετήθηκε 2012-01-16 στο Wayback Machine.
- Φωτοθήκη: γράφοι
- Συνοπτικός κατάλογος πηγών για τη θεωρία γράφων
- Graph Theory Software Αρχειοθετήθηκε 2013-03-13 στο Wayback Machine.
Ελληνικά άρθρα Επεξεργασία
- Χριστόπουλος, Παναγιώτης Π. (Απριλίου 2019). «Οι επτά γέφυρες και τα γραφήματα». Ευκλείδης Β΄ (114): 4-8. http://www.hms.gr/sites/default/files/subsites/problems/material/EYKLEIDHS_B_114_EYKLEIDHS_2019.pdf.
Παραπομπές Επεξεργασία
- ↑ Μαυρονικόλας Μάριος 2002, vii.
- ↑ ««Graph theory» στο Actano - glossary». Αρχειοθετήθηκε από το πρωτότυπο στις 23 Μαρτίου 2010. Ανακτήθηκε στις 11 Μαρτίου 2010.
- ↑ «graph» στο WordNet Search - 3.0.
- ↑ «graph» στο Actano.com Αρχειοθετήθηκε 2010-03-23 στο Wayback Machine..
- ↑ Δ. Σπινέλλης «Γράφοι», Οικονομικό Πανεπιστήμιο Αθηνών Αρχειοθετήθηκε 2010-01-02 στο Wayback Machine..
- ↑ Μαυρονικόλας Μάριος 2002, 11.
- ↑ Μαυρονικόλας Μάριος 2002, 13.
- ↑ Dimitrios, Georgiou,; Efstathios, Antoniou,; Anestis, Chatzimichailidis,; Γεωργίου, Δημήτριος,; Αντωνίου, Ευστάθιος,; Χατζημιχαηλίδης, Ανέστης, (2015-12-21). Γραφοί και Εφαρμογές Αυτών. https://repository.kallipos.gr/handle/11419/461.
- ↑ Biggs, N.· Lloyd, E.· Wilson, R. (1986). Graph Theory, 1736-1936. Oxford University Press.
- ↑ Cauchy, A.L. (1813). «Recherche sur les polyèdres - premier mémoire». Journal de l'Ecole Polytechnique 9 (Cahier 16): 66–86.
- ↑ L'Huillier, S.-A.-J. (1861). «Mémoire sur la polyèdrométrie». Annales de Mathématiques 3: 169–189.
- ↑ 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:..