National and Kapodistrian University of Athens
Asymptotic Analysis of Outerplanar Graphs with Subgraph Obstructions
Abstract
dc:descriptionΣε αυτή την εργασία μελετάμε τεχνικές συνδυαστικής μοντελοποίησης καιασυμπτωτικής απαρίθμησης στο πλαίσιο της αναλυτικής συνδυαστικής. Ο οδηγός μας μέσα σε αυτή την πληθώρα τεχνικών είναι η απαρίθμηση κάποιων τύπων επίπεδων γραφημάτων, όταν εξαιρούμε συγκεκριμένα υπογραφήματα. Για την ακρίβεια, μελετάμε εξωεπίπεδα γραφήματα όταν ο περιορισμός είναι ο αποκλεισμός κύκλων συγκεκριμένου μήκους. Κατασκευάζουμε συνδυαστικές περιγραφές για τις δισυνεκτικές συνιστώσες που εξαιρούν τους κύκλους ώστε να αποκτήσουμε ασυμπτωτικά αποτελέσματα για τη γενική κλάση των εξωεπίπεδων γραφημάτων υπό περιορισμό. Οι προκλήσεις είναι συνδυαστικής αλλά και υπολογιστικής φύσης, καθώς οι περιγραφές γίνονται πιο περίπλοκες όταν το μήκος των κύκλων μεγαλώνει και οι γεννήτριες συναρτήσεις δίνονται σε έμμεση μορφή. Η συνδυαστική γλώσσα που χρησιμοποιείται είναι η λεγόμενη Συμβολική Μέθοδος που έρχεται μαζί με αντίστοιχες αναλυτικές τεχνικές.Επίσης μελετάμε παραμέτρους γενικών εξωεπίπεδων γραφημάτων, συγκεκριμένα τον αριθμό των τριγώνων και των τετραγώνων. Καταλήγουμε σε κανονικές οριακές κατανομές και εξάγουμε συγκεκριμένες σταθερές για την μέση τιμή και τη διασπορά.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Βελώνα Βασιλική
Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:1320908