Back to search

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

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Πετρόπουλος Άγγελος. Το πρόβλημα των ζωτικών σημείων σε γραφήματα. 2015. https://pergamos.lib.uoa.gr/uoa/dl/object/1320456