1. Home page
  2. Search

Expanding Graphs and Balanced Separators

This item is provided by the institution :
/aggregator-openarchives/portal/institutions/uoa   

Repository :
Pergamos Digital Library   

see the original item page
in the repository's web site and access all digital files if the item*



Expanding Graphs and Balanced Separators
Νικλάνοβιτς Αικατερίνη (EL)
Niklanovits Aikaterini (EN)
born_digital_postgraduate_thesis
Διπλωματική Εργασία (EL)
Postgraduate Thesis (EN)
2019
Ένα γράφημα ονομάζεται εξαπλωτής αν είναι αραιό αλλά ταυτόχρονα έχει ισχυρές ιδιότητες συνεκτικότητας. Οι εξαπλωτές είναι μία κατηγορία γραφημάτων η οποία, κυρίως λόγω των πολλών εφαρμογών τους σε διαφορετικά πεδία των μαθηματικών, έχουν μελετηθεί εκτενώς. Ο στόχος αυτής της εργασίας είναι να αναλύσουμε τη σύνδεση των εξαπλωτών με άλλες έννοιες της θεωρίας γραφημάτων, και να μελετήσουμε τις δομές που μπορούμε να βρούμε σε αυτούς. Συγκεκριμένα, θα επικεντρωθούμε στους ισορροπημένους διαχωριστές και πώς αυτοί συνδέονται με τους εξαπλωτές. Επιπλέον θα δούμε πιο σύντομα, πώς οι ιδιοτιμές του πίνακα γειτνίασης ενός γραφήματος συνδέονται με την εξάπλωσή του αλλά και με άλλες ιδιότητές του. Τέλος, θα ασχοληθούμε ιδιαίτερα με τα ελάσσονα γραφήματα ενός εξαπλωτή. (EL)
A graph is an expander if it is sparse and has strong connectivity properties. Expanders are widely studied graphs, mainly due to their numerous applications in many different mathematical fields. The purpose of this thesis is to analyze the connections between expanders and other notions of graph theory, and study their substructures. Specifically, we will focus on the connection of balanced separators and expanders and provide an introduction on how the expansion of a graph is connected to the eigenvalues of its adjacency matrix. We will also study in detail the minors one can find in expanders. (EN)
Θετικές Επιστήμες
Θετικές Επιστήμες (EL)
Science (EN)
English
Βιβλιοθήκη και Κέντρο Πληροφόρησης » Βιβλιοθήκη Σχολής Θετικών Επιστημών » Πληροφορική
Σχολή Θετικών Επιστημών » Τμήμα Πληροφορικής & Τηλεπικοινωνιών » Διιδρυματικό ΠΜΣ Αλγόριθμοι, Λογική και Διακριτά Μαθηματικά (Α.Λ.ΜΑ.) » Κατεύθυνση Αλγόριθμοι, Λογική και Διακριτά Μαθηματικά (Α.Λ.ΜΑ.)
https://creativecommons.org/licenses/by-nc/4.0/
University of Athens
Pergamos Digital Library
Postgraduate Thesis



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)