Back to search

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 × 2

Rights

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

Identifiers

dc:identifier.*
Identifier
uoadl:2895465

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

Κατωγιάννη Ιωάννα; Katogianni Ioanna. Προσομοίωση τυχαίων γραφημάτων με περιορισμούς στην ακολουθία βαθμών. 2020. https://pergamos.lib.uoa.gr/uoa/dl/object/2895465