Random regular graph
ایک بے ترتیب r-ریگولر گراف ایک ایسا گراف ہے جس سے منتخب کیا جاتا ہے، جو عمودی حصوں پر تمام r-ریگولر گرافوں کے امکانات کی جگہ کی نشاندہی کرتا ہے، جہاں اور یکساں ہے۔ اس لیے یہ ایک خاص قسم کا بے ترتیب گراف ہے، لیکن باقاعدگی کی پابندی نمایاں طور پر ان خصوصیات کو بدل دیتی ہے جو برقرار رہیں گی، کیونکہ زیادہ تر گراف باقاعدہ نہیں ہوتے ہیں۔ بے ترتیب باقاعدہ گرافوں کی خصوصیات جیسا کہ زیادہ عام بے ترتیب گرافوں کے ساتھ، یہ ثابت کرنا ممکن ہے کہ بے ترتیب-باقاعدہ گرافوں کی کچھ خصوصیات تقریبا یقینی طور پر غیر علامتی طور پر ہوتی ہیں۔ خاص طور پر، بڑے سائز کا بے ترتیب آر-ریگولر گراف تقریبا یقینی طور پر آر سے جڑا ہوا ہے۔ دوسرے لفظوں میں، اگرچہ-رابطے کے ساتھ باقاعدہ گراف موجود سے کم ہیں، اس طرح کے گراف کو منتخب کرنے کا امکان بڑھتے ہی 0 ہو جاتا ہے۔ اگر ایک مثبت مستقل ہے، اور سب سے کم عدد تسلی بخش ہے تو، غیر علامتی طور پر تقریبا یقینی طور پر، ایک بے ترتیب r-ریگولر گراف کا قطر زیادہ سے زیادہ d ہوتا ہے۔ r-ریگولر گراف کے قطر پر ایک (زیادہ پیچیدہ) نچلا پابند بھی ہوتا ہے، تاکہ تقریبا تمام r-ریگولر گراف (ایک ہی سائز کے) کا قطر تقریبا ایک جیسا ہو۔ مختصر چکروں کی تعداد کی تقسیم بھی معلوم ہے: فکسڈ کے لیے، لمبائی کے چکروں کی تعداد ہونے دیں۔ پھر بے ترتیب باقاعدہ گرافوں کے لیے الگورتھم کے ذرائع کے ساتھ غیر علامتی طور پر آزاد پوسن بے ترتیب متغیرات ہیں۔ r-ریگولر گرافوں کے بے ترتیب انتخاب کو مؤثر طریقے سے اور غیر جانبدار طریقے سے نافذ کرنا غیر معمولی ہے، کیونکہ زیادہ تر گراف باقاعدہ نہیں ہوتے ہیں۔ جوڑی ماڈل (کنفیگریشن ماڈل بھی) ایک ایسا طریقہ ہے جو این آر پوائنٹس لیتا ہے، اور ان میں سے ہر ایک میں آر پوائنٹس کے ساتھ انہیں این بالٹیوں میں تقسیم کرتا ہے۔ این آر پوائنٹس کا بے ترتیب ملاپ لیتے ہوئے، اور پھر ہر بالٹی میں آر پوائنٹس کو ایک ہی سرے میں سکڑتے ہوئے، ایک آر-ریگولر گراف یا ملٹی گراف حاصل ہوتا ہے۔ اگر اس شے کے متعدد کنارے یا لوپس نہیں ہیں (یعنی۔ یہ ایک گراف ہے)، پھر یہ مطلوبہ نتیجہ ہے۔ اگر نہیں، تو دوبارہ شروع کرنے کی ضرورت ہے۔ اس طریقہ کار کی ایک اصلاح برینڈن میککے اور نکولس ورمالڈ نے تیار کی تھی۔ حوالہ جات بے ترتیب گراف باقاعدہ گراف