1. Αποθετήριο Παραδοτέων Υποτρόφων Δράσεων ΕΣΠΑ Τριτοβάθμιας Εκπαίδευσης 2017-2023
2. Όλο το Αποθετήριο
3. Υποψήφιοι διδάκτορες

Τύπος:	Διδακτορική διατριβή
Τίτλος:	Structural properties of signed-graphic matroids
Εναλλακτικός τίτλος:	Δομικές ιδιότητες προσημασμένων-γραφικών μητροειδών
Συγγραφέας:	[EL] Βρεττά, Ελένη-Μαρία[EN] Vretta, Eleni-Maria
Επιβλέπων διατριβής:	[EL] Πιτσούλης, Λεωνίδας[EN] Pitsoulis, Leonidas
Ημερομηνία:	Απρ-2019
Περίληψη:	Η παρούσα διδακτορική διατριβή παρέχει δομικά αποτελέσματα για τα προσημασμένα-γραφικά μητροειδή εστιάζοντας κυρίως σε δύο υποκλάσεις τους τα δυαδικά και τα τετραδικά προσημασμένα-γραφικά μητροειδή. Η κλάση των τετραδικών προσημασμένων-γραφικών μητροειδών αποσυνθέτεται και οι κλάσεις των συγγραφικών προσημασμένων-γραφικών μητροειδών και των δυαδικών προσημασμένων-γραφικών μητροειδών χαρακτηρίζονται μέσω δομικών θεωρημάτων. Πιο συγκεκριμένα, παρουσιάζεται ένας χαρακτηρισμός για την κλάση των συγγραφικών προσημασμένων-γραφικών μητροειδών που βασίζεται σε ιδιότητες των συγκυκλωμάτων. Επιπλέον, παρουσιάζονται ένας χαρακτηρισμός των δυαδικών προσημασμένων-γραφικών μητροειδών και δύο αλγόριθμοι. Όσον αφορά τα περίπλοκα προσημασμένα γραφήματα, ορίζουμε μια πράξη που διατηρεί τον αριθμό των αρνητικών κύκλων. Ως συνέπεια, αποδεικνύουμε ότι το πλήθος των αρνητικών κύκλων στα περίπλοκα προσημασμένα γραφήματα είναι πολυωνυμικά φραγμένο από το πλήθος των αρνητικών κύκλων των προσημασμένων γραφημάτων που ανήκουν σε δύο καλά ορισμένες κλάσεις. Η κλάση των τετραδικών προσημασμένων-γραφικών μητροειδών χαρακτηρίζεται μέσω ενός θεωρήματος αποσύνθεσης σύμφωνα με το οποίο η ύπαρξη ενός μη-γραφικού συγκυκλώματος που διαχωρίζει τις γέφυρες και αποσυνθέτει το μητροειδές σε ένα γραφικό έλασσον και ένα προσημασμένο-γραφικό έλασσον είναι ικανές και αναγκαίες συνθήκες για να είναι το μητροειδές προσημασμένο-γραφικό. Ως αποτέλεσμα, προσδιορίζονται οι δομικοί λίθοι των τετραδικών προσημασμένων-γραφικών μητροειδών οι οποίοι είναι γραφικά μητροειδή και προσημασμένα-γραφικά μητροειδή τα οποία μετατρέπονται σε γραφικά μετά τη διαγραφή οποιουδήποτε συγκυκλώματος. Το θεώρημα αποσύνθεσης των τετραδικών προσημασμένων-γραφικών μητροειδών, το οποίο βασίζεται σε μια πράξη που ονομάζεται αστρική σύνθεση και στα γνωστά κ-αθροίσματα, αποτελεί το θεωρητικό υπόβαθρο για έναν αλγόριθμο αναγνώρισης. Τέλος παρουσιάζεται μια επισκόπηση των πιο σημαντικών αποτελεσμάτων και εικασιών της Θεωρίας Μητροειδών. In this doctoral thesis we furnish structural results for signed-graphic matroids focusing mainly on two subclasses binary and quaternary signed-graphic matroids. Our purpose is to decompose the class of quaternary signed-graphic matroids and to characterize the classes of cographic signed-graphic and binary signed-graphic matroids. We provide a characterization for the class of cographic signed-graphic matroids which is based on properties of cocircuits. To achieve this, we show that each cographic excluded-minor of signed-graphic matroids contains a Fournier triple with two non-graphic cocircuits. Furthermore, we present a characterization for binary signed-graphic matroids along with two algorithms. A polynomial algorithm which checks whether a binary matroid is isomorphic with the signed-graphic matroid of a given jointless signed graph and a recognition algorithm for binary signed-graphic matroids. Regarding tangled signed graphs, we define an operation which preserves the number of negative cycles. As a consequence, we prove that the number of negative cycles in tangled signed graphs is polynomially bounded by the number of negative cycles of signed graphs belonging to two well-defined classes. The class of quaternary signed-graphic matroids is characterized by a decomposition theorem which states that the existence of a non-graphic and bridgeseparable cocircuit which decomposes a quaternary matroid into a graphic minor and a signed-graphic minor are necessary and sufficient conditions for the matroid to be signed-graphic. As a result, we determine the building blocks of quaternary signed-graphic matroids which are graphic matroids and signed-graphic matroids which become graphic upon the deletion of any cocircuit. To this end quaternary signed-graphic matroids are studied in terms of signed graphs representing them. Moreover, we prove that hereditary properties under k-sums permit desirable graphical representations. The decomposition theorem, which is based on a new operation called star composition and k-sums, constitutes the theoretical background for a recognition algorithm. A survey of important results of Matroid Theory as well as conjectures and recent work on the field are also presented.
Γλώσσα:	Αγγλικά
Τόπος δημοσίευσης:	Θεσσαλονίκη, Ελλάδα
Σελίδες:	204
Θεματική κατηγορία:	[EL] Διακριτά μαθηματικά και Συνδυαστική[EN] Discrete Mathematics and Combinatorics
Λέξεις-κλειδιά:	προσημασμένα-γραφικά μητροειδή; τετραδικά προσημασμένα γραφικά μητροειδή; αποσύνθεση τετραδικών προσημασμένων-γραφικών μητροειδών; δυαδικά προσημασμένα-γραφικά μητροειδή; διαχωρισμός γεφυρών
Κάτοχος πνευματικών δικαιωμάτων:	© Ελένη-Μαρία Βρεττά
Διατίθεται ανοιχτά στην τοποθεσία:	https://www.didaktorika.gr/eadd/handle/10442/45563
Σημειώσεις:	This thesis was implemented with a scholarship from the State Scholarships Foundation of Greece which was funded by the «Scholarship Program for Postgraduate Studies of the Second Cycle Studies» with resources from the Operational Program «Human Resources Development, Education and Lifelong Learning», 2014-2020 which was co-financed by the European Social Fund and the Greek State.
Εμφανίζεται στις συλλογές:	Υποψήφιοι διδάκτορες