مدل اردوش رنیی

در    نظریه گراف  مدل اردوش - رنیی  شامل دو مدل نزدیک به هم برای ساختن  گراف تصادفی  است. از آنجا که برای اولین بار دو ریاضیدان  پال اردوش  و    آلفرد رنیی  یکی از این دو مدل را در سال ۱۹۵۹ معرفی کردند، این مدل به نام آن ها نامگذاری شده است. [ ۱]   ادگار گیلبرت مدل دیگر را همزمان و به طور مستقل از اردوش و رنیی معرفی کرد. [ ۲] در مدل اردوش و رنیی، همه گراف ها با تعداد راس و یال ثابت و مشخص احتمال برابر دارند؛ در مدلی که توسط گیلبرت معرفی شد هر یال با احتمال ثابت و مشخصی وجود دارد یا ندارد که این احتمال مستقل از احتمال وجود سایر یال هاست.
دو مدل نزدیک به هم برای گراف تصادفی اردوش - رنیی وجود دارد.
• در مدل  ( G ( n, M یک گراف به صورت یکنواخت و تصادفی از مجموعه ای از گراف ها با n گره و M یال انتخاب می شود. برای مثال در ( 3, 2 ) G هر کدام از سه گراف ممکن با 3 راس و 2 یال با احتمال 1/3 انتخاب می شوند.
• در مدل  ( G ( n, p گراف با وصل کردن گره ها به صورت تصادفی به وجود می آید. هر یال با احتمال p در گراف خواهد بود که این احتمال مستقل از احتمال وجود سایر یال هاست.     تمام گراف ها با n گره و M یال احتمال برابر خواهند داشت این احتمال برابر است با:
رفتار گراف های تصادفی اغلب هنگامی مورد مطالعه قرار می گیرد  که در آن n  تعداد رئوس به بی نهایت میل کند.   p و M  در این مورد می توانند ثابت یا به صورت تابعی از  n باشند.   برای مثال عبارت:
به این معنا است که:
با توجه به تعاریف بالا یک گراف  ( G ( n, p به طور متوسط ( n 2 ) p   یال دارد. توزیع درجه هر راس از نوع توزیع  دوجمله ای  است:[ ۳]
که در آن n تعداد رئوس در گراف است.   از آن جایی که:
این توزیع  برای nهای بزرگ  و np = عدد ثابت  پواسون  است.
در سال 1960 اردوش و رنیی در مقاله ای که منتشر کردند[ ۴]   رفتار ( G ( n, p را به طور دقیق برای مقادیر مختلف  p توصیف کردند.   از جملهٔ این نتایج:
• اگر np < 1 آنگاه یک گراف در  ( G ( n, p با تقریب خوبی هیچ جز همبندی با اندازه بزرگتر از ( ( O ( log ( n نخواهد داشت.
• اگر np = 1  آنگاه یک گراف در ( G ( n, p با تقریب خوبی مولفه همبندی با اندازه ای در حد n2/3    خواهد داشت.
• اگر np → c > 1 که در آن c ثابت است، آنگاه یک گراف در ( G ( n, p با تقریب خوبی  بزرگ ترین مؤلفه ای شامل کسر مثبتی از راس ها خواهد بود. هیچ جزء بیش از ( ( O ( log ( n راس نخواهد داشت.
• اگر p < ( 1 − ε ) ln ⁡ n n {\displaystyle p< {\tfrac { ( 1 - \varepsilon ) \ln n}{n}}} شامل راس جدا ( ایزوله ) و در نتیجه غیرهمبند خواهد بود.
• اگر p > ( 1 + ε ) ln ⁡ n n {\displaystyle p> {\tfrac { ( 1+\varepsilon ) \ln n}{n}}} گراف با تقریب خوبی همبند خواهد بود.