Ένα γράφημα ονομάζεται εξαπλωτής αν είναι αραιό αλλά ταυτόχρονα έχει ισχυρές ιδιότητες συνεκτικότητας. Οι εξαπλωτές είναι μία κατηγορία γραφημάτων η οποία, κυρίως λόγω των πολλών εφαρμογών τους σε διαφορετικά πεδία των μαθηματικών, έχουν μελετηθεί εκτενώς. Ο στόχος αυτής της εργασίας είναι να αναλύσουμε τη σύνδεση των εξαπλωτών με άλλες έννοιες της θεωρίας γραφημάτων, και να μελετήσουμε τις δομές που μπορούμε να βρούμε σε αυτούς. Συγκεκριμένα, θα επικεντρωθούμε στους ισορροπημένους διαχωριστές και πώς αυτοί συνδέονται με τους εξαπλωτές. Επιπλέον θα δούμε πιο σύντομα, πώς οι ιδιοτιμές του πίνακα γειτνίασης ενός γραφήματος συνδέονται με την εξάπλωσή του αλλά και με άλλες ιδιότητές του. Τέλος, θα ασχοληθούμε ιδιαίτερα με τα ελάσσονα γραφήματα ενός εξαπλωτή.
Όνομα
Αικατερίνη Νικλάνοβιτς
Ημερομηνία παρουσίασης
09-10-2019
Τριμελής επιτροπή
Αρχοντία Γιαννοπούλου
Μιχάλης Δρακόπουλος
Δημήτριος Θηλυκός (Επιβλέπων)
Σύνοψη