القفص (نظرية الرسم البياني)

📅 آخر تحديث: ٢٨ يوليو ٢٠٢٦
✍️ نُشر في: ٢٨ يوليو ٢٠٢٦
📷 يحتوي على 5 صور
الموسوعة الحرة
قفص Tutte ( 3,8 ) .

في مجال نظرية الرسم البياني الرياضي ، القفص هو رسم بياني منتظم يحتوي على أقل عدد ممكن من الرؤوس بالنسبة لمحيطه .

يُعرَّف الرسم البياني ( r , g ) رسميًا بأنه رسم بياني لكل رأس فيه r من الجيران بالضبط، ويكون طول أقصر دورة فيه g بالضبط . أما القفص ( r , g ) فهو رسم بياني ( r , g ) يحتوي على أقل عدد ممكن من الرؤوس بين جميع الرسوم البيانية ( r , g ) . ويُطلق على القفص (3, g ) غالبًا اسم القفص g .

من المعروف أن هناك رسمًا بيانيًا ( r , g ) لأي تركيبة من r ≥ 2 و g ≥ 3. ويترتب على ذلك أن جميع الأقفاص ( r , g ) موجودة.

إذا وُجد رسم بياني من نوع مور بدرجة r ومحيط g ، فلا بد أن يكون قفصًا. علاوة على ذلك، فإن حدود أحجام رسوم مور البيانية تُعمم على الأقفاص: أي قفص بمحيط فردي g يجب أن يكون على الأقل

1+ر∑أنا=0(ز-3)/2(ر-1)أنا{\displaystyle 1+r\sum _{i=0}^{(g-3)/2}(r-1)^{i}}

الرؤوس، وأي قفص ذو محيط زوجي g يجب أن يحتوي على الأقل

2∑أنا=0(ز-2)/2(ر-1)أنا{\displaystyle 2\sum _{i=0}^{(g-2)/2}(r-1)^{i}}

الرؤوس. أي رسم بياني ( r ، g ) يحتوي على هذا العدد من الرؤوس بالضبط هو بحكم التعريف رسم بياني مور، وبالتالي فهو قفص تلقائي.

قد توجد عدة أقفاص لتركيبة معينة من r و g . على سبيل المثال، توجد ثلاثة أقفاص غير متماثلة من النوع (3، 10) ، كل منها يحتوي على 70 رأسًا: قفص بالابان ذو 10 رؤوس ، ومخطط هاريس ، ومخطط هاريس-وونغ . ولكن يوجد قفص واحد فقط من النوع (3، 11) : قفص بالابان ذو 11 رأسًا (يحتوي على 112 رأسًا).

الأقفاص المعروفة

لا يحتوي الرسم البياني المنتظم من الدرجة 1 على دورة، ويكون محيط الرسم البياني المنتظم من الدرجة 2 المتصل مساوياً لعدد رؤوسه، لذا فإن الأقفاص ذات أهمية فقط عندما يكون r ≥ 3. القفص ( r ، 3) هو رسم بياني كامل K r + 1 على r  +  1 رأس، والقفص ( r ، 4) هو رسم بياني ثنائي الأجزاء كامل K r ، r على 2 r رأس.

ومن بين الأقفاص البارزة ما يلي:

عدد الرؤوس في الأقفاص المعروفة ( r ، g )، لقيم r > 2 و g > 2، بخلاف المستويات الإسقاطية والمضلعات المعممة، هي:

ز
ر
3456789101112
346101424305870112126
45819266780728
561030421702730
671240623127812
78145090

التقارب

بالنسبة للقيم الكبيرة لـ g ، فإن حد مور يعني أن عدد الرؤوس n يجب أن ينمو على الأقل بشكل أُسّي كدالة لـ g . وبصورة مكافئة، يمكن أن تكون g متناسبة على الأكثر مع لوغاريتم n . بتعبير أدق،

ز≤2سجلر-1⁡ن+يا(1).{\displaystyle g\leq 2\log _{r-1}n+O(1).}

يُعتقد أن هذا الحدّ دقيق أو شبه دقيق ( بولوباس وسزيميريدي ، 2002 ) . أفضل الحدود الدنيا المعروفة لـ g هي أيضًا لوغاريتمية، ولكن بمعامل ثابت أصغر (مما يعني أن n ينمو أُسّيًا ولكن بمعدل أعلى من حدّ مور). وبالتحديد، فإن بناء رسوم رامانوجان البيانية ، كما حددها لوبوتزكي وفيليبس وسارناك (1988)، يُحقق هذا الحدّ .

ز≥43سجلر-1⁡ن+يا(1).{\displaystyle g\geq {\frac {4}{3}}\log _{r-1}n+O(1).}

وقد تم تحسين هذا الحد قليلاً بواسطة لازيبنيك، أوستيمينكو وولدار (1995) .

من غير المرجح أن تكون هذه الرسوم البيانية نفسها أقفاصًا، لكن وجودها يعطي حدًا أعلى لعدد الرؤوس اللازمة في القفص.

مراجع