Ο φοιτητής του προγράμματος Φίλιππος Μαυρόπουλος θα παρουσιάσει τη διπλωματική του εργασία με θέμα:
Ισοδύναμοι Ορισμοί για το Δισυνεκτικό Δεντροβάθος και ένας Πολυωνυμικός Πυρήνας
την Τρίτη 8 Νοεμβρίου 2022 και ώρα 14:00, μέσω τηλεμετάδοσης *.
Σύνοψη Διπλωματικής:
Η δισυνεκτική απόσταση εξάλειψης είναι μία παράμετρος σε γραφήματα που μετράει την "απόσταση" των δισυνεκτικών συνιστωσών ενός γραφήματος από μία δεδομένη κλάση γραφημάτων. Όταν η υποδεικνούμενη κλάση γραφημάτων είναι η κλάση των γραφημάτων& χωρίς ακμές, χρησιμοποιούμε τον όρο δισυνεκτικό δεντροβάθος για να περιγράψουμε την παράμετρο. Στην παρούσα διπλωματική, αποδεικνύουμε ότι το δισυνεκτικό δεντροβάθος είναι ισοδύναμο με το ελάχιστο πλήθος χρωμάτων ενός χρωματισμού που αποδίδει κορυφή μοναδικού χρώματος σε κάθε δισυνεκτικό υπογράφημα του γραφήματος. Επιπροσθέτως, εισάγουμε μια ειδική περίπτωση ενός μη έγκυρου ακμοχρωματισμού που μπορεί να λειτουργήσει ως ένας εναλλακτικός ορισμός του δισυνεκτικού δεντροβάθους, ο οποίος καλείται κατάταξη ακμών κύκλου. Έπειτα, συνδέουμε το δισυνεκτικό δεντροβάθος με παίγνια αναζήτησης σε γραφήματα, εισάγοντας δύο παραλλαγές του παίγνιου "κλέφτες και αστυνόμοι" οι οποίες μπορούν να χρησιμοποιηθούν για τον υπολογισμό του δισυνεκτικού δεντροβάθους ενός γραφήματος. Τέλος, αποδεικνύουμε ότι το δισυνεκτικό δεντροβάθος επιδέχεται πολυωνυμικό πυρήνα παραμετρικοποιημένο ως προς το μέγεθος του Καλύμματος Κορυφών.
Η Επιτροπή,
Αρχοντία Χ. Γιαννοπούλου (Επιβλέπουσα),
Τμήμα Πληροφορικής και Τηλεπικοινωνιών Ε.Κ.Π.Α.
Δημήτριος Μ. Θηλυκός,
Τμήμα Μαθηματικών Ε.Κ.Π.Α.
Σταύρος Κολλιόπουλος,
Τμήμα Πληροφορικής και Τηλεπικοινωνιών Ε.Κ.Π.Α
* Σύνδεσμος: https://uoa.webex.com/uoa/j.php?MTID=m8d54021a5359b15e1e2fe43d3aa3424b