ریاضیات

از ویکیپدیا، دانشنامه آزاد

تصادفی R به طور منظم نمودار است نمودار انتخاب شده از، که فضای احتمالی تمام نمودارهای r- منظم را بر روی n رئوس ، که 3 ≤ r < n و nr یکنواخت است ، نشان می دهد. [1] بنابراین این یک نوع خاص از نمودار تصادفی است ، اما محدودیت نظم به طور قابل توجهی ویژگی های نگهداری شده را تغییر می دهد ، زیرا بیشتر نمودارها منظم نیستند.

خصوصیات نمودارهای منظم تصادفی [ ویرایش ]

همانطور که در نمودارهای تصادفی عمومی تر وجود دارد ، می توان ثابت کرد که خصوصیات خاصی از نمودارهای R با قاعده تصادفی تقریباً به طور مجانبی وجود دارد . به ویژه ، برای، یک نمودار R- قاعده ای تصادفی از اندازه بزرگ به طور مجانبی تقریباً به طور قطع r- متصل است . [2] به عبارت دیگر ، اگرچه نمودارهای r منظم با قابلیت اتصال کمتر از r وجود دارد ، اما با انتخاب n ، احتمال انتخاب چنین گرافی به 0 می رسد .

اگر > 0 یک ثابت مثبت است و d کمترین مقدار را دارد

پس از آن، به طور مجانبی مطمئنا، تصادفی R نمودار به طور منظم است قطر در اکثر د . همچنین یک مرز پایین تر (پیچیده تر) روی قطر نمودارهای R- منظم وجود دارد ، به طوری که تقریباً تمام نمودارهای r- منظم (از همان اندازه) تقریباً قطر یکسانی دارند. [3]

توزیع تعداد چرخه های کوتاه نیز شناخته شده است: برای ثابت m ≥ 3 ، اجازه دهید Y 3 ، Y 4 ،… ، Y m تعداد چرخه های طول تا m باشد. سپس Y من متغیرهای تصادفی پواسون به صورت مجانبی و با میانگین [4] هستند

الگوریتم نمودارهای تصادفی منظم [ ویرایش ]

اجرای تصادفی نمودارهای r- منظم به طور کارآمد و به روشی بی طرفانه غیرمعمول نیست ، زیرا بیشتر نمودارها منظم نیستند. مدل جفت شدن (همچنین مدل پیکربندی ) یک روش است که طول می کشد است NR امتیاز، و پارتیشن آنها را به N سطل با R امتیاز در هر یک از آنها. گرفتن یک تطبیق تصادفی از نقاط nr ، و سپس انقباض نقاط r در هر سطل به یک راس واحد ، یک نمودار یا چند نمودار منظم r را بدست می آورد . اگر این جسم چندین لبه یا حلقه نداشته باشد (یعنی نمودار است) ، نتیجه لازم است. در غیر این صورت ، راه اندازی مجدد مورد نیاز است.[5]

اصلاح این روش توسط Brendan McKay و Nicholas Wormald ساخته شد. [6]

منبع 

https://en.wikipedia.org/wiki/Random_regular_graph