پروفر کد

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در ریاضیات ترکیبیاتی، کدِ پروفر (دنبالهٔ پروفر یا اعداد پروفر) برای یک درخت برچسب‌دار، یک دنباله از اعداد است که به این درخت نسبت داده می‌شود. طول این دنباله برای یک درخت 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) برابر است با
\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)!}.
زیرا در پروفر کد این درخت‌ها عدد 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}

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

منابع[ویرایش]

  1. Prüfer, H. (1918). "Neuer Beweis eines Satzes über Permutationen". Arch. Math. Phys. 27: 742–744. 
  2. Jens Gottlieb, Bryant A. Julstrom, Günther R. Raidl, and Franz Rothlauf. (2001). "Prüfer numbers: A poor representation of spanning trees for evolutionary search". Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001): 343–350. 

پیوند به بیرون[ویرایش]