Αλγοριθμικές Τεχνικές για προβλήματα μέτρησης σε γραφήματα

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

Μονάδα:
Κατεύθυνση Θεωρητικά Μαθηματικά
Βιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2019-01-11
Έτος εκπόνησης:
2019
Συγγραφέας:
Καλογιάννη Μαρία
Στοιχεία επιβλεπόντων καθηγητών:
Θηλυκός Δημήτριος, Καθηγητής, Τμήμα Μαθηματικών, ΕΚΠΑ.
Πρωτότυπος Τίτλος:
Αλγοριθμικές Τεχνικές για προβλήματα μέτρησης σε γραφήματα
Γλώσσες εργασίας:
Ελληνικά
Μεταφρασμένος τίτλος:
Αλγοριθμικές Τεχνικές για προβλήματα μέτρησης σε γραφήματα
Περίληψη:
Στην εργασία αυτή θα ασχοληθούμε με το πρόβλημα της καταμέτρησης του πλήθους των εναγομένων υπογραφημάτων με k κορυφές, ενός δοσμένου γραφήματος G, που έχουν άρτια ποσότητα ακμών, και αυτά τα υπογραφήματα τα καλούμε άρτια υπογραφήματα. Αρχικά, θα διερευνήσουμε τα δομικά χαρακτηριστικά που πρέπει να έχει ένα γράφημα ώστε να εξασφαλίζεται η ύπαρξη, ή όχι, τουλάχιστον ενός άρτιου εναγομένου υπογραφήματος k κορυφών. Με την βοήθεια φράγματος της θεωρίας Ramsey, θα καταλήξουμε ότι, για γραφήματα με μεγάλο πλήθος ακμών, η ύπαρξη τουλάχιστον ενός άρτιου εναγομένου γραφήματος k κορυφών μπορεί πολύ εύκολα να αποφασιστεί, ελέγχοντας αν το γράφημα G ανήκει σε κάποιες συγκεκριμένες οικογένειες γραφημάτων, το πλήθος των οποίων είναι πολύ μικρό, και εξετάζοντας κάποιες απλές αριθμητικές σχέσεις για το k. Χρησιμοποιώντας τα παραπάνω δεδομένα, θα κατασκευάσουμε έναν παραμετρικό αλγόριθμο, με παράμετρο το k, που θα αποφασίζει αν ένα γράφημα περιέχει ένα τέτοιο υπογράφημα με k κορυφές. Επιπλέον, συναντάμε ένα απροσδόκητο αποτέλεσμα, που μας εξασφαλίζει ότι αν ένα γράφημα n κορυφών έχει τουλάχιστον ένα άρτιο εναγόμενο υπογράφημα k κορυφών, όπου το n είναι αρκετά πιο μεγάλο από το k, τότε θα έχει ένα μεγάλο πλήθος τέτοιων υπογραφημάτων. Μάλιστα το πλήθος αυτών των υπογραφημάτων είναι επαρκώς μεγάλο ώστε η μέθοδος της τυχαίας δειγματοληψίας να παρέχει μια καλή εκτίμηση του συνολικού πλήθους τέτοιων υπογραφημάτων χωρίς απαιτούνται υπερβολικά πολλές δοκιμές. Αντίστοιχη μελέτη γίνεται για το πρόβλημα απόφασης ύπαρξης περιττών εναγομένων υπογραφημάτων k κορυφών, δηλαδή υπογραφημάτων έχουν περιττό πλήθος ακμών, όπως και για το αντίστοιχο πρόβλημα καταμέτρησης.
Κύρια θεματική κατηγορία:
Θετικές Επιστήμες
Λέξεις-κλειδιά:
γραφήματα, παραμετρική πολυπλοκότητα, θεωρία Ράμσεϊ, καταμέτρηση άρτιων εναγόμενων υπογραφημάτων, περιττό υπογράφημα
Ευρετήριο:
Ναι
Αρ. σελίδων ευρετηρίου:
1
Εικονογραφημένη:
Ναι
Αρ. βιβλιογραφικών αναφορών:
34
Αριθμός σελίδων:
74
thesis_Maria_Kalogianni.pdf (407 KB) Άνοιγμα σε νέο παράθυρο