Asymptotic Analysis of Outerplanar Graphs with Subgraph Obstructions

Διπλωματική Εργασία uoadl:1320908 209 Αναγνώσεις

Μονάδα:
Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και Υπολογισμού
Βιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2016-06-24
Έτος εκπόνησης:
2016
Συγγραφέας:
Βελώνα Βασιλική
Στοιχεία επιβλεπόντων καθηγητών:
Δημήτριος Μ. Θηλυκός Καθηγητής (Επιβλέπων), Juanjo Rue Perna
Πρωτότυπος Τίτλος:
Asymptotic Analysis of Outerplanar Graphs with Subgraph Obstructions
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Ασυμπτωτική Ανάλυση Εξωεπίπεδων Γραφημάτων με Παρεμποδισμένα Υπογραφήματα
Περίληψη:
Σε αυτή την εργασία μελετάμε τεχνικές συνδυαστικής μοντελοποίησης
καιασυμπτωτικής απαρίθμησης στο πλαίσιο της αναλυτικής συνδυαστικής. Ο οδηγός
μας μέσα σε αυτή την πληθώρα τεχνικών είναι η απαρίθμηση κάποιων τύπων επίπεδων
γραφημάτων, όταν εξαιρούμε συγκεκριμένα υπογραφήματα. Για την
ακρίβεια, μελετάμε εξωεπίπεδα γραφήματα όταν ο περιορισμός είναι ο αποκλεισμός
κύκλων συγκεκριμένου μήκους. Κατασκευάζουμε συνδυαστικές
περιγραφές για τις δισυνεκτικές συνιστώσες που εξαιρούν τους κύκλους ώστε να
αποκτήσουμε ασυμπτωτικά αποτελέσματα για τη γενική κλάση των
εξωεπίπεδων γραφημάτων υπό περιορισμό. Οι προκλήσεις είναι συνδυαστικής αλλά
και υπολογιστικής φύσης, καθώς οι περιγραφές γίνονται πιο περίπλοκες
όταν το μήκος των κύκλων μεγαλώνει και οι γεννήτριες συναρτήσεις δίνονται σε
έμμεση μορφή. Η συνδυαστική γλώσσα που χρησιμοποιείται είναι η λεγόμενη
Συμβολική Μέθοδος που έρχεται μαζί με αντίστοιχες αναλυτικές τεχνικές.Επίσης
μελετάμε παραμέτρους γενικών εξωεπίπεδων γραφημάτων, συγκεκριμένα
τον αριθμό των τριγώνων και των τετραγώνων. Καταλήγουμε σε κανονικές οριακές
κατανομές και εξάγουμε συγκεκριμένες σταθερές για την μέση τιμή
και τη διασπορά.
Λέξεις-κλειδιά:
Συνδυαστική
Ευρετήριο:
Ναι
Αρ. σελίδων ευρετηρίου:
7,9,11
Εικονογραφημένη:
Ναι
Αρ. βιβλιογραφικών αναφορών:
11
Αριθμός σελίδων:
57