Παρεμποδίσεις των απόγειων-Ψευδοδασών ως προς την σχέση του ελάσσονος

Submitted by admin on Sat, 12/03/2022 - 11:03
Όνομα
Κωνσταντίνος Τσατσάνης
Ημερομηνία παρουσίασης
30-03-2022
Τριμελής επιτροπή
Αρχοντία Χ. Γιαννοπούλου (Επιβλέπουσα)
Δημήτρης Ζώρος
Σταύρος Κολλιόπουλος
Σύνοψη

Ένα γράφημα ανήκει στην κλάση των Ψευδοδασών αν κάθε συνεκτική συνιστώσα του περιέχει το πολύ έναν κύκλο. Ένα γράφημα είναι απόγειο-Ψευδοδάσος αν μπορεί να μετατραπεί σε Ψευδοδάσος με την αφαίρεση μίας κορυφής. Έχουμε εντοπίσει τα 33 γραφήματα τα οποία αποτελούν το Σύνολο Παρεμπόδισης για την κλάση γραφημάτων απόγεια-Ψευδοδάση, δηλαδή τα ελαχιστικά γραφήματα ως προς την σχέση του ελάσσονος, τα οποία δεν είναι απόγεια-Ψευδοδάση.