در ریاضیات، گراف تصادفی اصطلاحی کلی است که به احتمال پراکندگی روی گراف ها اطلاق می گردد و نقطه برخورد تئوری گراف و تئوری احتمالات است. از جنبه ریاضیات، گراف تصادفی برای پاسخ به پرسش هایی در مورد خواص گراف ها بکار گرفته می شود، اما برنامه های کاربردی آن در تمام حوزه هایی که در آن شبکه های پیچیده نیاز به مدل سازی دارند وجود دارد. در مبحث ریاضی، گراف تصادفی تقریباً به مدل گراف تصادفی Erdös - Renyi منحصر است. در زمینه های دیگر، هر مدل گراف دیگر ممکن است به یک گراف تصادفی نسبت داده شود. [ ۱]
فرض کنید n نقطه در فضا و همچنین سکه ای اریب با احتمال رو آمدن p در اختیار داریم. با پرتاب سکه و با احتمال رو آمدن متناظر p، دو نقطه انتخابی دلخواه را به هم وصل می کنیم یعنی یالی از این رئوس می گذرانیم. قابل ذکر است که رئوس شماره دار هستند. برای روشن شدن مطلب یک حالت خاص n و p را بررسی می کنیم. [ ۲] مثال: در حالت n = ۳ و فرض p = 4 5 ، 1 125 احتمال دارد سه نقطه ایزوله تشکیل شود؛ یعنی هیچ یالی بین سه راس تشکیل نشود. در این حالت هر یک از سه یال ممکن، یعنی همان اضلاع مثلث با احتمال 1 5 ظاهر نمی شوند. از این رو احتمال اینکه هیچ یک از اضلاع در گراف حضور نداشته باشند، برابر با 1 5 ∗ 1 5 ∗ 1 5 = 1 125 می باشد. با احتمال ( 3 1 ) ∗ 4 5 ∗ 1 5 ∗ 1 5 = 12 125 ، تنها یک یال ایجاد می شود؛ یعنی سه گراف که در آن رأس ۱ یا ۲ یا ۳ تنها بوده و یال، بین دو رأس دیگر ایجاد می شود؛ به این معنی که در شماره رأس ها تفاوت دارند. همچنین به همین صورت با احتمال ( 3 2 ) ∗ 4 5 ∗ 4 5 ∗ 1 5 = 48 125 دو یال ایجاد می گردد و در آخر با احتمال 4 5 ∗ 4 5 ∗ 4 5 = 64 125 یک گراف کامل از مرتبه ۳ خواهیم داشت.
یک گراف تصادفی از یکسری رئوس منفرد به علاوه یال های متوالی تصادفی میان آن ها بدست می آید. هدف مطالعه در این زمینه این است که تعیین کنیم احتمال رخ دادن خاصیت بخصوصی از گراف در چه مرحله ای است. چندین نوع گراف از گراف تصادفی وجود دارد اما متداول ترین نوع گراف، گرافی است که توسط Edgar Gilbert ارائه گردیده و مثالش در بالا ذکر شده است. [ ۱]
در این مدل رئوس گراف ثابت بوده و تصادفی بودن گراف به واسطه وجود پارامتر P بوده که در بازه تغییر می کند. در این مدل یال ها به صورت تصادفی و مستقل از هم انتخاب می شوند. [ ۲] احتمال به دست آوردن گراف تصادفی بخصوصی با m یال، با توجه به اینکه N = ( n 2 ) ، P m ( 1 − P ) N − m می باشد. [ ۱]
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلففرض کنید n نقطه در فضا و همچنین سکه ای اریب با احتمال رو آمدن p در اختیار داریم. با پرتاب سکه و با احتمال رو آمدن متناظر p، دو نقطه انتخابی دلخواه را به هم وصل می کنیم یعنی یالی از این رئوس می گذرانیم. قابل ذکر است که رئوس شماره دار هستند. برای روشن شدن مطلب یک حالت خاص n و p را بررسی می کنیم. [ ۲] مثال: در حالت n = ۳ و فرض p = 4 5 ، 1 125 احتمال دارد سه نقطه ایزوله تشکیل شود؛ یعنی هیچ یالی بین سه راس تشکیل نشود. در این حالت هر یک از سه یال ممکن، یعنی همان اضلاع مثلث با احتمال 1 5 ظاهر نمی شوند. از این رو احتمال اینکه هیچ یک از اضلاع در گراف حضور نداشته باشند، برابر با 1 5 ∗ 1 5 ∗ 1 5 = 1 125 می باشد. با احتمال ( 3 1 ) ∗ 4 5 ∗ 1 5 ∗ 1 5 = 12 125 ، تنها یک یال ایجاد می شود؛ یعنی سه گراف که در آن رأس ۱ یا ۲ یا ۳ تنها بوده و یال، بین دو رأس دیگر ایجاد می شود؛ به این معنی که در شماره رأس ها تفاوت دارند. همچنین به همین صورت با احتمال ( 3 2 ) ∗ 4 5 ∗ 4 5 ∗ 1 5 = 48 125 دو یال ایجاد می گردد و در آخر با احتمال 4 5 ∗ 4 5 ∗ 4 5 = 64 125 یک گراف کامل از مرتبه ۳ خواهیم داشت.
یک گراف تصادفی از یکسری رئوس منفرد به علاوه یال های متوالی تصادفی میان آن ها بدست می آید. هدف مطالعه در این زمینه این است که تعیین کنیم احتمال رخ دادن خاصیت بخصوصی از گراف در چه مرحله ای است. چندین نوع گراف از گراف تصادفی وجود دارد اما متداول ترین نوع گراف، گرافی است که توسط Edgar Gilbert ارائه گردیده و مثالش در بالا ذکر شده است. [ ۱]
در این مدل رئوس گراف ثابت بوده و تصادفی بودن گراف به واسطه وجود پارامتر P بوده که در بازه تغییر می کند. در این مدل یال ها به صورت تصادفی و مستقل از هم انتخاب می شوند. [ ۲] احتمال به دست آوردن گراف تصادفی بخصوصی با m یال، با توجه به اینکه N = ( n 2 ) ، P m ( 1 − P ) N − m می باشد. [ ۱]
wiki: گراف تصادفی