National and Kapodistrian University of Athens
Το πρόβλημα των ζωτικών σημείων σε γραφήματα
Abstract
dc:descriptionΗ γνώση των κρίσιμων σημείων ενός συστήματος είναι πολύ σημαντική, έτσι ώστε να μπορούν να ληφθούν τα κατάλληλα μέτρα για την προστασία του από εσκεμμένες κακόβουλες ενέργειες (όπως τρομοκρατικές ενέργειες) ή φυσικές καταστροφές. Τα συστήματα αυτά εκφράζονται μαθηματικά μέσω διαφόρων προβλημάτων πάνω σε γραφήματα, όπως το ελάχιστο ζευγνύον δέντρο, το μέγιστο ταίριασμα, το πρόβλημα των p-διαμέσων κλπ. Έτσι για παράδειγμα μπορεί να καταστραφεί κάποιο κομμάτι του οδικού δικτύου (αυτό σε ένα γράφημα μεταφράζεται σε ακμή/ακμές) ή κάποια εγκατάσταση (δηλαδή κάποιος κόμβος/οι) με αποτέλεσμα κάποιος (κόμβος) πελάτης να πρέπει να βρει κάποια εναλλακτική λύση με κατά πάσα πιθανότητα μεγαλύτερο πλέον κόστος. Οπότε σε ένα γράφημα είναι σημαντικό να γνωρίζουμε εκ των προτέρων ποιές ακμές ή κόμβοι άμα καταστραφούν θα έχουμε ως αποτέλεσμα μια νέα λύση με την μεγαλύτερη αύξηση του κόστους, έτσι ώστε να ληφθούν κατάλληλα μέτρα (όπως για παράδειγμα ενισχυμένα μέτρα φύλαξης). Αυτά τα προβλήματα για γενικό k (αριθμό ακμών ή κόμβων) είναι συνήθως NP-hard. Ως αποτέλεσμα για γενικό και μεγάλο k ακριβείς αλγόριθμοι πάνω σε αυτά έχουν κυρίως θεωρητικό ενδιαφέρον. Πρακτικό ενδιαφέρον έχει η έρευνα και μελέτη προσεγγιστικών αλγόριθμων έτσι ώστε να έχουμε κάποια λύση σε εύλογο χρονικό διάστημα με ένα σφάλμα το οποίο δεν ξεπερνάει κάποιο επιθυμητό όριο. Στην παρούσα εργασία γίνεται μελέτη και παρουσίαση αλγορίθμων και μελετών για την επίλυση τέτοιου είδους προβλημάτων από την υπάρχουσα μέχρι σήμερα βιβλιογραφία.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Πετρόπουλος Άγγελος
Rights
- Language dc:language
- Ελληνικά, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:1320456