Μονάδα:
Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και ΥπολογισμούΒιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2014-02-04
Συγγραφέας:
Ζώρος Δημήτριος
Στοιχεία επιβλεπόντων καθηγητών:
Αναπλ. Καθηγητής Δημήτριος Μ. Θηλυκός (επιβλέπων), Καθηγητής Ελευθέριος Κυρούσης, Αναπλ. Καθηγητής Σταύρος Κολλιόπουλος
Πρωτότυπος Τίτλος:
Παρεμποδι?σεις και Αλγο?ριθμοι για Προβλη?ματα Ανι?χνευσης Γραφημα?των
Γλώσσες εργασίας:
Ελληνικά
Μεταφρασμένος τίτλος:
Obstructions and Algorithms for Graph Searching Problems
Περίληψη:
Η Ανιχνευση Γραφηματων αποτελει εναν κλαδο των Διακριτων Μαθηματικων με
πληθος εφαρμογων σε πολλους τομεις της Θεωρητικης Πληροφορικης.
Παρουσιαζει επισης μεγαλο θεωρητικο ενδιαφερον καθως μεσω αυτης
εκφραζονται πολλα σημα- ντικα συνδυαστικα προβληματα. Στα πρωτα κεφαλαια
αυτης της εργασιας θα παρουσιασουμε τα κινητρα που ωθη- σαν τους
ερευνητες να ασχοληθουν με την ανιχνευση γραφηματων, θα ορισουμε τυπικα
τους τρεις βασικους τυπους της και θα παρουσιασουμε τις σημαντικοτερες
παραλλαγες τους. Στη συνεχεια θα αναλυσουμε τις εννοιες της μονοτονιας και
της συνεκτικοτητας και θα καταγραψουμε μερικα αποτελεσματα απο τη
βιβλιογραφια. Το δευτερο σκελος της εργασιας αυτης ειναι η μελετη της
Θεωριας Μερικων Δια- ταξεων σε κλασεις γραφηματων και πως απο αυτη
προκυπτει ο χαρακτηρισμος της κλασης μεσω ενος συνολου απαγορευμενων
γραφηματων, το οποιο καλειται Συνολο Παρεμποδισης της κλασης. Αφου
αναφερουμε συνοπτικα τις απαραιτητες εννοιες, θα παρουσιασουμε ολα τα
εως τωρα γνωστα συνολα παρεμποδισης για κλασεις γραφημα- των με
φραγμενο αριθμο ανιχνευσης. Το μεγαλυτερο σε μεγεθος συνολο που θα ανα-
φερθει συγκαταλεγεται στα αποτελεσματα δικης μας εργασιας, που βρισκεται
ακομα υπο συγγραφη. Η ανιχνευση γραφηματων συνδεεται αρρηκτα με τις
Παραμετρους Πλατους γρα- φηματος. Τα περισσοτερα αποτελεσματα της
βιβλιογραφιας αφορουν τις παραμετρους αυτες καθως η ορολογια τους
διευκολυνει αρκετα την αποδειξη των θεωρηματων. Στο Κεφαλαιο 6 θα
ορισθουν οι σημαντικοτερες παραμετροι πλατους γραφηματος και θα
παρουσιαστει ο τροπος που σχετιζονται με τους αριθμους ανιχνευσης. Το
τριτο σκελος της εργασιας αυτης αφορα την Υπολογιστικη Πολυπλοκοτητα των
προβληματων ανιχνευσης γραφηματων. Στο τελος της εργασιας αυτης θα
κανουμε μια συνοπτικη παρουσιαση των δικων μας αποτελεσματων και των
κεντρικων ιδεων που διεπουν την αποδειξη τους.
Λέξεις-κλειδιά:
Σύνολα Παρεμπόδισης, Ανίχνευση Γραφημάτων, Αλγόριθμοι, Διακριτά Μαθηματικά, Θεωρία Γραφημάτων
Αρ. σελίδων ευρετηρίου:
iii-iv
Αρ. βιβλιογραφικών αναφορών:
49
