Structural properties of signed - graphic matroids

Η παρούσα διδακτορική διατριβή παρέχει δομικά αποτελέσματα για τα προσημασμένα-γραφικά μητροειδή εστιάζοντας κυρίως σε δύο υποκλάσεις τους τα δυαδικά και τα τετραδικά προσημασμένα-γραφικά μητροειδή. Η κλάση των τετραδικών προσημασμένων-γραφικών μητροειδών αποσυνθέτεται και οι κλάσεις των συγγραφικών προσημασμένων-γραφικών μητροειδών και των δυαδικών προσημασμένων-γραφικών μητροειδών χαρακτηρίζονται μέσω δομικών θεωρημάτων. Πιο συγκεκριμένα, παρουσιάζεται ένας χαρακτηρισμός για την κλάση των συγγραφικών προσημασμένων-γραφικών μητροειδών που βασίζεται σε ιδιότητες των συγκυκλωμάτων. Επιπλέον, παρουσιάζονται ένας χαρακτηρισμός των δυαδικών προσημασμένων-γραφικών μητροειδών και δύο αλγόριθμοι. Όσον αφορά τα περίπλοκα προσημασμένα γραφήματα, ορίζουμε μια πράξη που διατηρεί τον αριθμό των αρνητικών κύκλων. Ως συνέπεια, αποδεικνύουμε ότι το πλήθος των αρνητικών κύκλων στα περίπλοκα προσημασμένα γραφήματα είναι πολυωνυμικά φραγμένο από το πλήθος των αρνητικών κύκλων των προσημασμένων γραφημάτων που ανήκουν σε δύο καλά ορισμένες κλάσεις. Η κλάση των τετραδικών προσημασμένων-γραφικών μητροειδών χαρακτηρίζεται μέσω ενός θεωρήματος αποσύνθεσης σύμφωνα με το οποίο η ύπαρξη ενός μη-γραφικού συγκυκλώματος που διαχωρίζει τις γέφυρες και αποσυνθέτει το μητροειδές σε ένα γραφικό έλασσον και ένα προσημασμένο-γραφικό έλασσον είναι ικανές και αναγκαίες συνθήκες για να είναι το μητροειδές προσημασμένο-γραφικό. Ως αποτέλεσμα, προσδιορίζονται οι δομικοί λίθοι των τετραδικών προσημασμένων-γραφικών μητροειδών οι οποίοι είναι γραφικά μητροειδή και προσημασμένα-γραφικά μητροειδή τα οποία μετατρέπονται σε γραφικά μετά τη διαγραφή οποιουδήποτε συγκυκλώματος. Το θεώρημα αποσύνθεσης των τετραδικών προσημασμένων-γραφικών μητροειδών, το οποίο βασίζεται σε μια πράξη που ονομάζεται αστρική σύνθεση και στα γνωστά κ-αθροίσματα, αποτελεί το θεωρητικό υπόβαθρο για έναν αλγόριθμο αναγνώρισης. Τέλος παρουσιάζεται μια επισκόπηση των πιο σημαντικών αποτελεσμάτων και εικασιών της Θεωρίας Μητροειδών.