National and Kapodistrian University of Athens
Παρεμποδι?σεις και Αλγο?ριθμοι για Προβλη?ματα Ανι?χνευσης Γραφημα?των
Abstract
dc:descriptionΗ Ανιχνευση Γραφηματων αποτελει εναν κλαδο των Διακριτων Μαθηματικων με πληθος εφαρμογων σε πολλους τομεις της Θεωρητικης Πληροφορικης. Παρουσιαζει επισης μεγαλο θεωρητικο ενδιαφερον καθως μεσω αυτης εκφραζονται πολλα σημα- ντικα συνδυαστικα προβληματα. Στα πρωτα κεφαλαια αυτης της εργασιας θα παρουσιασουμε τα κινητρα που ωθη- σαν τους ερευνητες να ασχοληθουν με την ανιχνευση γραφηματων, θα ορισουμε τυπικα τους τρεις βασικους τυπους της και θα παρουσιασουμε τις σημαντικοτερες παραλλαγες τους. Στη συνεχεια θα αναλυσουμε τις εννοιες της μονοτονιας και της συνεκτικοτητας και θα καταγραψουμε μερικα αποτελεσματα απο τη βιβλιογραφια. Το δευτερο σκελος της εργασιας αυτης ειναι η μελετη της Θεωριας Μερικων Δια- ταξεων σε κλασεις γραφηματων και πως απο αυτη προκυπτει ο χαρακτηρισμος της κλασης μεσω ενος συνολου απαγορευμενων γραφηματων, το οποιο καλειται Συνολο Παρεμποδισης της κλασης. Αφου αναφερουμε συνοπτικα τις απαραιτητες εννοιες, θα παρουσιασουμε ολα τα εως τωρα γνωστα συνολα παρεμποδισης για κλασεις γραφημα- των με φραγμενο αριθμο ανιχνευσης. Το μεγαλυτερο σε μεγεθος συνολο που θα ανα- φερθει συγκαταλεγεται στα αποτελεσματα δικης μας εργασιας, που βρισκεται ακομα υπο συγγραφη. Η ανιχνευση γραφηματων συνδεεται αρρηκτα με τις Παραμετρους Πλατους γρα- φηματος. Τα περισσοτερα αποτελεσματα της βιβλιογραφιας αφορουν τις παραμετρους αυτες καθως η ορολογια τους διευκολυνει αρκετα την αποδειξη των θεωρηματων. Στο Κεφαλαιο 6 θα ορισθουν οι σημαντικοτερες παραμετροι πλατους γραφηματος και θα παρουσιαστει ο τροπος που σχετιζονται με τους αριθμους ανιχνευσης. Το τριτο σκελος της εργασιας αυτης αφορα την Υπολογιστικη Πολυπλοκοτητα των προβληματων ανιχνευσης γραφηματων. Στο τελος της εργασιας αυτης θα κανουμε μια συνοπτικη παρουσιαση των δικων μας αποτελεσματων και των κεντρικων ιδεων που διεπουν την αποδειξη τους.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Ζώρος Δημήτριος
Rights
- Language dc:language
- Ελληνικά, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:1319352