Prüfer sequence
مشترکہ ریاضی میں، لیبل والے درخت کی پرفر ترتیب (جسے پرفر کوڈ یا پرفر نمبر بھی کہا جاتا ہے) درخت سے وابستہ ایک منفرد ترتیب ہے۔ n عمودی پر کسی درخت کی ترتیب کی لمبائی n−2 ہوتی ہے، اور اسے ایک سادہ تکراری الگورتھم کے ذریعے تیار کیا جا سکتا ہے۔ 1918 میں کیلی کے فارمولے کو ثابت کرنے کے لیے پہلی بار ہینز پرفر نے پرفر کے سلسلے کا استعمال کیا تھا۔ کسی درخت کو پرفر ترتیب میں تبدیل کرنے کے لیے الگورتھم کوئی بھی درخت سے عمودی طور پر ہٹاتے ہوئے لیبل شدہ درخت کی پرفر ترتیب پیدا کر سکتا ہے جب تک کہ صرف دو عمودی باقی نہ رہیں۔ خاص طور پر، ایک لیبل والے ٹری T پر غور کریں جس کے عمودی حصے {1,2,., n} ہوں۔ مرحلہ I پر، سب سے چھوٹے لیبل والے پتی کو ہٹا دیں اور پرفر ترتیب کے ith عنصر کو اس پتی کے پڑوسی کا لیبل مقرر کریں۔ لیبل والے درخت کی پرفر ترتیب منفرد ہوتی ہے اور اس کی لمبائی n−2 ہوتی ہے۔ کوڈنگ اور ڈیکوڈنگ دونوں کو انٹیجر ریڈکس چھانٹ اور متوازی میں کم کیا جا سکتا ہے۔ مثال دائیں طرف دکھائے گئے درخت پر چلنے والے مندرجہ بالا الگورتھم پر غور کریں۔ ابتدائی طور پر، ورٹیکس 1 سب سے چھوٹے لیبل والا پتی ہے، اس لیے اسے پہلے ہٹا دیا جاتا ہے اور 4 کو پرفر ترتیب میں رکھا جاتا ہے۔ عمودی 2 اور 3 کو آگے ہٹا دیا جاتا ہے، لہذا 4 کو دو بار مزید شامل کیا جاتا ہے۔ ورٹیکس 4 اب ایک پتی ہے اور اس پر سب سے چھوٹا لیبل ہے، اس لیے اسے ہٹا دیا جاتا ہے اور ہم 5 کو ترتیب میں شامل کرتے ہیں۔ ہمارے پاس صرف دو عمودی حصے رہ گئے ہیں، اس لیے ہم رک جاتے ہیں۔ درخت کی ترتیب {4,4,4، 5} ہے۔ پروفر ترتیب کو درخت میں تبدیل کرنے کے لیے الگورتھم فرض کریں کہ {a [1]، a [2]،.، a [n]} ایک پروفر ترتیب ہو: درخت میں n + 2 نوڈس ہوں گے، جن کی تعداد 1 سے n + 2 تک ہوگی۔ ہر نوڈ کے لیے اس کی ڈگری سیٹ کریں کہ یہ ترتیب جمع 1 میں کتنی بار ظاہر ہوتی ہے۔ مثال کے طور پر، چھدم کوڈ میں: کنورٹ-پرفر-ٹو-ٹری (a) 1 n کی لمبائی [a] 2 T کی لمبائی n + 2 الگ تھلگ نوڈس کے ساتھ ایک گراف، جس کی تعداد 1 سے n + 2 3 ڈگری ہے۔ ہر نوڈ کے لیے انٹیجرز کی ایک صف i کو T میں 5 ڈگری [i] کے لیے ہر ویلیو کے لیے i کو 7 ڈگری [i] کے لیے [i] کے لیے [i] کے لیے اگلا نمبر، ترتیب میں ہر نمبر کے لیے a [i]، پہلا (سب سے کم نمبر والا) نوڈ تلاش کریں، j، 1 کے برابر ڈگری کے ساتھ، ٹری میں ایج (j، a [i]) شامل کریں، اور j اور a [i] کی ڈگری کم کریں۔ سڈو کوڈ میں: 8 ہر ویلیو کے لیے i میں ہر نوڈ کے لیے 9 کریں T میں ہر نوڈ کے لیے 10 کریں اگر ڈگری [j] = 1 تو 11 ایج [i, j] کو T 12 ڈگری [i] میں ڈالیں [i] → ڈگری [i]-1 13 ڈگری [j] → ڈگری [j]-1 14 بریک اس لوپ کے آخر میں ڈگری 1 والے دو نوڈس باقی رہیں گے (انہیں u، v کہیں)۔ آخر میں، درخت کے کنارے (یو، وی) کو شامل کریں۔ ہر نوڈ i کے لیے T17 میں اگر ڈگری [i] = 1 ہے تو 18 اگر u = 0 ہے تو 19 u → i 20 اور 21 v → i 22 ٹوٹتے ہیں 23 کنارے [u, v] کو T 24 ڈگری [u] میں ڈالیں [u] → ڈگری [u]-1 25 ڈگری [v] → ڈگری [v]-1 26 واپسی T کیلی کا فارمولا n عمودی پر لیبل والے درخت کی پرفر ترتیب لیبل 1 سے n پر لمبائی n−2 کی ایک منفرد ترتیب ہے۔ 1 سے n لیبل پر لمبائی n−2 کی دی گئی ترتیب S کے لیے، ایک منفرد لیبل والا درخت ہے جس کی پرفر ترتیب S ہے۔ فوری نتیجہ یہ ہے کہ پرو کہ n عمودی پر nn−2 لیبل والے درخت ہیں۔ دیگر ایپلی کیشنز کیلی کے فارمولے کو مندرجہ ذیل دعوے کو ثابت کرنے کے لیے مضبوط کیا جا سکتا ہے: ایک مکمل گراف میں ہر سرے کے لیے مخصوص ڈگری کے ساتھ پھیلے ہوئے درختوں کی تعداد کثیر الجہتی گتانک کے برابر ہوتی ہے۔ ثبوت اس بات کا مشاہدہ کرتا ہے کہ پرفر ترتیب میں نمبر بالکل بار ظاہر ہوتا ہے۔ کیلی کے فارمولے کو عام کیا جا سکتا ہے: ایک لیبل شدہ درخت درحقیقت لیبل شدہ مکمل گراف کا ایک پھیلا ہوا درخت ہے۔ شمار شدہ پرفر ترتیبات پر پابندیاں لگا کر، اسی طرح کے طریقے ایک مکمل دو طرفہ گراف کے پھیلے ہوئے درختوں کی تعداد دے سکتے ہیں۔ اگر G ایک پارٹیشن میں عمودی 1 سے n1 اور دوسری پارٹیشن میں عمودی n1 + 1 سے n کے ساتھ مکمل دو طرفہ گراف ہے، تو G کے لیبل والے پھیلے ہوئے درختوں کی تعداد ہے، جہاں n2 = n − n1 ہے۔ یکساں طور پر تقسیم شدہ بے ترتیب پروفر ترتیبات پیدا کرنا اور انہیں متعلقہ درختوں میں تبدیل کرنا یکساں طور پر تقسیم شدہ بے ترتیب لیبل والے درختوں کو پیدا کرنے کا ایک سیدھا سیدھا طریقہ ہے۔ حوالہ جات بیرونی روابط پرفر کوڈ-ریاضی ورلڈ کے عددی امتزاج درختوں سے (گراف تھیوری)