هذه المقالة يتيمة. ساعد بإضافة وصلة إليها في مقالة متعلقة بها

متتالية بغوفر

من أرابيكا، الموسوعة الحرة

هذه هي النسخة الحالية من هذه الصفحة، وقام بتعديلها عبود السكاف (نقاش | مساهمات) في 08:38، 25 مارس 2023 (بوت: إصلاح التحويلات). العنوان الحالي (URL) هو وصلة دائمة لهذه النسخة.

(فرق) → نسخة أقدم | نسخة حالية (فرق) | نسخة أحدث ← (فرق)
اذهب إلى التنقل اذهب إلى البحث

في نظرية المخططات يُقرن رمز بغوفر (بالألمانية: Prüfer-Code) أو متتالية بغوفر إلى شجرة مسماة أحادياً (بانفراد). يبلغ طول شجرة مكونة من س رؤوس س-1 ، ويمكن توليده بخوارزمية بسيطة. تم استخدم هذه المتتالية لأول مرة في عام 1918م من قبل الألماني هاينز بروفر لإثبات صيغة كايلي.[1]

خوارزمية

تحويل شجرة لمتتابعة بغوفر

يُمكن تحويل شجرة بغوفر مسماة إلى متتابعة بإزالة الرؤوس بتتابع من الشجرة حتى يتبقى رأسان.على سبيل المثال، لتكن ش شجرة مسماة تحوي على {1،2،...س} رؤوس، في كل خطوة خ تُزال الأوراق ذات أصغر قيمة اسمية، وتحدد القيمة خ لمتتالية بغوفر بمسمى والدة الورقة. كل متتابعة لبغوفر تعتبر فريدة وطولها يصل لـ س-1.

مثال

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

شجرة مسماة بمتتالية بغوفر {4,4,4,5}.

مراجع

  1. ^ Prüfer, H. (1918). "Neuer Beweis eines Satzes über Permutationen". Arch. Math. Phys. ج. 27: 742–744.