گراف تصادفی
در ریاضیات، گراف تصادفی اصطلاحی کلی است که به احتمال پراکندگی روی گرافها اطلاق میگردد و نقطه برخورد تئوری گراف و تئوری احتمالات است. از جنبه ریاضیات، گراف تصادفی برای پاسخ به پرسشهایی در مورد خواص گرافها بکار گرفته میشود، اما برنامههای کاربردی آن در تمام حوزههایی که در آن شبکههای پیچیده نیاز به مدلسازی دارند وجود دارد. در مبحث ریاضی، گراف تصادفی تقریباً به مدل گراف تصادفی Erdös-Renyi منحصر است. در زمینههای دیگر، هر مدل گراف دیگر ممکن است به یک گراف تصادفی نسبت داده شود.
مفهوم گراف تصادفی
فرض کنید n نقطه در فضا و همچنین سکهای اریب با احتمال رو آمدن p در اختیار داریم. با پرتاب سکه و با احتمال رو آمدن متناظر p، دو نقطه انتخابی دلخواه را به هم وصل میکنیم یعنی یالی از این رئوس میگذرانیم. قابل ذکر است که رئوس شمارهدار هستند. برای روشن شدن مطلب یک حالت خاص n و p را بررسی میکنیم.
مثال: در حالت n = ۳ و فرض
مدلهایی از گراف تصادفی
یک گراف تصادفی از یکسری رئوس منفرد به علاوه یالهای متوالی تصادفی میان آنها بدست میآید. هدف مطالعه در این زمینه این است که تعیین کنیم احتمال رخ دادن خاصیت بخصوصی از گراف در چه مرحلهای است. چندین نوع گراف از گراف تصادفی وجود دارد اما متداولترین نوع گراف، گرافی است که توسط Edgar Gilbert ارائه گردیده و مثالش در بالا ذکر شدهاست.
گراف تصادفی G(n,P)
در این مدل رئوس گراف ثابت بوده و تصادفی بودن گراف به واسطه وجود پارامتر P بوده که در بازه [۰٬۱] تغییر میکند. در این مدل یالها به صورت تصادفی و مستقل از هم انتخاب میشوند. احتمال به دست آوردن گراف تصادفی بخصوصی با m یال، با توجه به اینکه
گراف تصادفی G(n,M)
مدل G(n,M) نشاندهنده گراف تصادفی با n رأس و M یال ثابت است و تصادفی بودن گراف به واسطه جایگشت یالها میباشد که در بین رئوس شماره دار تغییر میکند. اگر N ≥ M ≥ ۰ و
گراف تصادفی نامحدود
اگر بینهایت رأس داشته باشیم و هر یال بهطور مستقل با احتمال p که در بازه [۰٬۱] تغییر میکند، به وجود بیاید، گرافی خواهیم داشت که گراف تصادفی نامحدود نامیده میشود؛ مگر در مواردی جزئی که P صفر یا یک است.
منابع
- ↑ ، ویکیپدیا انگلیسیen:Random graph
- ↑ «، نشریه دانشجویی» (PDF). بایگانیشده از اصلی (PDF) در ۱۵ اوت ۲۰۱۶. دریافتشده در ۲۸ ژوئن ۲۰۱۶.
- ویکیپدیا انگلیسی، Random graph
- نشریه دانشجویی آمار (ندا)، مفهوم گراف تصادفی و مدلهایی از آن