نمایش مبدأ برای پروفر کد

در ریاضیات [[ترکیبیات|ترکیبیاتی]]، '''کدِ پروفر''' ('''دنبالهٔ پروفر''' یا '''اعداد پروفر''') برای یک [[درخت_(نظریه_گراف)|درخت برچسب‌دار]]، یک دنباله از اعداد است که به این درخت نسبت داده می‌شود. طول این دنباله برای یک [[درخت_(نظریه_گراف)|درخت]] n رأسی دقیقاً n-2 است، و می‌توان آن را با یک [[الگوریتم]] تکرار شونده ساده تولید کرد. پروفر کد برای اولین بار به وسیلهٔ هینز پروفر برای اثبات [[فرمول کیلی]] استفاده شد.<ref>{{cite journal | author=Prüfer, H. | title=Neuer Beweis eines Satzes über Permutationen | journal=Arch. Math. Phys. | year=1918 | volume=27 | pages=742–744}}</ref>
== الگوریتم تبدیل یک درخت به کد پروفر ==
[[پرونده:Tree graph.svg|150px|بندانگشتی|یک درخت با کد پروفر 4،4،4و5 (از راست به چپ)]]
کد پروفر برای یک درخت می‌تواند با حذف کردن پی در پی رأس‌های یک درخت تا وقتی که تنها ۲ رأس مانده، به دست آید. یعنی اگر T یک درخت برچسب‌دار با رأس های
<math>\{1,2,... ,n\}</math> باشد، در مرحلهٔ iام کوچک‌ترین برگ درخت را حذف کرده و شمارهٔ همسایهٔ آن را به عنوان عنصر iام کد قرار می‌دهیم.{{سخ}}
کد پروفر برای یک درخت برچسب‌دار یکتاست و دقیقاً n-2 عنصر دارد.
=== یک مثال ===
فرض کنید الگوریتم بالا بر روی درخت سمت چپ اجرا شود. در ابتدا رأس شمارهٔ 1 برگی است که کوچک‌ترین شماره را بین برگ‌ها دارد، از این رو این برگ اول از همه پاک می‌شود و عدد 4(شمارهٔ رأس متصل به 1) در کد پروفر قرار می‌گیرد. سپس رأس‌های 2 و 3 حذف می‌شوند، پس 4 دو بار دیگر نیز به کد اضافه خواهد شد. در این حال رأس 4 کوچک‌ترین برگ در درخت است و در نتیجه ما 4 را نیز حذف می‌کنیم و شمارهٔ 5 را به دنباله اضافه می‌کنیم. تنها 2 رأس باقی‌مانده پس فرایند متوقف خواهد شد.

== الگوریتم تبدیل یک کد پروفر به درخت ==
فرض کنید <code><math>\{a[1], a[2], ..., a[n]\}</math></code> یک کد پروفر باشد.{{سخ}}
درخت حاصل <code>n+2</code> رأس، با شماره‌های <code>1</code>تا<code>n+2</code> خواهد داشت. درجه را برای هر رأس یکی بیشتر از تعداد بارهای ظاهر شدن آن در دنبالهٔ پروفر قرار دهید. برای مثال به صورت شبه کد:{{سخ}}
<syntaxhighlight lang="pascal">
  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
</syntaxhighlight>
سپس برای هر رأس در <code><math>a[i]</math></code> ، کوچک‌ترین رأس j با درجهٔ 1 را پیدا کنید و با اضافه کردن یال <code>(j,<math>a[i]</math>)</code> به درخت از درجهٔ این دو رأس یک واحد کم کنید. به صورت شبه کد:{{سخ}}
<syntaxhighlight lang="pascal">
  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
</syntaxhighlight>
در انتهای حلقه دو رأس با درجهٔ یک باقی می‌ماند(فرض کنید<code>v</code>و<code>u</code>) در پایان یال <code>(v,u)</code> را به درخت اضافه کنید.<ref>{{cite journal | author=Jens Gottlieb, Bryant A. Julstrom, Günther R. Raidl, and Franz Rothlauf. | title=Prüfer numbers:   A poor representation of spanning trees for evolutionary search | journal=Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001) | year=2001 | pages=343–350 | url=http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf | access-date=۲۰ مه ۲۰۱۴ | archive-url=https://web.archive.org/web/20060926171652/http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf | archive-date=۲۶ سپتامبر ۲۰۰۶ | dead-url=yes }}</ref>
<syntaxhighlight lang="pascal">
 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
</syntaxhighlight>

== فرمول کلی ==
واضح است که پروفر کد یک درخت برچسب‌دار، یک دنباله به طول <code>n-2</code> یکتا است. اما این که '''برای هر دنباله به طول <code>n-2</code> از اعداد 1 تا n یک درخت برچسب‌دار یکتا وجود دارد''' آنقدر واضح نیست.{{سخ}}
نتیجهٔ مستقیم این عبارت این است که کد پروفر، یک [[تابع_دوسویی|تابع یک به یک و پوشا]] بین مجموعهٔ درخت‌های n رأسی برچسب‌دار و مجموعهٔ دنباله‌هایی به طول n-2 از اعداد 1 تا n ارائه می‌دهد. مجموعهٔ دوم <math>n^{n-2}</math> عضو دارد، پس وجود این تابع یک به یک و پوشا فرمول کیلی را اثبات می‌کند: تعداد درخت‌های n رأسی برچسب‌دار برابر با <math>n^{n-2}</math> است.

== کاربردهای دیگر ==
* فرمول کیلی می‌تواند تعمیم داده شود تا ادعای زیر را ثابت کند:
:تعداد [[درخت_پوشا|درخت‌های پوشا]] با درجه‌های <math>d_1, d_2, ..., d_n</math> در یک [[گراف کامل]] n رأسی(<math>K_n</math>) برابر است با 
::<math>\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)!}.</math>
:زیرا در پروفر کد این درخت‌ها عدد i دقیقاً <math>d_i</math> بار آمده‌است.
* فرمول کیلی می‌تواند به این صورت نیز تعمیم داده شود:
یک درخت برچسب‌دار در حقیقت یک درخت پوشا در گراف کامل برچسب‌دار متناظر است. همچنین با گذاشتن محدودیت‌هایی بر روی کدهای پروفر شمرده شده،به روشی مشابه می‌توان تعداد درخت‌های پوشای یک [[گراف_دوبخشی|گراف دو بخشی کامل]] را نیز به دست آورد. اگر گراف کامل 2 بخشی G از دو بخش به ترتیب <math>n_2</math>و<math>n_1</math> رأسی تشکیل شده باشد(<math>n=n_1+n_2</math>)، تعداد درخت‌های پوشای برچسب‌دار G برابر است با <math>n_{1}^{n_2-1} n_{2}^{n_1-1}</math>
* تولید دنباله‌های تصادفی پروفر با احتمال مساوی و تبدیل آن‌ها به درخت برچسب دار یکی از راه‌های سادهٔ تولید درخت‌های برچسب دار تصادفی  با احتمال مساوی است.

== منابع ==
{{پانویس}}

== پیوند به بیرون ==
* [http://mathworld.wolfram.com/PrueferCode.html Prüfer code] – from MathWorld

[[رده:ترکیبیات شمارشی]]
[[رده:درختان (نظریه گراف)]]
[[رده:ریاضیات]]