Кіріспе
Комбинаторлық математикада, белгіленген ағаштың Пруфер тізбегі (сондай-ақ Пруфер коды немесе Пруфер сандары) – бұл ағашқа сәйкес келетін бірегей тізбек. n төбесі бар ағаш үшін тізбектің ұзындығы n–2-ге тең, және оны қарапайым итерациялық алгоритм арқылы құруға болады. Пруфер тізбектерін алғаш рет Хайнц Пруфер 1918 жылы Кейли формуласын дәлелдеу үшін пайдаланды.
Ағаштарды Пруфер тізбегіне айналдыру алгоритмі
Бір белгіленген ағаштың Пруфер тізбегін, ағаштан екі түйін қалғанша түйіндерді қайталап алып тастау арқылы жасауға болады. Атап айтқанда, {1, 2, ..., n} түйіндері бар T белгіленген ағашын қарастырайық. i-ші қадамда, ең кіші нөмірлі жапырақты алып тастап, Пруфер тізбегінің i-ші мүшесін осы жапырақтың көршісінің нөміріне тең етіңіз. Белгіленген ағаштың Пруфер тізбегі бірегей және ұзындығы n – 2-ге тең. Кодтау және декодтауды да бүтін сан радиксі бойынша сұрыптауға және параллельдеуге келтіруге болады.
Мысал
Жоғарыда көрсетілген алгоритмді оң жақтағы ағашқа қарай қолданайық. Бастапқыда 1-шы төбе ең кішкентай белгісі бар жапырақ болып табылады, сондықтан ол бірінші болып алынып тасталады және 4 саны Прюфер тізбегіне қосылады. Келесі кезекте 2-ші және 3-ші төбелер алынып тасталады, сондықтан 4 саны тағы екі рет қосылады. 4-ші төбе енді жапырақ болып табылады және ең кішкентай белгісіне ие, сондықтан ол алынып тасталады және біз тізбеге 5 санын қосамыз. Бізге тек екі төбе қалды, сондықтан тоқтаймыз. Ағаштың тізбегі {4,4,4,5} болады.
Кейли формуласы
n түйіндік таңбаланған ағаштың Пруфер тізбегі – 1-ден n-ге дейінгі таңбалардан тұратын, n-2 ұзындығындағы бірегей тізбек. 1-ден n-ге дейінгі таңбалардан тұратын, n-2 ұзындығындағы берілген S тізбегі үшін, Пруфер тізбегі S болып табылатын бірегей таңбаланған ағаш бар.
Бұл тікелей салдары – Пруфер тізбектері n түйіндік таңбаланған ағаштар жиыны мен 1-ден n-ге дейінгі таңбалардан тұратын n-2 ұзындығындағы тізбектер жиыны арасындағы бір-бірге сәйкестік (биекция) орнатуға мүмкіндік береді. Соңғы жиынның саны n^(n-2) болғандықтан, осы бір-бірге сәйкестіктің болуы Кейли формуласын дәлелдейді, яғни n түйіндік n^(n-2) таңбаланған ағаш бар.