MSc thesis defense presentation
Michael Samaris defends his MSc thesis
Date: | Friday, 24 Jun 2016 |
---|---|
Time: | 11:15 |
Location: | Univeristy of Athens, Department of Mathematics, University of Athens, Α32 |
Thesis title: | Αποσυνθέσεις σφαιρικών τομών και σύνολα κυριαρχίας σε επίπεδα γραφήματα |
Committee: |
Thesis abstract
́Ενα σημαντικό αποτέλεσμα στη Θεωρία Γραφημάτων αποτελεί η απόδειξη της εικασίας του Wagner από τους Neil Robertson και Paul D. Seymour. στη σειρά εργασιών ‘Ελλάσσονα Γραφήματα’ απο το 1983 εώς το 2011. Η εικασία αυτή λέει ότι στην κλάση των γραφημάτων δεν υπάρχει άπειρη αντιαλυσίδα ώς προς τη σχέση των ελλασόνων γραφημάτων. Η Θεωρία που αναπτύχθηκε για την απόδειξη αυτής της εικασίας είχε και έχει ακόμα σημαντικό αντίκτυπο τόσο στην δομική όσο και στην αλγοριθμική Θεωρία Γραφημάτων, άλλα και σε άλλα πεδία όπως η Παραμετρική Πολυπλοκότητα. Στα πλάισια της απόδειξης οι συγγραφείς εισήγαγαν και νέες παραμέτρους πλά- τους. Σε αυτές ήταν η κλαδοαποσύνθεση και το κλαδοπλάτος ενός γραφήματος. Η παράμετρος αυτή χρησιμοποιήθηκε ιδιαίτερα στο σχεδιασμό αλγορίθμων και στην χρήση της τεχνικής ‘διαίρει και βασίλευε’. Επιπλεόν εισήχθησαν νέες παρεμφερείς έννοιες όπως οι αποσυνθέσεις σφαιρικών τομών που είναι κλαδοαποσυνθέσεις στην κλαση των επίπεδων γραφημάτων που έχουν κάποιες επιπλέον ιδιότητες. Στην εξέλιξη της έρευνας υπήρξαν σημαντικά αποτελέσμα σχετικά με το κλαδο- πλάτος στην κλάση των επίπεδων γραφημάτων. Οι Fedor V. Fomin και Δημήτριος Μ. Θηλυκός απέδειξαν ότι το κλαδοπλάτος ενός επίπεδου γραφήματος με n κορυφές είναι το πολύ √4.5 · n. Βασιζόμενος σε αυτό το αποτέλεσμα, ο Δημήτριος Μ. Θη- λυκός συσχέτισχε το κλαδοπλάτος με μια άλλη παράμετρο σε επίπεδα γραφήματα, το r-ακτινικό σύνολο κυριαρχίας. Απέδειξε ότι αν ένα εμβαπτισμένο επίπεδο γράφημα έχει r- ακτινικό σύνολο κυριαρχίας το πολύ k, τότε το κλαδοπλάτος του γραφήματος θα είναι το πολύ r·√4.5·k. Η παρούσα διπλωματική εργασία κάνει μια ποιοτική επέκταση του αποτελέσματος αυτού. Αποδεικνύουμε ότι το παραπάνω όριο μπορεί να αναζητηθεί σε ένα δάσος που είναι υπογράφημα του δέντρου μιας αποσύνθεσης σφαιρικών τομών του γραφήματος, όπου το μέγεθος του είναι γραμμικό ως προς το k.