National and Kapodistrian University of Athens
Αλγοριθμικές Τεχνικές για προβλήματα μέτρησης σε γραφήματα
Abstract
dc:descriptionΣτην εργασία αυτή θα ασχοληθούμε με το πρόβλημα της καταμέτρησης του πλήθους των εναγομένων υπογραφημάτων με k κορυφές, ενός δοσμένου γραφήματος G, που έχουν άρτια ποσότητα ακμών, και αυτά τα υπογραφήματα τα καλούμε άρτια υπογραφήματα. Αρχικά, θα διερευνήσουμε τα δομικά χαρακτηριστικά που πρέπει να έχει ένα γράφημα ώστε να εξασφαλίζεται η ύπαρξη, ή όχι, τουλάχιστον ενός άρτιου εναγομένου υπογραφήματος k κορυφών. Με την βοήθεια φράγματος της θεωρίας Ramsey, θα καταλήξουμε ότι, για γραφήματα με μεγάλο πλήθος ακμών, η ύπαρξη τουλάχιστον ενός άρτιου εναγομένου γραφήματος k κορυφών μπορεί πολύ εύκολα να αποφασιστεί, ελέγχοντας αν το γράφημα G ανήκει σε κάποιες συγκεκριμένες οικογένειες γραφημάτων, το πλήθος των οποίων είναι πολύ μικρό, και εξετάζοντας κάποιες απλές αριθμητικές σχέσεις για το k. Χρησιμοποιώντας τα παραπάνω δεδομένα, θα κατασκευάσουμε έναν παραμετρικό αλγόριθμο, με παράμετρο το k, που θα αποφασίζει αν ένα γράφημα περιέχει ένα τέτοιο υπογράφημα με k κορυφές. Επιπλέον, συναντάμε ένα απροσδόκητο αποτέλεσμα, που μας εξασφαλίζει ότι αν ένα γράφημα n κορυφών έχει τουλάχιστον ένα άρτιο εναγόμενο υπογράφημα k κορυφών, όπου το n είναι αρκετά πιο μεγάλο από το k, τότε θα έχει ένα μεγάλο πλήθος τέτοιων υπογραφημάτων. Μάλιστα το πλήθος αυτών των υπογραφημάτων είναι επαρκώς μεγάλο ώστε η μέθοδος της τυχαίας δειγματοληψίας να παρέχει μια καλή εκτίμηση του συνολικού πλήθους τέτοιων υπογραφημάτων χωρίς απαιτούνται υπερβολικά πολλές δοκιμές. Αντίστοιχη μελέτη γίνεται για το πρόβλημα απόφασης ύπαρξης περιττών εναγομένων υπογραφημάτων k κορυφών, δηλαδή υπογραφημάτων έχουν περιττό πλήθος ακμών, όπως και για το αντίστοιχο πρόβλημα καταμέτρησης.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Καλογιάννη Μαρία
- Kalogianni Maria
Subjects
dc:subject × 2Rights
- Language dc:language
- Ελληνικά, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:2838872