پروفر کد کیست؟ توضیح بده.
در ریاضیات ترکیبیاتی، کدِ پروفر (دنبالهٔ پروفر یا اعداد پروفر) برای یک درخت برچسب‌دار، یک دنباله از اعداد است که به این درخت نسبت داده می‌شود. طول این دنباله برای یک درخت n رأسی دقیقاً n-2 است، و می‌توان آن را با یک الگوریتم تکرار شونده ساده تولید کرد. پروفر کد برای اولین بار به وسیلهٔ هینز پروفر برای اثبات فرمول کیلی استفاده شد.الگوریتم تبدیل یک درخت به کد پروفر.کد پروفر برای یک درخت می‌تواند با حذف کردن پی در پی رأس‌های یک درخت تا وقتی که تنها ۲ رأس مانده، به دست آید. یعنی اگر T یک درخت برچسب‌دار با رأس هایformula_1 باشد، در مرحلهٔ iام کوچک‌ترین برگ درخت را حذف کرده و شمارهٔ همسایهٔ آن را به عنوان عنصر iام کد قرار می‌دهیم.کد پروفر برای یک درخت برچسب‌دار یکتاست و دقیقاً n-2 عنصر دارد.یک مثال.فرض کنید الگوریتم بالا بر روی درخت سمت چپ اجرا شود. در ابتدا رأس شمارهٔ 1 برگی است که کوچک‌ترین شماره را بین برگ‌ها دارد، از این رو این برگ اول از همه پاک می‌شود و عدد 4(شمارهٔ رأس متصل به 1) در کد پروفر قرار می‌گیرد. سپس رأس‌های 2 و 3 حذف می‌شوند، پس 4 دو بار دیگر نیز به کد اضافه خواهد شد. در این حال رأس 4 کوچک‌ترین برگ در درخت است و در نتیجه ما 4 را نیز حذف می‌کنیم و شمارهٔ 5 را به دنباله اضافه می‌کنیم. تنها 2 رأس باقی‌مانده پس فرایند متوقف خواهد شد.الگوریتم تبدیل یک کد پروفر به درخت.فرض کنید codice_1 یک کد پروفر باشد.درخت حاصل codice_2 رأس، با شماره‌های codice_3تاcodice_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سپس برای هر رأس در codice_5 ، کوچک‌ترین رأس j با درجهٔ 1 را پیدا کنید و با اضافه کردن یال codice_6 به درخت از درجهٔ این دو رأس یک واحد کم کنید. به صورت شبه کد: 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در انتهای حلقه دو رأس با درجهٔ یک باقی می‌ماند(فرض کنیدcodice_7وcodice_8) در پایان یال codice_9 را به درخت اضافه کنید. 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فرمول کلی.واضح است که پروفر کد یک درخت برچسب‌دار، یک دنباله به طول codice_10 یکتا است. اما این که برای هر دنباله به طول codice_10 از اعداد 1 تا n یک درخت برچسب‌دار یکتا وجود دارد آنقدر واضح نیست.نتیجهٔ مستقیم این عبارت این است که کد پروفر، یک تابع یک به یک و پوشا بین مجموعهٔ درخت‌های n رأسی برچسب‌دار و مجموعهٔ دنباله‌هایی به طول n-2 از اعداد 1 تا n ارائه می‌دهد. مجموعهٔ دوم formula_5 عضو دارد، پس وجود این تابع یک به یک و پوشا فرمول کیلی را اثبات می‌کند: تعداد درخت‌های n رأسی برچسب‌دار برابر با formula_5 است.کاربردهای دیگر.یک درخت برچسب‌دار در حقیقت یک درخت پوشا در گراف کامل برچسب‌دار متناظر است. همچنین با گذاشتن محدودیت‌هایی بر روی کدهای پروفر شمرده شده،به روشی مشابه می‌توان تعداد درخت‌های پوشای یک گراف دو بخشی کامل را نیز به دست آورد. اگر گراف کامل 2 بخشی G از دو بخش به ترتیب formula_11وformula_12 رأسی تشکیل شده باشد(formula_13)، تعداد درخت‌های پوشای برچسب‌دار G برابر است با formula_14