{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:2800850"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:2800850","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Η αρχή των μεγάλων αποκλίσεων για το τυχαίο γράφημα Erdős–Rényi","abstract":"Έστω G(n,p) να είναι το τυχαίο γράφημα με n κόμβους όπου οι ακμές του προστίθενται ανεξάρτητα η καθεμία με μία σταθερή πιθανότητα p. Το μοντέλο αυτό ονομάζεται τυχαίο γράφημα Erdős–Rényi. Πως μοιάζει ένα τέτοιο γράφημα ανάλογα με το πόσο μεγάλη είναι η πιθανότητα p; Πόσους κόμβους περιέχει η μεγαλύτερη συνεκτική συνιστώσα ενός τέτοιου γραφήματος; Προκύπτει ότι αν η πιθανότητα p είναι αρκετά μικρή τότε όλες οι συνιστώσες του γραφήματος είναι μικρές υπό την έννοια ότι καμιά τους δεν περιέχει περισσότερους από logn κόμβους. Από την άλλη αν η πιθανότητα είναι αρκετά μεγάλη τότε υπάρχει μια μεγάλη συνεκτική συνιστώσα που περιέχει ένα μεγάλο μέρος των κόμβων. Πως μοιάζει ένα γράφημα Erdős–Rényi όταν γνωρίζουμε εκ των προτέρων ότι συμβαίνει ένα σπάνιο γεγονός; Αυτή η απάντηση μπορεί να δοθεί για σταθερό p και για n που τείνει στο άπειρο. Για να μελετήσουμε τα παραπάνω θα χρειαστεί να κατασκευάσουμε τον κατάλληλο χώρο, μέσα στον οποίο θα μπορούμε να εφαρμόσουμε την αρχή των μεγάλων αποκλίσεων. Η εργασία αυτή έχει σκοπό να παρουσιάσει το τυχαίο γράφημα Erdős–Rényi και ύστερα υπό το πρίσμα της αρχής των μεγάλων αποκλίσεων να απαντήσει και να αποδείξει τα παραπάνω ερωτήματα. Ως εφαρμογή του βασικού θεωρήματος των μεγάλων αποκλίσεων θα δούμε πως μοιάζει το τυχαίο γράφημα Erdős–Rényi όταν γνωρίζουμε τον αριθμό των τριγώνων του γραφήματος.","abstract_html":"Έστω G(n,p) να είναι το τυχαίο γράφημα με n κόμβους όπου οι ακμές του προστίθενται ανεξάρτητα η καθεμία με μία σταθερή πιθανότητα p. Το μοντέλο αυτό ονομάζεται τυχαίο γράφημα Erdős–Rényi. Πως μοιάζει ένα τέτοιο γράφημα ανάλογα με το πόσο μεγάλη είναι η πιθανότητα p; Πόσους κόμβους περιέχει η μεγαλύτερη συνεκτική συνιστώσα ενός τέτοιου γραφήματος; Προκύπτει ότι αν η πιθανότητα p είναι αρκετά μικρή τότε όλες οι συνιστώσες του γραφήματος είναι μικρές υπό την έννοια ότι καμιά τους δεν περιέχει περισσότερους από logn κόμβους. Από την άλλη αν η πιθανότητα είναι αρκετά μεγάλη τότε υπάρχει μια μεγάλη συνεκτική συνιστώσα που περιέχει ένα μεγάλο μέρος των κόμβων. Πως μοιάζει ένα γράφημα Erdős–Rényi όταν γνωρίζουμε εκ των προτέρων ότι συμβαίνει ένα σπάνιο γεγονός; Αυτή η απάντηση μπορεί να δοθεί για σταθερό p και για n που τείνει στο άπειρο. Για να μελετήσουμε τα παραπάνω θα χρειαστεί να κατασκευάσουμε τον κατάλληλο χώρο, μέσα στον οποίο θα μπορούμε να εφαρμόσουμε την αρχή των μεγάλων αποκλίσεων. Η εργασία αυτή έχει σκοπό να παρουσιάσει το τυχαίο γράφημα Erdős–Rényi και ύστερα υπό το πρίσμα της αρχής των μεγάλων αποκλίσεων να απαντήσει και να αποδείξει τα παραπάνω ερωτήματα. Ως εφαρμογή του βασικού θεωρήματος των μεγάλων αποκλίσεων θα δούμε πως μοιάζει το τυχαίο γράφημα Erdős–Rényi όταν γνωρίζουμε τον αριθμό των τριγώνων του γραφήματος.","abstract_has_math":false,"creators":["Κονδυλάτος Σπυρίδων","Kondylatos Spyridon"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018","date_published":"2018","updated_at":"2026-11-19T05:32:09Z","subjects":["Θετικές Επιστήμες","Science"],"languages":["Ελληνικά","Greek"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:2800850"],"render_values":[{"text":"uoadl:2800850","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2800850","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2800850","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%3A2800850","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Κονδυλάτος Σπυρίδων","Kondylatos Spyridon"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2018"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Θετικές Επιστήμες","Science"]}]},{"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:2800850","https://pergamos.lib.uoa.gr/uoa/dl/object/2800850"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Έστω G(n,p) να είναι το τυχαίο γράφημα με n κόμβους όπου οι ακμές του προστίθενται ανεξάρτητα η καθεμία με μία σταθερή πιθανότητα p. Το μοντέλο αυτό ονομάζεται τυχαίο γράφημα Erdős–Rényi. Πως μοιάζει ένα τέτοιο γράφημα ανάλογα με το πόσο μεγάλη είναι η πιθανότητα p; Πόσους κόμβους περιέχει η μεγαλύτερη συνεκτική συνιστώσα ενός τέτοιου γραφήματος; Προκύπτει ότι αν η πιθανότητα p είναι αρκετά μικρή τότε όλες οι συνιστώσες του γραφήματος είναι μικρές υπό την έννοια ότι καμιά τους δεν περιέχει περισσότερους από logn κόμβους. Από την άλλη αν η πιθανότητα είναι αρκετά μεγάλη τότε υπάρχει μια μεγάλη συνεκτική συνιστώσα που περιέχει ένα μεγάλο μέρος των κόμβων. Πως μοιάζει ένα γράφημα Erdős–Rényi όταν γνωρίζουμε εκ των προτέρων ότι συμβαίνει ένα σπάνιο γεγονός; Αυτή η απάντηση μπορεί να δοθεί για σταθερό p και για n που τείνει στο άπειρο. Για να μελετήσουμε τα παραπάνω θα χρειαστεί να κατασκευάσουμε τον κατάλληλο χώρο, μέσα στον οποίο θα μπορούμε να εφαρμόσουμε την αρχή των μεγάλων αποκλίσεων. Η εργασία αυτή έχει σκοπό να παρουσιάσει το τυχαίο γράφημα Erdős–Rényi και ύστερα υπό το πρίσμα της αρχής των μεγάλων αποκλίσεων να απαντήσει και να αποδείξει τα παραπάνω ερωτήματα. Ως εφαρμογή του βασικού θεωρήματος των μεγάλων αποκλίσεων θα δούμε πως μοιάζει το τυχαίο γράφημα Erdős–Rényi όταν γνωρίζουμε τον αριθμό των τριγώνων του γραφήματος.","Let G(n,p) be a random graph with n vertices where its edges are added independently the one with the other with a stable probability p. This model is known as the Erdős–Rényi random graph. How does such a graph looks like depending on how big the probability p is? How many vertices contains the biggest connected component of such a graph? It happens that when the probability p is small enough then all the components of this graph are small, which means that none of them contains more than logn vertices. From the other side, if the probability is high enough then there is one large connected component which contains a great part of the vertices. How such a graph looks like when we know beforehand that a rare event happens? This answer can be given for stable p and for n that goes to infinity. In order to be able to study the above, we need to construct the appropriate space in which we will be able to apply the large deviation principle. This work aims to present the Erdős–Rényi random graph and after with the help of the large deviations principle to answer and prove the above questions. As an application of the basic theorem of large deviations we will see how the Erdős–Rényi random graph looks like when we know the number of the triangles of the graph."]},{"key":"dc:title","label":"Title","values":["Η αρχή των μεγάλων αποκλίσεων για το τυχαίο γράφημα Erdős–Rényi"]}]}],"canonical_facts":{"dc:creator":["Κονδυλάτος Σπυρίδων","Kondylatos Spyridon"],"dc:date":["2018"],"dc:description":["Έστω G(n,p) να είναι το τυχαίο γράφημα με n κόμβους όπου οι ακμές του προστίθενται ανεξάρτητα η καθεμία με μία σταθερή πιθανότητα p. Το μοντέλο αυτό ονομάζεται τυχαίο γράφημα Erdős–Rényi. Πως μοιάζει ένα τέτοιο γράφημα ανάλογα με το πόσο μεγάλη είναι η πιθανότητα p; Πόσους κόμβους περιέχει η μεγαλύτερη συνεκτική συνιστώσα ενός τέτοιου γραφήματος; Προκύπτει ότι αν η πιθανότητα p είναι αρκετά μικρή τότε όλες οι συνιστώσες του γραφήματος είναι μικρές υπό την έννοια ότι καμιά τους δεν περιέχει περισσότερους από logn κόμβους. Από την άλλη αν η πιθανότητα είναι αρκετά μεγάλη τότε υπάρχει μια μεγάλη συνεκτική συνιστώσα που περιέχει ένα μεγάλο μέρος των κόμβων. Πως μοιάζει ένα γράφημα Erdős–Rényi όταν γνωρίζουμε εκ των προτέρων ότι συμβαίνει ένα σπάνιο γεγονός; Αυτή η απάντηση μπορεί να δοθεί για σταθερό p και για n που τείνει στο άπειρο. Για να μελετήσουμε τα παραπάνω θα χρειαστεί να κατασκευάσουμε τον κατάλληλο χώρο, μέσα στον οποίο θα μπορούμε να εφαρμόσουμε την αρχή των μεγάλων αποκλίσεων. Η εργασία αυτή έχει σκοπό να παρουσιάσει το τυχαίο γράφημα Erdős–Rényi και ύστερα υπό το πρίσμα της αρχής των μεγάλων αποκλίσεων να απαντήσει και να αποδείξει τα παραπάνω ερωτήματα. Ως εφαρμογή του βασικού θεωρήματος των μεγάλων αποκλίσεων θα δούμε πως μοιάζει το τυχαίο γράφημα Erdős–Rényi όταν γνωρίζουμε τον αριθμό των τριγώνων του γραφήματος.","Let G(n,p) be a random graph with n vertices where its edges are added independently the one with the other with a stable probability p. This model is known as the Erdős–Rényi random graph. How does such a graph looks like depending on how big the probability p is? How many vertices contains the biggest connected component of such a graph? It happens that when the probability p is small enough then all the components of this graph are small, which means that none of them contains more than logn vertices. From the other side, if the probability is high enough then there is one large connected component which contains a great part of the vertices. How such a graph looks like when we know beforehand that a rare event happens? This answer can be given for stable p and for n that goes to infinity. In order to be able to study the above, we need to construct the appropriate space in which we will be able to apply the large deviation principle. This work aims to present the Erdős–Rényi random graph and after with the help of the large deviations principle to answer and prove the above questions. As an application of the basic theorem of large deviations we will see how the Erdős–Rényi random graph looks like when we know the number of the triangles of the graph."],"dc:identifier":["uoadl:2800850","https://pergamos.lib.uoa.gr/uoa/dl/object/2800850"],"dc:language":["Ελληνικά","Greek"],"dc:subject":["Θετικές Επιστήμες","Science"],"dc:title":["Η αρχή των μεγάλων αποκλίσεων για το τυχαίο γράφημα Erdős–Rényi"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:32:09Z"}