گراف تصادفی

فرض کنید n نقطه در فضا و همچنین سکه‌ای اریب با احتمال رو آمدن p در اختیار داریم. با پرتاب سکه و با احتمال رو آمدن متناظر p، دو نقطه انتخابی دلخواه را به هم وصل می‌کنیم یعنی یالی از این رئوس می‌گذرانیم. قابل ذکر است که رئوس شماره‌دار هستند. برای روشن شدن مطلب یک حالت خاص n و p را بررسی می‌کنیم.[2]
مثال: در حالت n = ۳ و فرض ${\displaystyle p={\frac {4}{5}}}$، ${\displaystyle {\frac {1}{125}}}$ احتمال دارد سه نقطه ایزوله تشکیل شود؛ یعنی هیچ یالی بین سه راس تشکیل نشود. در این حالت هر یک از سه یال ممکن، یعنی همان اضلاع مثلث با احتمال ${\displaystyle {\frac {1}{5}}}$ ظاهر نمی‌شوند. از این رو احتمال اینکه هیچ‌یک از اضلاع در گراف حضور نداشته باشند، برابر با ${\displaystyle {\frac {1}{5}}*{\frac {1}{5}}*{\frac {1}{5}}={\frac {1}{125}}}$ می‌باشد. با احتمال ${\displaystyle {\binom {3}{1}}*{\frac {4}{5}}*{\frac {1}{5}}*{\frac {1}{5}}={\frac {12}{125}}}$، تنها یک یال ایجاد می‌شود؛ یعنی سه گراف که در آن رأس ۱ یا ۲ یا ۳ تنها بوده و یال، بین دو رأس دیگر ایجاد می‌شود؛ به این معنی که در شماره رأس‌ها تفاوت دارند. همچنین به همین صورت با احتمال ${\displaystyle {\binom {3}{2}}*{\frac {4}{5}}*{\frac {4}{5}}*{\frac {1}{5}}={\frac {48}{125}}}$ دو یال ایجاد می‌گردد و در آخر با احتمال${\displaystyle {\frac {4}{5}}*{\frac {4}{5}}*{\frac {4}{5}}={\frac {64}{125}}}$ یک گراف کامل از مرتبه ۳ خواهیم داشت.

یک گراف تصادفی از یکسری رئوس منفرد به علاوه یال‌های متوالی تصادفی میان آن‌ها بدست می‌آید. هدف مطالعه در این زمینه این است که تعیین کنیم احتمال رخ دادن خاصیت بخصوصی از گراف در چه مرحله‌ای است. چندین نوع گراف از گراف تصادفی وجود دارد اما متداول‌ترین نوع گراف، گرافی است که توسط Edgar Gilbert ارائه گردیده و مثالش در بالا ذکر شده‌است.[1]

در این مدل رئوس گراف ثابت بوده و تصادفی بودن گراف به واسطه وجود پارامتر P بوده که در بازه [۰٬۱] تغییر می‌کند. در این مدل یال‌ها به صورت تصادفی و مستقل از هم انتخاب می‌شوند.[2] احتمال به دست آوردن گراف تصادفی بخصوصی با m یال، با توجه به اینکه ${\displaystyle N={\binom {n}{2}}}$، ${\displaystyle P^{m}(1-P)^{N-m}}$ می‌باشد.[1]

مدل G(n,M) نشان‌دهنده گراف تصادفی با n رأس و M یال ثابت است و تصادفی بودن گراف به واسطه جایگشت یال‌ها می‌باشد که در بین رئوس شماره دار تغییر می‌کند.[2] اگر N ≥ M ≥ ۰ و ${\displaystyle N={\binom {n}{2}}}$ باشد، گراف تصادفی G(n,M) دارای ${\displaystyle {\binom {N}{M}}}$ عضو است و هر عضو با احتمال ${\displaystyle {\frac {1}{\binom {N}{M}}}}$ در مدل حضور دارد. این مدل را می‌توان به عنوان یک عضو از مجموعه گراف‌های G(n,M)، با M یال مشخص، در نظر گرفت طوری‌که ابتدا با n رأس و بدون یال شروع شده و در هر مرحله یال جدیدی اضافه کند تا به N یال برسد.[1] اجتماع تمام این گراف‌ها به صورت ${\displaystyle \bigcup _{M=0}^{N}G(n,M)}$ نشان داده می‌شود.

اگر بی‌نهایت رأس داشته باشیم و هر یال به‌طور مستقل با احتمال p که در بازه [۰٬۱] تغییر می‌کند، به وجود بیاید، گرافی خواهیم داشت که گراف تصادفی نامحدود نامیده می‌شود؛ مگر در مواردی جزئی که P صفر یا یک است.[1]

• ویکی‌پدیا انگلیسی، Random graph
• نشریه دانشجویی آمار (ندا)، مفهوم گراف تصادفی و مدل‌هایی از آن