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

Θεωρία γράφων
Ταξινόμηση
Dewey	512
MSC2010	05Cxx
	π; σ; ε;

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

Γράφημα (σχέδιο) γράφου

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

ΓράφοςΕπεξεργασία

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

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

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

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

Άκυκλος γράφος (δέντρο) έξι κόμβων

Κυκλικός γράφος (δακτύλιος) έξι κόμβων

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

Μη κατευθυνόμενος γράφοςΕπεξεργασία

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

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

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

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

Κατευθυνόμενος γράφοςΕπεξεργασία

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

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

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

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

Βαθμός κορυφής (degv_i )Επεξεργασία

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

ΔιαδρομήΕπεξεργασία

Σε ένα συνεκτικό γράφο, διαδρομή καλείται ένα υποσύνολο κορυφών V'(G)={v₁,v₂...v_m}, m≤n , με 0 < deg v_i ≤ 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) ορολογίας της θεωρίας γράφων.

Σημειώσεις-παραπομπέςΕπεξεργασία

↑ Μαυρονικόλας Μάριος 2002, vii.
↑ ««Graph theory» στο Actano - glossary». Αρχειοθετήθηκε από το πρωτότυπο στις 23 Μαρτίου 2010. Ανακτήθηκε στις 11 Μαρτίου 2010.
↑ «graph» στο WordNet Search - 3.0.
↑ «graph» στο Actano.com Αρχειοθετήθηκε 2010-03-23 στο 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. and 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: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 κείμεναΕπεξεργασία

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

Άλλες πηγέςΕπεξεργασία

[1] Μαυρονικόλας Μάριος 2002, vii.

[2] ««Graph theory» στο Actano - glossary». Αρχειοθετήθηκε από το πρωτότυπο στις 23 Μαρτίου 2010. Ανακτήθηκε στις 11 Μαρτίου 2010.

[3] «graph» στο WordNet Search - 3.0.

[4] «graph» στο Actano.com Αρχειοθετήθηκε 2010-03-23 στο Wayback Machine..

[5] Δ. Σπινέλλης «Γράφοι», Οικονομικό Πανεπιστήμιο Αθηνών.

[6] Μαυρονικόλας Μάριος 2002, 11.

[7] Μαυρονικόλας Μάριος 2002, 13.

[8] Dimitrios, Georgiou,; Efstathios, Antoniou,; Anestis, Chatzimichailidis,; Γεωργίου, Δημήτριος,; Αντωνίου, Ευστάθιος,; Χατζημιχαηλίδης, Ανέστης, (2015-12-21). Γραφοί και Εφαρμογές Αυτών. https://repository.kallipos.gr/handle/11419/461.

[Biggs-9] Biggs, N.; Lloyd, E. and Wilson, R. (1986). Graph Theory, 1736-1936. Oxford University Press.

[Cauchy-10] Cauchy, A.L. (1813). «Recherche sur les polyèdres - premier mémoire». Journal de l'Ecole Polytechnique 9 (Cahier 16): 66–86.

[Lhuillier-11] L'Huillier, S.-A.-J. (1861). «Mémoire sur la polyèdrométrie». Annales de Mathématiques 3: 169–189.

[Cayley1-12] 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. .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]