پروفر کد

در ریاضیات ترکیبیاتی، کد پروفر ( دنباله پروفر یا اعداد پروفر ) برای یک درخت برچسب‌دار، یک دنباله از اعداد است که به این درخت نسبت داده می‌شود. طول این دنباله برای یک درخت n راسی دقیقا n-2 است، و می‌توان آن را با یک الگوریتم تکرار شونده ساده تولید کرد. پروفر کد برای اولین بار به وسیله هینز پروفر برای اثبات فرمول کیلی استفاده شد.
الگوریتم تبدیل یک درخت به کد پروفر
یک درخت با کد پروفر 4،4،4و5 (از راست به چپ)
کد پروفر برای یک درخت می‌تواند با حذف کردن پی در پی راس‌های یک درخت تا وقتی که تنها ۲ راس مانده، به دست آید. یعنی اگر T یک درخت برچسب‌دار با راس‌های
باشد، در مرحله iام کوچک‌ترین برگ درخت را حذف کرده و شماره همسایه آن را به عنوان عنصر iام کد قرار می‌دهیم.
کد پروفر برای یک درخت برچسب‌دار یکتاست و دقیقا n-2 عنصر دارد.
یک مثال
فرض کنید الگوریتم بالا بر روی درخت سمت چپ اجرا شود. در ابتدا راس شماره 1 برگی است که کوچک‌ترین شماره را بین برگ‌ها دارد، از این رو این برگ اول از همه پاک می‌شود و عدد 4(شماره راس متصل به 1) در کد پروفر قرار می‌گیرد. سپس راس‌های 2 و 3 حذف می‌شوند، پس 4 دو بار دیگر نیز به کد اضافه خواهد شد. در این حال راس 4 کوچک‌ترین برگ در درخت است و در نتیجه ما 4 را نیز حذف می‌کنیم و شماره 5 را به دنباله اضافه می‌کنیم. تنها 2 راس باقی‌مانده پس فرایند متوقف خواهد شد.
الگوریتم تبدیل یک کد پروفر به درخت
فرض کنید یک کد پروفر باشد.
درخت حاصل n+2 راس، با شماره‌های 1 تا n+2 خواهد داشت. درجه را برای هر راس یکی بیشتر از تعداد بارهای ظاهر شدن آن در دنباله پروفر قرار دهید. برای مثال به صورت شبه کد:
Convert-Prüfer-to-Tree(a)
1 n ← lengtha
2 T ← a graph with n + 2 isolated nodes, numbered 1 to n + 2
3 degree ← an array of integers
4 for each node i in T
5 do degreei ← 1
6 for each value i in a
7 do degreei ← degreei + 1
سپس برای هر راس در ، کوچک‌ترین راس j با درجه 1 را پیدا کنید و با اضافه کردن یال (j, ) به درخت از درجه این دو راس یک واحد کم کنید. به صورت شبه کد:
8 for each value i in a
9 for each node j in T
10 if degreej = 1
11 then Insert edgei, j into T
12 degreei ← degreei - 1
13 degreej ← degreej - 1
14 break
در انتهای حلقه دو راس با درجه یک باقی می‌ماند(فرض کنید v و u ) در پایان یال (v,u) را به درخت اضافه کنید.
15 u ← v ← 0
16 for each node i in T
17 if degreei = 1
18 then if u = 0
19 then u ← i
20 else v ← i
21 break
22 Insert edgeu, v into T
23 degreeu ← degreeu - 1
24 degreev ← degreev - 1
25 return T
فرمول کیلی
واضح است که پروفر کد یک درخت برچسب‌دار، یک دنباله به طول n-2 یکتا است. اما این که برای هر دنباله به طول n-2 از اعداد 1 تا n یک درخت برچسب‌دار یکتا وجود دارد آنقدر واضح نیست.
نتیجه مستقیم این عبارت این است که کد پروفر، یک تابع یک به یک و پوشا بین مجموعه درخت‌های n راسی برچسب‌دار و مجموعه دنباله‌هایی به طول n-2 از اعداد 1 تا n ارائه می‌دهد. مجموعه دوم عضو دارد، پس وجود این تابع یک به یک و پوشا فرمول کیلی را اثبات می‌کند: تعداد درخت‌های n راسی برچسب‌دار برابر با است.
کاربردهای دیگر
فرمول کیلی می‌تواند تعمیم داده شود تا ادعای زیر را ثابت کند:
تعداد درخت‌های پوشا با درجه‌های در یک گراف کامل n راسی( ) برابر است با
زیرا در پروفر کد این درخت‌ها عدد i دقیقا بار آمده‌است.
فرمول کیلی می‌تواند به این صورت نیز تعمیم داده شود:
یک درخت برچسب‌دار در حقیقت یک درخت پوشا در گراف کامل برچسب‌دار متناظر است. همچنین با گذاشتن محدودیت‌هایی بر روی کدهای پروفر شمرده شده،به روشی مشابه می‌توان تعداد درخت‌های پوشای یک گراف دو بخشی کامل را نیز به دست آورد. اگر گراف کامل 2 بخشی G از دو بخش به ترتیب و راسی تشکیل شده باشد( )، تعداد درخت‌های پوشای برچسب‌دار G برابر است با
تولید دنباله‌های تصادفی پروفر با احتمال مساوی و تبدیل آن‌ها به درخت برچسب دار یکی از راه‌های ساده تولید درخت‌های برچسب دار تصادفی با احتمال مساوی است.