From Wikipedia, the free encyclopedia
در ریاضیات، گراف تصادفی اصطلاحی کلی است که به احتمال پراکندگی روی گرافها اطلاق میگردد و نقطه برخورد تئوری گراف و تئوری احتمالات است. از جنبه ریاضیات، گراف تصادفی برای پاسخ به پرسشهایی در مورد خواص گرافها بکار گرفته میشود، اما برنامههای کاربردی آن در تمام حوزههایی که در آن شبکههای پیچیده نیاز به مدلسازی دارند وجود دارد. در مبحث ریاضی، گراف تصادفی تقریباً به مدل گراف تصادفی Erdös-Renyi منحصر است. در زمینههای دیگر، هر مدل گراف دیگر ممکن است به یک گراف تصادفی نسبت داده شود.[1]
فرض کنید n نقطه در فضا و همچنین سکهای اریب با احتمال رو آمدن p در اختیار داریم. با پرتاب سکه و با احتمال رو آمدن متناظر p، دو نقطه انتخابی دلخواه را به هم وصل میکنیم یعنی یالی از این رئوس میگذرانیم. قابل ذکر است که رئوس شمارهدار هستند. برای روشن شدن مطلب یک حالت خاص n و p را بررسی میکنیم.[2]
مثال: در حالت n = ۳ و فرض
، احتمال دارد سه نقطه ایزوله تشکیل شود؛ یعنی هیچ یالی بین سه راس تشکیل نشود. در این حالت هر یک از سه یال ممکن، یعنی همان اضلاع مثلث با احتمال ظاهر نمیشوند. از این رو احتمال اینکه هیچیک از اضلاع در گراف حضور نداشته باشند، برابر با میباشد. با احتمال ، تنها یک یال ایجاد میشود؛ یعنی سه گراف که در آن رأس ۱ یا ۲ یا ۳ تنها بوده و یال، بین دو رأس دیگر ایجاد میشود؛ به این معنی که در شماره رأسها تفاوت دارند. همچنین به همین صورت با احتمال دو یال ایجاد میگردد و در آخر با احتمال یک گراف کامل از مرتبه ۳ خواهیم داشت.
یک گراف تصادفی از یکسری رئوس منفرد به علاوه یالهای متوالی تصادفی میان آنها بدست میآید. هدف مطالعه در این زمینه این است که تعیین کنیم احتمال رخ دادن خاصیت بخصوصی از گراف در چه مرحلهای است. چندین نوع گراف از گراف تصادفی وجود دارد اما متداولترین نوع گراف، گرافی است که توسط Edgar Gilbert ارائه گردیده و مثالش در بالا ذکر شدهاست.[1]
در این مدل رئوس گراف ثابت بوده و تصادفی بودن گراف به واسطه وجود پارامتر P بوده که در بازه [۰٬۱] تغییر میکند. در این مدل یالها به صورت تصادفی و مستقل از هم انتخاب میشوند.[2] احتمال به دست آوردن گراف تصادفی بخصوصی با m یال، با توجه به اینکه ، میباشد.[1]
مدل G(n,M) نشاندهنده گراف تصادفی با n رأس و M یال ثابت است و تصادفی بودن گراف به واسطه جایگشت یالها میباشد که در بین رئوس شماره دار تغییر میکند.[2] اگر N ≥ M ≥ ۰ و باشد، گراف تصادفی G(n,M) دارای عضو است و هر عضو با احتمال در مدل حضور دارد. این مدل را میتوان به عنوان یک عضو از مجموعه گرافهای G(n,M)، با M یال مشخص، در نظر گرفت طوریکه ابتدا با n رأس و بدون یال شروع شده و در هر مرحله یال جدیدی اضافه کند تا به N یال برسد.[1] اجتماع تمام این گرافها به صورت نشان داده میشود.
اگر بینهایت رأس داشته باشیم و هر یال بهطور مستقل با احتمال p که در بازه [۰٬۱] تغییر میکند، به وجود بیاید، گرافی خواهیم داشت که گراف تصادفی نامحدود نامیده میشود؛ مگر در مواردی جزئی که P صفر یا یک است.[1]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.