تسلسل الاختبار

في الرياضيات التوافقية ، تُعرف متتالية بروفر (أو رمز بروفر أو أعداد بروفر ) لشجرة مُصنَّفة بأنها متتالية فريدة مرتبطة بتلك الشجرة. يبلغ طول متتالية بروفر لشجرة ذات n رأسًا n − 2 ، ويمكن توليدها باستخدام خوارزمية تكرارية بسيطة. استخدم هاينز بروفر متتاليات بروفر لأول مرة لإثبات صيغة كايلي عام 1918. ^{[ 1 ]}

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

إن تسلسل بروفر لشجرة مصنفة فريد وله طول n − 2 .

يمكن اختزال كل من عملية الترميز وفك الترميز إلى فرز أساس الأعداد الصحيحة ومعالجتها بالتوازي. ^{[ 2 ]}

مثال

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

لتكن [a[1], a[2], ..., a[n]]متتالية بروفر:

ستحتوي الشجرة على n+2عُقد، مرقمة من 11 إلى n+22. لكل عُقدة، حدد درجتها بعدد مرات ظهورها في التسلسل زائد 1. على سبيل المثال، في الشفرة الزائفة:

Convert-Prüfer-to-Tree ( a ) 1 ن ← الطول [ أ ] 2T ← رسم بياني يحتوي على n + 2 عقدة معزولة، مرقمة من 1 إلى n + 2الدرجة الثالثة ← مصفوفة من الأعداد الصحيحة 4 لكل عقدة i في T، قم بما يلي: 5 درجة [ i ] ← 1 ٦ لكل قيمة i في a، قم بما يلي: ٧ درجة [ i ] ← درجة [ i ] + ١

بعد ذلك، لكل رقم في المتتالية a[i]، ابحث عن العقدة الأولى (الأصغر رقمًا)، j، التي درجتها تساوي 1، وأضف الحافة (j, a[i])إلى الشجرة، ثم قلل درجات jو a[i]. في الشفرة الزائفة:

٨ لكل قيمة i في a، نفّذ ما يلي: ٩ لكل عقدة j في T، نفّذ ما يلي: ١٠ إذا كانت درجة [ j ] = ١، فقم بما يلي: ١١ أدخل الحافة [ i , j ] في T ١٢ درجة [ i ] ← درجة [ i ] - ١ 13 درجة [ j ] ← درجة [ j ] - 1استراحة 14 

في نهاية هذه الحلقة، ستبقى عقدتان بدرجة 1 (لنسميهما u) v. وأخيرًا، أضف الحافة (u,v)إلى الشجرة. ^{[ 3 ]}

15 u ← v ← 0 16 لكل عقدة i في T 17 إذا كانت درجة [ i ] = 1، فإن 18 إذا كانت u = 0، فإن 19 u ← i 20 وإلا 21 v ← i 22 توقف 23 أدخل الحافة [ u , v ] في T 24 درجة [ u ] ← درجة [ u ] - 1 25 درجة [ v ] ← درجة [ v ] - 1 26 عودة T

تُعرَّف متتالية بروفر لشجرة مُصنَّفة ذات n رأسًا بأنها متتالية فريدة طولها n − 2 على التصنيفات من 1 إلى n . وبالنسبة لمتتالية معينة S طولها n − 2 على التصنيفات من 1 إلى n ، توجد شجرة مُصنَّفة فريدة تكون متتالية بروفر الخاصة بها هي S.   

والنتيجة المباشرة لذلك هي أن متتاليات بروفر توفر تقابلاً بين مجموعة الأشجار المصنفة على n رأسًا ومجموعة المتتاليات ذات الطول n − 2 على التصنيفات من 1 إلى n . يبلغ حجم المجموعة الأخيرة n ^{n − 2} ، لذا فإن وجود هذا التقابل يثبت صيغة كايلي ، أي أن هناك n ^{n − 2} شجرة مصنفة على n رأسًا.

المصدر: ^{[ 4 ]}

• يمكن تعزيز صيغة كايلي لإثبات الادعاء التالي:

عدد الأشجار الممتدة في الرسم البياني الكامل${\displaystyle K_{n}}$حاصل على درجة علمية${\displaystyle d_{i}}$محدد لكل رأس${\displaystyle i}$يساوي معامل متعدد الحدود

${\displaystyle {\binom {n-2}{d_{1}-1,\,d_{2}-1,\,\dots ,\,d_{n}-1}}={\frac {(n-2)!}{(d_{1}-1)!(d_{2}-1)!\cdots (d_{n}-1)!}}.}$

ويتضح البرهان من خلال ملاحظة أن عدد تسلسل بروفر${\displaystyle i}$يبدو تمامًا${\textstyle d_{i}-1}$مرات.

• يمكن تعميم صيغة كايلي: الشجرة المصنفة هي في الواقع شجرة ممتدة للرسم البياني الكامل المصنف . بوضع قيود على متواليات بروفر المعدودة، يمكن لأساليب مماثلة أن تعطي عدد الأشجار الممتدة لرسم بياني ثنائي الأجزاء كامل . إذا كان G هو الرسم البياني الثنائي الأجزاء الكامل برؤوس من 1 إلى _n1 في أحد الأجزاء ورؤوس _{من n1} + 1 إلى n في الجزء الآخر، فإن عدد الأشجار الممتدة المصنفة لـ G هو${\displaystyle n_{1}^{n_{2}-1}n_{2}^{n_{1}-1}}$، حيث n ₂ = n − n ₁ .
• إن توليد تسلسلات بروفر العشوائية الموزعة بشكل منتظم وتحويلها إلى الأشجار المقابلة هو طريقة مباشرة لتوليد أشجار عشوائية مصنفة موزعة بشكل منتظم.

• كود أفضل – من MathWorld