Το θέμα αυτής της πτυχιακής εργασίας είναι τα γραφήματα expanders. Αρχικά αναφέρεται πώς μπορεί να περιγραφεί ένα γράφημα, το οποίο αποτελείται από κορυφές και ακμές, καθώς και διάφορα στοιχεία αυτού, ένα από τα οποία είναι ο βαθμός του. Στη συνέχεια, αναλύεται η σημασία του πίνακα γειτονίας ενός γραφήματος και η έννοια του girth. Απαραίτητος είναι ο ορισμός των γραφημάτων που ονομάζονται δέντρα, καθώς και των διμερών γραφημάτων, τα οποία παρουσιάζονται παρακάτω μέσω των ορισμών τους και παραδειγμάτων που τα περιγράφουν ακόμη περισσότερο. Στη συνέχεια, ορίζονται έννοιες όπως η απόσταση και η διάμετρος δύο κορυφών σε ένα γράφημα, αλλά και το καθολικό κάλυμμα, το οποίο αποτελεί μία πολύ σημαντική κατασκευή γραφημάτων. Έπειτα, αρχίζει η ενότητα που αφορά την επέκταση των γραφημάτων, στην οποία πρώτα από όλα ορίζεται η σταθερά επέκτασης. Ακολουθούν τα expander γραφήματα, που είναι και το κύριο θέμα της εργασίας. Αναλύονται σε πλήρη βαθμό οι τρεις συνθήκες που κάνουν μία οικογένεια γραφημάτων να είναι expander οικογένεια και δε θα μπορούσαν να λείπουν διάφορα παραδείγματα που βοηθούν ακόμη περισσότερο στην κατανόησή αυτών των εννοιών. Παρουσίαζεται ξανά η διάμετρος, τώρα συναρτήσει της σταθεράς επέκτασης, καθώς και μία νέα έννοια η οποία ονομάζεται σύνορο γραφήματος. Τέλος, αναφέρονται οι έννοιες των spectrum και spectral gap, έννοιες που σχετίζονται με τις ιδιοτιμές του πίνακα γειτονίας, τα οποία δινούν έναν ακόμη τρόπο να περιγραφεί η έννοια της οικογένειας expanders.
University of the Aegena
