mpla.math.uoa.gr
Font size: Αα Αα Αα hide gadgets
You are here: Theses » MSc » Michael Samaris

MSc thesis of Michael Samaris

Αποσυνθέσεις σφαιρικών τομών και σύνολα κυριαρχίας σε επίπεδα γραφήματα

Supervisor: Dimitrios M. Thilikos

́Ενα σημαντικό αποτέλεσμα στη Θεωρία Γραφημάτων αποτελεί η απόδειξη της εικασίας του Wagner από τους Neil Robertson και Paul D. Seymour. στη σειρά εργασιών ‘Ελλάσσονα Γραφήματα’ απο το 1983 εώς το 2011. Η εικασία αυτή λέει ότι στην κλάση των γραφημάτων δεν υπάρχει άπειρη αντιαλυσίδα ώς προς τη σχέση των ελλασόνων γραφημάτων. Η Θεωρία που αναπτύχθηκε για την απόδειξη αυτής της εικασίας είχε και έχει ακόμα σημαντικό αντίκτυπο τόσο στην δομική όσο και στην αλγοριθμική Θεωρία Γραφημάτων, άλλα και σε άλλα πεδία όπως η Παραμετρική Πολυπλοκότητα. Στα πλάισια της απόδειξης οι συγγραφείς εισήγαγαν και νέες παραμέτρους πλά- τους. Σε αυτές ήταν η κλαδοαποσύνθεση και το κλαδοπλάτος ενός γραφήματος. Η παράμετρος αυτή χρησιμοποιήθηκε ιδιαίτερα στο σχεδιασμό αλγορίθμων και στην χρήση της τεχνικής ‘διαίρει και βασίλευε’. Επιπλεόν εισήχθησαν νέες παρεμφερείς έννοιες όπως οι αποσυνθέσεις σφαιρικών τομών που είναι κλαδοαποσυνθέσεις στην κλαση των επίπεδων γραφημάτων που έχουν κάποιες επιπλέον ιδιότητες. Στην εξέλιξη της έρευνας υπήρξαν σημαντικά αποτελέσμα σχετικά με το κλαδο- πλάτος στην κλάση των επίπεδων γραφημάτων. Οι Fedor V. Fomin και Δημήτριος Μ. Θηλυκός απέδειξαν ότι το κλαδοπλάτος ενός επίπεδου γραφήματος με n κορυφές είναι το πολύ √4.5 · n. Βασιζόμενος σε αυτό το αποτέλεσμα, ο Δημήτριος Μ. Θη- λυκός συσχέτισχε το κλαδοπλάτος με μια άλλη παράμετρο σε επίπεδα γραφήματα, το r-ακτινικό σύνολο κυριαρχίας. Απέδειξε ότι αν ένα εμβαπτισμένο επίπεδο γράφημα έχει r- ακτινικό σύνολο κυριαρχίας το πολύ k, τότε το κλαδοπλάτος του γραφήματος θα είναι το πολύ r·√4.5·k. Η παρούσα διπλωματική εργασία κάνει μια ποιοτική επέκταση του αποτελέσματος αυτού. Αποδεικνύουμε ότι το παραπάνω όριο μπορεί να αναζητηθεί σε ένα δάσος που είναι υπογράφημα του δέντρου μιας αποσύνθεσης σφαιρικών τομών του γραφήματος, όπου το μέγεθος του είναι γραμμικό ως προς το k.

Defended: June 24, 2016.

Scientific committee

Download

Download thesis.

Reporter

Web standards: XHTML1.0, CSS3.
© 1996 – 2018 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.