در ریاضیات ترکیبیاتی، کدِ پروفر ( دنبالهٔ پروفر یا اعداد پروفر ) برای یک درخت برچسب دار، یک دنباله از اعداد است که به این درخت نسبت داده می شود. طول این دنباله برای یک درخت n رأسی دقیقاً n - 2 است، و می توان آن را با یک الگوریتم تکرار شونده ساده تولید کرد. پروفر کد برای اولین بار به وسیلهٔ هینز پروفر برای اثبات فرمول کیلی استفاده شد. [ ۱]
کد پروفر برای یک درخت می تواند با حذف کردن پی در پی رأس های یک درخت تا وقتی که تنها ۲ رأس مانده، به دست آید. یعنی اگر T یک درخت برچسب دار با رأس های { 1 , 2 , . . . , n } باشد، در مرحلهٔ iام کوچک ترین برگ درخت را حذف کرده و شمارهٔ همسایهٔ آن را به عنوان عنصر iام کد قرار می دهیم. کد پروفر برای یک درخت برچسب دار یکتاست و دقیقاً n - 2 عنصر دارد.
فرض کنید الگوریتم بالا بر روی درخت سمت چپ اجرا شود. در ابتدا رأس شمارهٔ 1 برگی است که کوچک ترین شماره را بین برگ ها دارد، از این رو این برگ اول از همه پاک می شود و عدد 4 ( شمارهٔ رأس متصل به 1 ) در کد پروفر قرار می گیرد. سپس رأس های 2 و 3 حذف می شوند، پس 4 دو بار دیگر نیز به کد اضافه خواهد شد. در این حال رأس 4 کوچک ترین برگ در درخت است و در نتیجه ما 4 را نیز حذف می کنیم و شمارهٔ 5 را به دنباله اضافه می کنیم. تنها 2 رأس باقی مانده پس فرایند متوقف خواهد شد.
فرض کنید { a , a , . . . , a } یک کد پروفر باشد. درخت حاصل n+2 رأس، با شماره های 1تاn+2 خواهد داشت. درجه را برای هر رأس یکی بیشتر از تعداد بارهای ظاهر شدن آن در دنبالهٔ پروفر قرار دهید. برای مثال به صورت شبه کد:
Convert - Prüfer - to - Tree ( a ) 1 n ← length 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 ← 1 6 for each value i in a 7 do degree ← degree + 1 سپس برای هر رأس در a ، کوچک ترین رأس j با درجهٔ 1 را پیدا کنید و با اضافه کردن یال ( j, a ) به درخت از درجهٔ این دو رأس یک واحد کم کنید. به صورت شبه کد:
8 for each value i in a 9 for each node j in T 10 if degree = 1 11 then Insert edge into T 12 degree ← degree - 1 13 degree ← degree - 1 14 break در انتهای حلقه دو رأس با درجهٔ یک باقی می ماند ( فرض کنیدvوu ) در پایان یال ( v, u ) را به درخت اضافه کنید. [ ۲]
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفکد پروفر برای یک درخت می تواند با حذف کردن پی در پی رأس های یک درخت تا وقتی که تنها ۲ رأس مانده، به دست آید. یعنی اگر T یک درخت برچسب دار با رأس های { 1 , 2 , . . . , n } باشد، در مرحلهٔ iام کوچک ترین برگ درخت را حذف کرده و شمارهٔ همسایهٔ آن را به عنوان عنصر iام کد قرار می دهیم. کد پروفر برای یک درخت برچسب دار یکتاست و دقیقاً n - 2 عنصر دارد.
فرض کنید الگوریتم بالا بر روی درخت سمت چپ اجرا شود. در ابتدا رأس شمارهٔ 1 برگی است که کوچک ترین شماره را بین برگ ها دارد، از این رو این برگ اول از همه پاک می شود و عدد 4 ( شمارهٔ رأس متصل به 1 ) در کد پروفر قرار می گیرد. سپس رأس های 2 و 3 حذف می شوند، پس 4 دو بار دیگر نیز به کد اضافه خواهد شد. در این حال رأس 4 کوچک ترین برگ در درخت است و در نتیجه ما 4 را نیز حذف می کنیم و شمارهٔ 5 را به دنباله اضافه می کنیم. تنها 2 رأس باقی مانده پس فرایند متوقف خواهد شد.
فرض کنید { a , a , . . . , a } یک کد پروفر باشد. درخت حاصل n+2 رأس، با شماره های 1تاn+2 خواهد داشت. درجه را برای هر رأس یکی بیشتر از تعداد بارهای ظاهر شدن آن در دنبالهٔ پروفر قرار دهید. برای مثال به صورت شبه کد:
Convert - Prüfer - to - Tree ( a ) 1 n ← length 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 ← 1 6 for each value i in a 7 do degree ← degree + 1 سپس برای هر رأس در a ، کوچک ترین رأس j با درجهٔ 1 را پیدا کنید و با اضافه کردن یال ( j, a ) به درخت از درجهٔ این دو رأس یک واحد کم کنید. به صورت شبه کد:
8 for each value i in a 9 for each node j in T 10 if degree = 1 11 then Insert edge into T 12 degree ← degree - 1 13 degree ← degree - 1 14 break در انتهای حلقه دو رأس با درجهٔ یک باقی می ماند ( فرض کنیدvوu ) در پایان یال ( v, u ) را به درخت اضافه کنید. [ ۲]
wiki: پروفر کد