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 × 2Rights
- Language dc:language
- Ελληνικά, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:2800850