{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1320456"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1320456","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Το πρόβλημα των ζωτικών σημείων σε γραφήματα","abstract":"Η γνώση των κρίσιμων σημείων ενός συστήματος είναι πολύ σημαντική, έτσι ώστε να μπορούν να ληφθούν τα κατάλληλα μέτρα για την προστασία του από εσκεμμένες κακόβουλες ενέργειες (όπως τρομοκρατικές ενέργειες) ή φυσικές καταστροφές. Τα συστήματα αυτά εκφράζονται μαθηματικά μέσω διαφόρων προβλημάτων πάνω σε γραφήματα, όπως το ελάχιστο ζευγνύον δέντρο, το μέγιστο ταίριασμα, το πρόβλημα των p-διαμέσων κλπ. Έτσι για παράδειγμα μπορεί να καταστραφεί κάποιο κομμάτι του οδικού δικτύου (αυτό σε ένα γράφημα μεταφράζεται σε ακμή/ακμές) ή κάποια εγκατάσταση (δηλαδή κάποιος κόμβος/οι) με αποτέλεσμα κάποιος (κόμβος) πελάτης να πρέπει να βρει κάποια εναλλακτική λύση με κατά πάσα πιθανότητα μεγαλύτερο πλέον κόστος. Οπότε σε ένα γράφημα είναι σημαντικό να γνωρίζουμε εκ των προτέρων ποιές ακμές ή κόμβοι άμα καταστραφούν θα έχουμε ως αποτέλεσμα μια νέα λύση με την μεγαλύτερη αύξηση του κόστους, έτσι ώστε να ληφθούν κατάλληλα μέτρα (όπως για παράδειγμα ενισχυμένα μέτρα φύλαξης). Αυτά τα προβλήματα για γενικό k (αριθμό ακμών ή κόμβων) είναι συνήθως NP-hard. Ως αποτέλεσμα για γενικό και μεγάλο k ακριβείς αλγόριθμοι πάνω σε αυτά έχουν κυρίως θεωρητικό ενδιαφέρον. Πρακτικό ενδιαφέρον έχει η έρευνα και μελέτη προσεγγιστικών αλγόριθμων έτσι ώστε να έχουμε κάποια λύση σε εύλογο χρονικό διάστημα με ένα σφάλμα το οποίο δεν ξεπερνάει κάποιο επιθυμητό όριο. Στην παρούσα εργασία γίνεται μελέτη και παρουσίαση αλγορίθμων και μελετών για την επίλυση τέτοιου είδους προβλημάτων από την υπάρχουσα μέχρι σήμερα βιβλιογραφία.","abstract_html":"Η γνώση των κρίσιμων σημείων ενός συστήματος είναι πολύ σημαντική, έτσι ώστε να μπορούν να ληφθούν τα κατάλληλα μέτρα για την προστασία του από εσκεμμένες κακόβουλες ενέργειες (όπως τρομοκρατικές ενέργειες) ή φυσικές καταστροφές. Τα συστήματα αυτά εκφράζονται μαθηματικά μέσω διαφόρων προβλημάτων πάνω σε γραφήματα, όπως το ελάχιστο ζευγνύον δέντρο, το μέγιστο ταίριασμα, το πρόβλημα των p-διαμέσων κλπ. Έτσι για παράδειγμα μπορεί να καταστραφεί κάποιο κομμάτι του οδικού δικτύου (αυτό σε ένα γράφημα μεταφράζεται σε ακμή/ακμές) ή κάποια εγκατάσταση (δηλαδή κάποιος κόμβος/οι) με αποτέλεσμα κάποιος (κόμβος) πελάτης να πρέπει να βρει κάποια εναλλακτική λύση με κατά πάσα πιθανότητα μεγαλύτερο πλέον κόστος. Οπότε σε ένα γράφημα είναι σημαντικό να γνωρίζουμε εκ των προτέρων ποιές ακμές ή κόμβοι άμα καταστραφούν θα έχουμε ως αποτέλεσμα μια νέα λύση με την μεγαλύτερη αύξηση του κόστους, έτσι ώστε να ληφθούν κατάλληλα μέτρα (όπως για παράδειγμα ενισχυμένα μέτρα φύλαξης). Αυτά τα προβλήματα για γενικό k (αριθμό ακμών ή κόμβων) είναι συνήθως NP-hard. Ως αποτέλεσμα για γενικό και μεγάλο k ακριβείς αλγόριθμοι πάνω σε αυτά έχουν κυρίως θεωρητικό ενδιαφέρον. Πρακτικό ενδιαφέρον έχει η έρευνα και μελέτη προσεγγιστικών αλγόριθμων έτσι ώστε να έχουμε κάποια λύση σε εύλογο χρονικό διάστημα με ένα σφάλμα το οποίο δεν ξεπερνάει κάποιο επιθυμητό όριο. Στην παρούσα εργασία γίνεται μελέτη και παρουσίαση αλγορίθμων και μελετών για την επίλυση τέτοιου είδους προβλημάτων από την υπάρχουσα μέχρι σήμερα βιβλιογραφία.","abstract_has_math":false,"creators":["Πετρόπουλος Άγγελος"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015","date_published":"2015","updated_at":"2026-11-19T05:26:18Z","subjects":[],"languages":["Ελληνικά","Greek"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1320456"],"render_values":[{"text":"uoadl:1320456","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1320456","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1320456","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1320456","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Πετρόπουλος Άγγελος"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["Ελληνικά","Greek"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1320456","https://pergamos.lib.uoa.gr/uoa/dl/object/1320456"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Η γνώση των κρίσιμων σημείων ενός συστήματος είναι πολύ σημαντική, έτσι ώστε να μπορούν να ληφθούν τα κατάλληλα μέτρα για την προστασία του από εσκεμμένες κακόβουλες ενέργειες (όπως τρομοκρατικές ενέργειες) ή φυσικές καταστροφές. Τα συστήματα αυτά εκφράζονται μαθηματικά μέσω διαφόρων προβλημάτων πάνω σε γραφήματα, όπως το ελάχιστο ζευγνύον δέντρο, το μέγιστο ταίριασμα, το πρόβλημα των p-διαμέσων κλπ. Έτσι για παράδειγμα μπορεί να καταστραφεί κάποιο κομμάτι του οδικού δικτύου (αυτό σε ένα γράφημα μεταφράζεται σε ακμή/ακμές) ή κάποια εγκατάσταση (δηλαδή κάποιος κόμβος/οι) με αποτέλεσμα κάποιος (κόμβος) πελάτης να πρέπει να βρει κάποια εναλλακτική λύση με κατά πάσα πιθανότητα μεγαλύτερο πλέον κόστος. Οπότε σε ένα γράφημα είναι σημαντικό να γνωρίζουμε εκ των προτέρων ποιές ακμές ή κόμβοι άμα καταστραφούν θα έχουμε ως αποτέλεσμα μια νέα λύση με την μεγαλύτερη αύξηση του κόστους, έτσι ώστε να ληφθούν κατάλληλα μέτρα (όπως για παράδειγμα ενισχυμένα μέτρα φύλαξης). Αυτά τα προβλήματα για γενικό k (αριθμό ακμών ή κόμβων) είναι συνήθως NP-hard. Ως αποτέλεσμα για γενικό και μεγάλο k ακριβείς αλγόριθμοι πάνω σε αυτά έχουν κυρίως θεωρητικό ενδιαφέρον. Πρακτικό ενδιαφέρον έχει η έρευνα και μελέτη προσεγγιστικών αλγόριθμων έτσι ώστε να έχουμε κάποια λύση σε εύλογο χρονικό διάστημα με ένα σφάλμα το οποίο δεν ξεπερνάει κάποιο επιθυμητό όριο. Στην παρούσα εργασία γίνεται μελέτη και παρουσίαση αλγορίθμων και μελετών για την επίλυση τέτοιου είδους προβλημάτων από την υπάρχουσα μέχρι σήμερα βιβλιογραφία.","The knowledge of the critical points of a system is essential, in order to take measures for its protection from intentional strikes (like terrorists attacks) or natural disasters. These systems are usually modelled as graph theoretic problems, like minimum spanning tree, maximum matching, p-median problem etc. For example, a point of a network may fail (i.e destroyed edge/s of a graph) or a facility may fail (i.e destroyed node/s) which may lead a client node to an alternative more expensive solution. So in a graph is crucial to know in advance which edges or nodes failure will lead to the most expensive solution, in order to take measures (for example reinforced patrol). These kind of problems for general k (number of edges or nodes) are usually NP-hard. As a consequence for general and big k algorithms for this kind of problem are mostly of theoretical interest. For practical purposes we need to study and research approximation algorithms for realistic computational time but with drawback some error (within a desirable bound) in the final solution. This thesis studies and presents this kind of problems from the current bibliography."]},{"key":"dc:title","label":"Title","values":["Το πρόβλημα των ζωτικών σημείων σε γραφήματα"]}]}],"canonical_facts":{"dc:creator":["Πετρόπουλος Άγγελος"],"dc:date":["2015"],"dc:description":["Η γνώση των κρίσιμων σημείων ενός συστήματος είναι πολύ σημαντική, έτσι ώστε να μπορούν να ληφθούν τα κατάλληλα μέτρα για την προστασία του από εσκεμμένες κακόβουλες ενέργειες (όπως τρομοκρατικές ενέργειες) ή φυσικές καταστροφές. Τα συστήματα αυτά εκφράζονται μαθηματικά μέσω διαφόρων προβλημάτων πάνω σε γραφήματα, όπως το ελάχιστο ζευγνύον δέντρο, το μέγιστο ταίριασμα, το πρόβλημα των p-διαμέσων κλπ. Έτσι για παράδειγμα μπορεί να καταστραφεί κάποιο κομμάτι του οδικού δικτύου (αυτό σε ένα γράφημα μεταφράζεται σε ακμή/ακμές) ή κάποια εγκατάσταση (δηλαδή κάποιος κόμβος/οι) με αποτέλεσμα κάποιος (κόμβος) πελάτης να πρέπει να βρει κάποια εναλλακτική λύση με κατά πάσα πιθανότητα μεγαλύτερο πλέον κόστος. Οπότε σε ένα γράφημα είναι σημαντικό να γνωρίζουμε εκ των προτέρων ποιές ακμές ή κόμβοι άμα καταστραφούν θα έχουμε ως αποτέλεσμα μια νέα λύση με την μεγαλύτερη αύξηση του κόστους, έτσι ώστε να ληφθούν κατάλληλα μέτρα (όπως για παράδειγμα ενισχυμένα μέτρα φύλαξης). Αυτά τα προβλήματα για γενικό k (αριθμό ακμών ή κόμβων) είναι συνήθως NP-hard. Ως αποτέλεσμα για γενικό και μεγάλο k ακριβείς αλγόριθμοι πάνω σε αυτά έχουν κυρίως θεωρητικό ενδιαφέρον. Πρακτικό ενδιαφέρον έχει η έρευνα και μελέτη προσεγγιστικών αλγόριθμων έτσι ώστε να έχουμε κάποια λύση σε εύλογο χρονικό διάστημα με ένα σφάλμα το οποίο δεν ξεπερνάει κάποιο επιθυμητό όριο. Στην παρούσα εργασία γίνεται μελέτη και παρουσίαση αλγορίθμων και μελετών για την επίλυση τέτοιου είδους προβλημάτων από την υπάρχουσα μέχρι σήμερα βιβλιογραφία.","The knowledge of the critical points of a system is essential, in order to take measures for its protection from intentional strikes (like terrorists attacks) or natural disasters. These systems are usually modelled as graph theoretic problems, like minimum spanning tree, maximum matching, p-median problem etc. For example, a point of a network may fail (i.e destroyed edge/s of a graph) or a facility may fail (i.e destroyed node/s) which may lead a client node to an alternative more expensive solution. So in a graph is crucial to know in advance which edges or nodes failure will lead to the most expensive solution, in order to take measures (for example reinforced patrol). These kind of problems for general k (number of edges or nodes) are usually NP-hard. As a consequence for general and big k algorithms for this kind of problem are mostly of theoretical interest. For practical purposes we need to study and research approximation algorithms for realistic computational time but with drawback some error (within a desirable bound) in the final solution. This thesis studies and presents this kind of problems from the current bibliography."],"dc:identifier":["uoadl:1320456","https://pergamos.lib.uoa.gr/uoa/dl/object/1320456"],"dc:language":["Ελληνικά","Greek"],"dc:title":["Το πρόβλημα των ζωτικών σημείων σε γραφήματα"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:26:18Z"}