Κατεύθυνση / ειδίκευση Θεωρητική Πληροφορική (ΘΕΩ)
Βιβλιοθήκη Σχολής Θετικών Επιστημών

2015-02-26

2015

Πετρόπουλος Άγγελος

Βασίλειος Ζησιμόπουλος Καθηγητής

Το πρόβλημα των ζωτικών σημείων σε γραφήματα

Ελληνικά

The problem of vital points in graphs

Η γνώση των κρίσιμων σημείων ενός συστήματος είναι πολύ σημαντική, έτσι ώστε να
μπορούν να ληφθούν τα κατάλληλα μέτρα για την προστασία του από εσκεμμένες
κακόβουλες ενέργειες (όπως τρομοκρατικές ενέργειες) ή φυσικές καταστροφές. Τα
συστήματα αυτά εκφράζονται μαθηματικά μέσω διαφόρων προβλημάτων πάνω σε
γραφήματα, όπως το ελάχιστο ζευγνύον δέντρο, το μέγιστο ταίριασμα, το πρόβλημα
των p-διαμέσων κλπ. Έτσι για παράδειγμα μπορεί να καταστραφεί κάποιο κομμάτι
του οδικού δικτύου (αυτό σε ένα γράφημα μεταφράζεται σε ακμή/ακμές) ή κάποια
εγκατάσταση (δηλαδή κάποιος κόμβος/οι) με αποτέλεσμα κάποιος (κόμβος) πελάτης
να πρέπει να βρει κάποια εναλλακτική
λύση με κατά πάσα πιθανότητα μεγαλύτερο πλέον κόστος. Οπότε σε ένα γράφημα
είναι σημαντικό να γνωρίζουμε εκ των προτέρων ποιές ακμές ή κόμβοι άμα
καταστραφούν θα έχουμε ως αποτέλεσμα μια νέα λύση με την μεγαλύτερη αύξηση του
κόστους, έτσι ώστε να ληφθούν κατάλληλα μέτρα (όπως για παράδειγμα ενισχυμένα
μέτρα φύλαξης). Αυτά τα
προβλήματα για γενικό k (αριθμό ακμών ή κόμβων) είναι συνήθως NP-hard. Ως
αποτέλεσμα για γενικό και μεγάλο k ακριβείς αλγόριθμοι πάνω σε αυτά έχουν
κυρίως θεωρητικό ενδιαφέρον. Πρακτικό ενδιαφέρον έχει η έρευνα και μελέτη
προσεγγιστικών αλγόριθμων έτσι ώστε να έχουμε κάποια λύση σε εύλογο χρονικό
διάστημα με ένα σφάλμα το οποίο δεν ξεπερνάει κάποιο επιθυμητό όριο. Στην
παρούσα εργασία γίνεται μελέτη και παρουσίαση αλγορίθμων και μελετών για την
επίλυση τέτοιου είδους προβλημάτων από την υπάρχουσα μέχρι σήμερα βιβλιογραφία.

Ζωτικές ακμές/κόμβοι, Κρίσιμα σημεία , Μοντέλα προστασίας, Ακριβείς αλγόριθμοι, Προσεγγιστικοί αλγόριθμοι

Όχι

0

Ναι

39

70

Δεν επιτρέπεται η πρόσβαση στο αρχείο. H πρόσβαση επιτρέπεται μόνο εντός του δικτύου του ΕΚΠΑ.

https://pergamos.lib.uoa.gr/uoa/dl/object/1320456