Random regular graph
રેન્ડમ આર-રેગ્યુલર ગ્રાફ એ પસંદ કરેલો ગ્રાફ છે, જે શિરોબિંદુઓ પરના તમામ આર-રેગ્યુલર ગ્રાફની સંભાવના જગ્યા સૂચવે છે, જ્યાં અને સમ છે. તેથી તે એક ચોક્કસ પ્રકારનો રેન્ડમ ગ્રાફ છે, પરંતુ નિયમિતતા પ્રતિબંધ એ ગુણધર્મોને નોંધપાત્ર રીતે બદલે છે જે જાળવી રાખશે, કારણ કે મોટાભાગના આલેખ નિયમિત નથી. રેન્ડમ રેગ્યુલર ગ્રાફના ગુણધર્મો વધુ સામાન્ય રેન્ડમ ગ્રાફની જેમ, તે સાબિત કરવું શક્ય છે કે રેન્ડમ-રેગ્યુલર ગ્રાફના ચોક્કસ ગુણધર્મો લગભગ ચોક્કસપણે એસિમ્પ્ટોટિક રીતે ધરાવે છે. ખાસ કરીને, મોટા કદનો રેન્ડમ આર-રેગ્યુલર ગ્રાફ એસિમ્પ્ટોટિક રીતે લગભગ ચોક્કસપણે આર-જોડાયેલ છે. બીજા શબ્દોમાં કહીએ તો, જોડાણ સાથે નિયમિત આલેખ અસ્તિત્વમાં હોવા કરતાં ઓછા હોવા છતાં, આવા આલેખને પસંદ કરવાની સંભાવના જેમ જેમ વધે છે તેમ તેમ 0 થાય છે. જો હકારાત્મક અચળાંક હોય અને ઓછામાં ઓછો પૂર્ણાંક સંતોષકારક હોય તો, એસિમ્પ્ટોટિક રીતે લગભગ ચોક્કસપણે, રેન્ડમ આર-રેગ્યુલર ગ્રાફનો વ્યાસ મહત્તમ ડી હોય છે. આર-રેગ્યુલર ગ્રાફના વ્યાસ પર (વધુ જટિલ) નીચલી બાઉન્ડ પણ હોય છે, જેથી લગભગ તમામ આર-રેગ્યુલર ગ્રાફ (સમાન કદના) નો વ્યાસ લગભગ સમાન હોય છે. ટૂંકા ચક્રોની સંખ્યાનું વિતરણ પણ જાણીતું છેઃ નિશ્ચિત માટે, ચાલો લંબાઈના ચક્રોની સંખ્યા સુધી હોઈએ. પછી એ એસિમ્પ્ટોટિકલી ઇન્ડિપેન્ડન્ટ પોઈસન રેન્ડમ વેરિયેબલ્સ છે જેનો અર્થ છે રેન્ડમ રેગ્યુલર ગ્રાફ્સ માટે અલ્ગોરિધમ્સ r-રેગ્યુલર ગ્રાફ્સની રેન્ડમ પસંદગીને અસરકારક રીતે અને નિષ્પક્ષ રીતે અમલમાં મૂકવી તે બિન-તુચ્છ છે, કારણ કે મોટાભાગના ગ્રાફ નિયમિત નથી. પેરિંગ મોડેલ (રૂપરેખાંકન મોડેલ પણ) એ એક પદ્ધતિ છે જે એન. આર. પોઈન્ટ લે છે, અને તેમને દરેકમાં આર પોઈન્ટ સાથે એન બકેટમાં વિભાજિત કરે છે. એન. આર. બિંદુઓનું રેન્ડમ મેચિંગ લેવાથી, અને પછી દરેક ડોલમાં આર બિંદુઓને એક જ શિરોબિંદુમાં સંકુચિત કરવાથી, આર-રેગ્યુલર ગ્રાફ અથવા મલ્ટિગ્રાફ મળે છે. જો આ ઑબ્જેક્ટમાં કોઈ બહુવિધ ધાર અથવા લૂપ્સ ન હોય (એટલે કે. તે એક આલેખ છે), પછી તે જરૂરી પરિણામ છે. જો નહિં, તો પુનઃપ્રારંભ કરવાની જરૂર છે. આ પદ્ધતિનું શુદ્ધિકરણ બ્રેન્ડન મેકકે અને નિકોલસ વોર્માલ્ડ દ્વારા વિકસાવવામાં આવ્યું હતું. સંદર્ભો રેન્ડમ આલેખ નિયમિત આલેખ