MSc thesis of Δημήτρη Ζώρου
Παρεμποδίσεις και Αλγόριθμοι για Προβλήματα Ανίχνευσης Γρφημάτων
Supervisor: Δημήτριος Μ. Θηλυκός
Η Ανίχνευση Γραφημάτων αποτελεί έναν κλάδο των Διακριτών Μαθηματικών με πλήθος εφαρμογών σε πολλούς τομείς της Θεωρητικής Πληροφορικής. Παρουσιάζει επίσης μεγάλο θεωρητικό ενδιαφέρον καθώς μέσω αυτής εκφράζονται πολλά σημαντικά συνδυαστικά προβλήματα. Στα πρώτα κεφάλαια αυτής της εργασίας θα παρουσιάσουμε τα κίνητρα που ώθησαν τους ερευνητές να ασχοληθούν με την ανίχνευση γραφημάτων, θα ορίσουμε τυπικά τους τρεις βασικούς τύπους της και θα παρουσιάσουμε τις σημαντικότερες παραλλαγές τους. Στη συνέχεια θα αναλύσουμε τις έννοιες της μονοτονίας και της συνεκτικότητας και θα καταγράψουμε μερικά αποτελέσματα από τη βιβλιογραφία. Το δεύτερο σκέλος της εργασίας αυτής είναι η μελέτη της Θεωρίας Μερικών Διατάξεων σε κλάσεις γραφημάτων και πως από αυτή προκύπτει ο χαρακτηρισμός της κλάσης μέσω ενός συνόλου απαγορευμένων γραφημάτων, το οποίο καλείται Σύνολο Παρεμπόδισης της κλάσης. Αφού αναφέρουμε συνοπτικά τις απαραίτητες έννοιες, θα παρουσιάσουμε όλα τα έως τώρα γνωστά σύνολα παρεμπόδισης για κλάσεις γραφημάτων με φραγμένο αριθμό ανίχνευσης. Το μεγαλύτερο σε μέγεθος σύνολο που θα αναφερθεί συγκαταλέγεται στα αποτελέσματα δικής μας εργασίας, που βρίσκεται ακόμα υπό συγγραφή. Η ανίχνευση γραφημάτων συνδέεται άρρηκτα με τις Παραμέτρους Πλάτους γραφήματος. Τα περισσότερα αποτελέσματα της βιβλιογραφίας αφορούν τις παραμέτρους αυτές καθώς η ορολογία τους διευκολύνει αρκετά την απόδειξη των θεωρημάτων. Στο Κεφάλαιο 6 θα ορισθούν οι σημαντικότερες παράμετροι πλάτους γραφήματος και θα παρουσιαστεί ο τρόπος που σχετίζονται με τους αριθμούς ανίχνευσης. Το τρίτο σκέλος της εργασίας αυτής αφορά την Υπολογιστική Πολυπλοκότητα των προβλημάτων ανίχνευσης γραφημάτων. Στο τέλος της εργασίας αυτής θα κάνουμε μια συνοπτική παρουσίαση των δικών μας αποτελεσμάτων και των κεντρικών ιδεών που διέπουν την απόδειξη τους.
Defended: 04 Φεβρουαρίου 2014.