National and Kapodistrian University of Athens
Προσομοίωση τυχαίων γραφημάτων με περιορισμούς στην ακολουθία βαθμών
Abstract
dc:descriptionΈνα σημαντικό πρόβλημα στη θεωρία των γράφων είναι η δημιουργία γράφων με μια δοθείσα κατανομή βαθμών,το οποίο είναι ισοδύναμο με τη δημιουργία τυχαίων γράφων,οι οποίοι έχουν ένα συγκεκριμένο αριθμό ακμών υπό τον περιορισμό των βαθμών.Τα κίνητρα για τη μελέτη είναι: α) να μπορούμε να έχουμε ετερογενείς ακμές,το οποίο δεν είναι δυνατό στο κλασικό μοντέλο των Erdos-Renyi,καθώς αυτό επιτρέπει καλύτερη προσαρμογή σε πραγματικές εφαρμογές και β) να σχεδιάσουμε αποτελεσματικά ένα τυχαίο γράφο με αυτούς τους περιορισμούς.Προηγούμενοι αλγόριθμοι συχνά βρίσκονται σε αδιέξοδο ή σε ατέρμονο βρόχο 'η παράγουν πολλαπλές ακμές.Αυτό επιτυγχάνεται με τον αλγόριθμο των Blitzstein & Diaconis,ο οποίος βασίζεται στην ιδέα της ακολουθιακής δειγματοληψίας σπουδαιότητας.Για αυτό χρησιμοποιείται μια επέκταση του χαρακτηρισμού Erdos-Gallai και μια κατάλληλα επιλεγμένη σειρά επιλογής ακμών.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Κατωγιάννη Ιωάννα
- Katogianni Ioanna
Subjects
dc:subject × 2Rights
- Language dc:language
- Ελληνικά, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:2895465