متتالية بغوفر
المحتويات
على سبيل التعريف، في نظرية المخططات يُقرن رمز بغوفر أو متتالية بغوفر إلى شجرة مسماة أحادياً (بانفراد). يبلغ طول شجرة مكونة من س رؤوس س-1 ، ويمكن توليده بخوارزمية بسيطة. تم استعمل هذه المتتالية لأول مرة في عام 1918م من قبل الألماني هاينز بروفر لإثبات صيغة كايلي. ونتناول فيما يلي مزيدًا من التفاصيل.
خوارزمية
مثال
من جهة ثانية، افرض أن الخوارزمية أعلاه طُبقت على الشجرة الظاهرة على الشكل أدناه، فالبداية الرأس بمسمى 1 سيكون ذو أقل قيمة، لذا ستتم إزالته، وتحديد قيمة 4 في متتالية بغوفر، بعدها بنفس العملية ستتم إزالة الرؤوس 2 و 3 ووضع 4 مرتين، أصبح الرأس 4 الآن ورقة بأصغر مسمى، لذا سيزال وتحدد القيمة 5 للمتتابعة. سيتبقى الآن رأسان، وهنا تتنهي الخوارزمية بنتيجة {4,4,4,5}.
تحويل شجرة لمتتابعة بغوفر
كذلك، يُمكن تحويل شجرة بغوفر مسماة إلى متتابعة بإزالة الرؤوس بتتابع من الشجرة حتى يتبقى رأسان.مثلًا، لتكن ش شجرة مسماة تحوي على {1،2،...س} رؤوس، في كل خطوة خ تُزال الأوراق ذات أصغر قيمة اسمية، وتحدد القيمة خ لمتتالية بغوفر بمسمى والدة الورقة. كل متتابعة لبغوفر تعتبر فريدة وطولها يصل لـ س-1.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟