مدل Erdős–Rényi (انگلیسی : Erdős–Rényi Model) - G(n, M)، در ریاضیات (Mathematics)
انواع گراف های تصادفی (Random Graphs) را در آموزش زیر شرح دادیم :
مدل Erdős–Rényi (انگلیسی : Erdős–Rényi Model) - G(n, M) :
این مدل که به نام دو ریاضیدان بزرگ، پل اردیش و آلفرد رنی، نامگذاری شده، اولین و یکی از مشهورترین انواع گراف تصادفی است. در این مدل، یک مجموعه با
\[ n \]رأس ثابت داریم و از بین تمام گراف هایی که دقیقا
\[ M \]یال دارند، یک گراف را به صورت کاملا تصادفی و با احتمال یکسان انتخاب می کنیم. به عبارت دیگر، ابتدا تمام حالات ممکن برای انتخاب
\[ M \]یال از بین تمام
\[ \binom{n}{2} \]یال ممکن را در نظر می گیریم و سپس یکی از این حالات را به تصادف برمی گزینیم. این مدل با مدل
\[ G(n, p) \]ارتباط نزدیکی دارد و برای
\[ n \]های بزرگ، انتظار می رود گراف
\[ G(n, p) \]با
\[ p = \frac{M}{\binom{n}{2}} \]تقریبا
\[ M \]یال داشته باشد. مطالعه این مدل منجر به کشف پدیده های مهمی مانند ظهور ناگهانی مؤلفه غول آسا (Giant Component) در آستانه خاصی از
\[ M \]شد.
نویسنده علیرضا گلمکانی
شماره کلید 5555
گزینه ها 
نظرات 0 0 0