پروفر کد

در ریاضیات ترکیبیاتی، کدِ پروفر (دنبالهٔ پروفر یا اعداد پروفر) برای یک درخت برچسب‌دار، یک دنباله از اعداد است که به این درخت نسبت داده می‌شود. طول این دنباله برای یک درخت n رأسی دقیقاً n-2 است، و می‌توان آن را با یک الگوریتم تکرار شونده ساده تولید کرد. پروفر کد برای اولین بار به وسیلهٔ هینز پروفر برای اثبات فرمول کیلی استفاده شد.

الگوریتم تبدیل یک درخت به کد پروفر

یک درخت با کد پروفر 4،4،4و5 (از راست به چپ)

کد پروفر برای یک درخت می‌تواند با حذف کردن پی در پی رأس‌های یک درخت تا وقتی که تنها ۲ رأس مانده، به دست آید. یعنی اگر T یک درخت برچسب‌دار با رأس های $\{1,2,...,n\}$ باشد، در مرحلهٔ iام کوچک‌ترین برگ درخت را حذف کرده و شمارهٔ همسایهٔ آن را به عنوان عنصر iام کد قرار می‌دهیم.الگو:سخ کد پروفر برای یک درخت برچسب‌دار یکتاست و دقیقاً n-2 عنصر دارد.

یک مثال

فرض کنید الگوریتم بالا بر روی درخت سمت چپ اجرا شود. در ابتدا رأس شمارهٔ 1 برگی است که کوچک‌ترین شماره را بین برگ‌ها دارد، از این رو این برگ اول از همه پاک می‌شود و عدد 4(شمارهٔ رأس متصل به 1) در کد پروفر قرار می‌گیرد. سپس رأس‌های 2 و 3 حذف می‌شوند، پس 4 دو بار دیگر نیز به کد اضافه خواهد شد. در این حال رأس 4 کوچک‌ترین برگ در درخت است و در نتیجه ما 4 را نیز حذف می‌کنیم و شمارهٔ 5 را به دنباله اضافه می‌کنیم. تنها 2 رأس باقی‌مانده پس فرایند متوقف خواهد شد.

الگوریتم تبدیل یک کد پروفر به درخت

فرض کنید $\{a[1],a[2],...,a[n]\}$ یک کد پروفر باشد.الگو:سخ درخت حاصل n+2 رأس، با شماره‌های 1تاn+2 خواهد داشت. درجه را برای هر رأس یکی بیشتر از تعداد بارهای ظاهر شدن آن در دنبالهٔ پروفر قرار دهید. برای مثال به صورت شبه کد:الگو:سخ

  Convert-Prüfer-to-Tree(a)
  1 n ← length[a]
  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 degree[i] ← 1
  6 for each value i in a
  7     do degree[i] ← degree[i] + 1

سپس برای هر رأس در $a[i]$ ، کوچک‌ترین رأس j با درجهٔ 1 را پیدا کنید و با اضافه کردن یال (j,$a[i]$) به درخت از درجهٔ این دو رأس یک واحد کم کنید. به صورت شبه کد:الگو:سخ

  8 for each value i in a
  9     for each node j in T
 10          if degree[j] = 1
 11             then Insert edge[i, j] into T
 12                  degree[i] ← degree[i] - 1
 13                  degree[j] ← degree[j] - 1
 14                  break

در انتهای حلقه دو رأس با درجهٔ یک باقی می‌ماند(فرض کنیدvوu) در پایان یال (v,u) را به درخت اضافه کنید.

 15 u ← v ← 0
 16 for each node i in T
 17     if degree[i] = 1
 18         then if u = 0
 19             then u ← i
 20             else v ← i
 21                  break
 22 Insert edge[u, v] into T
 23 degree[u] ← degree[u] - 1
 24 degree[v] ← degree[v] - 1
 25 return T

فرمول کلی

واضح است که پروفر کد یک درخت برچسب‌دار، یک دنباله به طول n-2 یکتا است. اما این که برای هر دنباله به طول n-2 از اعداد 1 تا n یک درخت برچسب‌دار یکتا وجود دارد آنقدر واضح نیست.الگو:سخ نتیجهٔ مستقیم این عبارت این است که کد پروفر، یک تابع یک به یک و پوشا بین مجموعهٔ درخت‌های n رأسی برچسب‌دار و مجموعهٔ دنباله‌هایی به طول n-2 از اعداد 1 تا n ارائه می‌دهد. مجموعهٔ دوم $n^{n-2}$ عضو دارد، پس وجود این تابع یک به یک و پوشا فرمول کیلی را اثبات می‌کند: تعداد درخت‌های n رأسی برچسب‌دار برابر با $n^{n-2}$ است.

کاربردهای دیگر

• فرمول کیلی می‌تواند تعمیم داده شود تا ادعای زیر را ثابت کند:

تعداد درخت‌های پوشا با درجه‌های $d_1,d_2,...,d_n$ در یک گراف کامل n رأسی($K_n$) برابر است با

$(\genfrac{}{}{0ex}{}{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)!}.$

زیرا در پروفر کد این درخت‌ها عدد i دقیقاً $d_i$ بار آمده‌است.

• فرمول کیلی می‌تواند به این صورت نیز تعمیم داده شود:

یک درخت برچسب‌دار در حقیقت یک درخت پوشا در گراف کامل برچسب‌دار متناظر است. همچنین با گذاشتن محدودیت‌هایی بر روی کدهای پروفر شمرده شده،به روشی مشابه می‌توان تعداد درخت‌های پوشای یک گراف دو بخشی کامل را نیز به دست آورد. اگر گراف کامل 2 بخشی G از دو بخش به ترتیب $n_2$و$n_1$ رأسی تشکیل شده باشد($n=n_1+n_2$)، تعداد درخت‌های پوشای برچسب‌دار G برابر است با $n_1^{n_2-1}{n}_2^{n_1-1}$

• تولید دنباله‌های تصادفی پروفر با احتمال مساوی و تبدیل آن‌ها به درخت برچسب دار یکی از راه‌های سادهٔ تولید درخت‌های برچسب دار تصادفی با احتمال مساوی است.

پیوند به بیرون

• Prüfer code – from MathWorld