Random regular graph
एक यादृच्छिक आर-नियमित ग्राफ एक चयनित ग्राफ है, जो शीर्षों पर सभी आर-नियमित ग्राफों के प्रायिकता स्थान को दर्शाता है, जहां और सम है। इसलिए यह एक विशेष प्रकार का यादृच्छिक ग्राफ है, लेकिन नियमितता प्रतिबंध उन गुणों को महत्वपूर्ण रूप से बदल देता है जो धारण करेंगे, क्योंकि अधिकांश ग्राफ नियमित नहीं होते हैं। यादृच्छिक नियमित आलेखों के गुण अधिक सामान्य यादृच्छिक आलेखों के साथ, यह साबित करना संभव है कि यादृच्छिक-नियमित आलेखों के कुछ गुण लगभग निश्चित रूप से स्पर्शोन्मुख रूप से होते हैं। विशेष रूप से, बड़े आकार का एक यादृच्छिक आर-नियमित ग्राफ लगभग निश्चित रूप से आर-जुड़ा हुआ है। दूसरे शब्दों में, हालांकि-संपर्क के साथ कम नियमित ग्राफ मौजूद हैं, इस तरह के ग्राफ को चुनने की संभावना बढ़ने पर 0 हो जाती है। यदि एक सकारात्मक स्थिरांक है, और सबसे कम पूर्णांक संतोषजनक है, तो लक्षणरहित रूप से लगभग निश्चित रूप से, एक यादृच्छिक आर-नियमित ग्राफ का व्यास अधिकतम डी होता है। आर-नियमित ग्राफ के व्यास पर एक (अधिक जटिल) निचली सीमा भी होती है, ताकि लगभग सभी आर-नियमित ग्राफ (समान आकार के) का व्यास लगभग समान हो। लघु चक्रों की संख्या का वितरण भी ज्ञात हैः निश्चित के लिए, लंबाई के चक्रों की संख्या मान लीजिए। फिर यादृच्छिक नियमित ग्राफ के लिए एल्गोरिदम के साधन के साथ एसिम्प्टोटिक रूप से स्वतंत्र पॉइसन यादृच्छिक चर हैं r-नियमित ग्राफ के यादृच्छिक चयन को कुशलता से और निष्पक्ष तरीके से लागू करना गैर-तुच्छ है, क्योंकि अधिकांश ग्राफ नियमित नहीं होते हैं। पेयरिंग मॉडल (विन्यास मॉडल भी) एक ऐसी विधि है जो एन. आर. अंक लेती है, और उन्हें प्रत्येक में आर अंकों के साथ एन बाल्टियों में विभाजित करती है। एन. आर. अंकों का यादृच्छिक मिलान करने से, और फिर प्रत्येक बाल्टी में आर अंकों को एक ही शीर्ष में संकुचित करने से, एक आर-नियमित ग्राफ या बहुलेखन प्राप्त होता है। यदि इस वस्तु के कई किनारे या लूप नहीं हैं (अर्थात। यह एक ग्राफ है), तो यह आवश्यक परिणाम है। यदि नहीं, तो पुनः आरंभ करने की आवश्यकता है। इस विधि का एक परिष्करण ब्रेंडन मैके और निकोलस वोर्माल्ड द्वारा विकसित किया गया था। संदर्भ यादृच्छिक ग्राफ नियमित ग्राफ