Prüfer Code

 

An encoding which provides a bijection between the  labeled trees on  nodes and strings of  integers chosen from an alphabet of the numbers 1 to . A labeled tree can be converted to a Prüfer code using LabeledTreeToCode[g] in the Wolfram Language package Combinatorica` , and a code can be converted to a labeled tree using CodeToLabeledTree[code].

Prüfer's bijection is based on the fact that every tree has at least two nodes of degree 1 (i.e., tree leaves. Therefore, the node  which is incident to the lowest labeled leaf is uniquely determined, and  is then taken as the first symbol in the code. This lowest labeled leaf is then deleted and the procedure is repeated until a single edge is left, giving a total of  integers between 1 and  (Skiena 1990). This is demonstrated in the labeled tree shown above. The sequence of leaf deletions is 4, 6, 2, 1, 7, and 3, corresponding to incident nodes 1, 2, 1, 3, 3, and 5, respectively.

---

REFERENCES

Prüfer, H. "Neuer Beweis eines Satzes über Permutationen." Arch. Math. Phys. 27, 742-744, 1918.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم شؤون المعارف يطلق دورة (صفات الشيعة) لعدد من ملاكات العتبة العباسية المقدسة

الهيأة العليا لإحياء التراث تبحث تعزيز التعاون المشترك مع مركز الإمام الباقر (عليه السلام) في إيران

جامعة الكفيل تكرِّم طلبتها المتميزين من ذوي الاحتياجات الخاصة

فريق طبي في مستشفى الكفيل يجري عملية ناجحة لطفل يعاني من تشوّه ولاديّ بالنخاع الشوكي

المزيد

الآخبار الصحية

خصوصا مع تقدم السن.. 6 سلوكيات يومية قد تدمّر صحتك

فاكهة خضراء.. علاج طبيعي فعّال للإمساك واضطرابات الهضم

روسيا تبدأ أولى التجارب السريرية للقاح واعد ضد السرطان

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

المزيد

الآخبار التكنلوجية

رصد نوع نادر من القطط في تايلاند للمرة الأولى منذ عقود

روسيا تخطط لإقامة محطة نووية في القمر خلال العقد المقبل

كيف قاد إيلون ماسك حملة "غروك" لاختراق عرش الذكاء الاصطناعي

ألتمان: الذكاء الاصطناعي سيتجاوز البشر في 2026 !

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength