رسم بياني منتظم عشوائي

الرسم البياني العشوائي المنتظم من الرتبة r هو رسم بياني يتم اختياره من${\displaystyle {\mathcal {G}}_{n,r}}$، والتي تشير إلى فضاء الاحتمالات لجميع الرسوم البيانية المنتظمة من الدرجة r على${\displaystyle n}$الرؤوس، حيث${\displaystyle 3\leq r<n}$و${\displaystyle nr}$هو زوجي. ^{[ 1 ]} لذلك فهو نوع خاص من الرسوم البيانية العشوائية ، لكن قيد الانتظام يغير بشكل كبير الخصائص التي ستتحقق، لأن معظم الرسوم البيانية ليست منتظمة.

كما هو الحال مع الرسوم البيانية العشوائية الأكثر عمومية ، من الممكن إثبات أن بعض خصائص العشوائية${\displaystyle m}$– تتحقق الرسوم البيانية المنتظمة بشكل شبه مؤكد عند التقارب . على وجه الخصوص، بالنسبة لـ${\displaystyle r\geq 3}$^{[ 2 ]} بعبارة أخرى، على الرغم من أن الرسم البياني العشوائي المنتظم من الدرجة r ذو الحجم الكبير يكون متصلاً من الدرجة r بشكل شبه مؤكد تقريبًا .${\displaystyle r}$– رسوم بيانية منتظمة ذات اتصال أقل من${\displaystyle r}$إذا وُجد مثل هذا الرسم البياني، فإن احتمال اختياره يؤول إلى الصفر عندما${\displaystyle n}$يزداد.

لو${\displaystyle \epsilon >0}$ثابت موجب، و${\displaystyle d}$هو أصغر عدد صحيح يحقق

${\displaystyle (r-1)^{d-1}\geq (2+\epsilon )rn\ln n}$

عندئذٍ، وبشكل شبه مؤكد تقريبًا، يكون قطر الرسم البياني المنتظم العشوائي من الرتبة r على الأكثر d . وهناك أيضًا حد أدنى (أكثر تعقيدًا) لقطر الرسوم البيانية المنتظمة من الرتبة r ، بحيث يكون لجميع الرسوم البيانية المنتظمة من الرتبة r تقريبًا (من نفس الحجم) نفس القطر تقريبًا. ^{[ 3 ]}

كما أن توزيع عدد الدورات القصيرة معروف أيضًا: بالنسبة لـ ثابت${\displaystyle m\geq 3}$، يترك${\displaystyle Y_{3},Y_{4},...Y_{m}}$ليكن عدد الدورات التي يصل طولها إلى${\displaystyle m}$ثم${\displaystyle Y_{i}}$هي متغيرات عشوائية مستقلة تقاربياً من نوع بواسون ذات متوسطات ^{[ 4 ]}

${\displaystyle \lambda _{i}={\frac {(r-1)^{i}}{2i}}}$

يُعدّ تنفيذ الاختيار العشوائي للرسوم البيانية المنتظمة من الرتبة r بكفاءة وبطريقة غير متحيزة أمرًا معقدًا، نظرًا لأن معظم الرسوم البيانية ليست منتظمة. نموذج الاقتران (أو نموذج التكوين ) هو طريقة تأخذ nr نقطة، وتقسمها إلى n مجموعة تحتوي كل منها على r نقطة. من خلال إجراء مطابقة عشوائية بين النقاط nr ، ثم دمج النقاط r في كل مجموعة لتكوين رأس واحد، ينتج رسم بياني منتظم من الرتبة r أو رسم بياني متعدد . إذا لم يكن لهذا الكائن حواف أو حلقات متعددة (أي أنه رسم بياني)، فهو النتيجة المطلوبة. وإلا، يلزم إعادة التشغيل. ^{[ 5 ]}

وقد قام بريندان مكاي ونيكولاس وورمالد بتطوير نسخة محسنة من هذه الطريقة . ^{[ 6 ]}