Back to search

National and Kapodistrian University of Athens

Η αρχή των μεγάλων αποκλίσεων για το τυχαίο γράφημα Erdős–Rényi

Abstract

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 όταν γνωρίζουμε τον αριθμό των τριγώνων του γραφήματος.

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Κονδυλάτος Σπυρίδων
  • Kondylatos Spyridon

Subjects

dc:subject × 2

Rights

Language dc:language
Ελληνικά, Greek

Identifiers

dc:identifier.*
Identifier
uoadl:2800850

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
citation

Κονδυλάτος Σπυρίδων; Kondylatos Spyridon. Η αρχή των μεγάλων αποκλίσεων για το τυχαίο γράφημα Erdős–Rényi. 2018. https://pergamos.lib.uoa.gr/uoa/dl/object/2800850