متتالية بغوفر
في نظرية المخططات يُقرن رمز بغوفر (بالألمانية: Prüfer-Code) أو متتالية بغوفر إلى شجرة مسماة أحادياً (بانفراد). يبلغ طول شجرة مكونة من س رؤوس س-1 ، ويمكن توليده بخوارزمية بسيطة. تم استخدم هذه المتتالية لأول مرة في عام 1918م من قبل الألماني هاينز بروفر لإثبات صيغة كايلي.[1]
خوارزمية
تحويل شجرة لمتتابعة بغوفر
يُمكن تحويل شجرة بغوفر مسماة إلى متتابعة بإزالة الرؤوس بتتابع من الشجرة حتى يتبقى رأسان.على سبيل المثال، لتكن ش شجرة مسماة تحوي على {1،2،...س} رؤوس، في كل خطوة خ تُزال الأوراق ذات أصغر قيمة اسمية، وتحدد القيمة خ لمتتالية بغوفر بمسمى والدة الورقة. كل متتابعة لبغوفر تعتبر فريدة وطولها يصل لـ س-1.
مثال
افرض أن الخوارزمية أعلاه طُبقت على الشجرة الظاهرة على الشكل أدناه، فالبداية الرأس بمسمى 1 سيكون ذو أقل قيمة، لذا ستتم إزالته، وتحديد قيمة 4 في متتالية بغوفر، بعدها بنفس العملية ستتم إزالة الرؤوس 2 و 3 ووضع 4 مرتين، أصبح الرأس 4 الآن ورقة بأصغر مسمى، لذا سيزال وتحدد القيمة 5 للمتتابعة. سيتبقى الآن رأسان، وهنا تتنهي الخوارزمية بنتيجة {4,4,4,5}.
مراجع
- ^ Prüfer, H. (1918). "Neuer Beweis eines Satzes über Permutationen". Arch. Math. Phys. ج. 27: 742–744.
| متتالية بغوفر في المشاريع الشقيقة: | |
