Codul Prufer

Codul Prufer mapează la un arbore finit arbitrar cu vârfuri o secvență de numere (de la la ) cu posibile repetări. Relația dintre un arbore cu vârfuri etichetate și un cod Prufer este unu-la-unu: fiecărui arbore îi corespunde un cod Prufer unic, iar elementele secvenței de cod sunt asociate cu numerele vârfurilor. În schimb, un arbore cu vârfuri poate fi restaurat în mod unic dintr-un anumit cod din numere . Codul a fost construit de Heinz Prüfer în timp ce demonstrează formula lui Cayley în 1918. [unu] $n$ $n-2$ $unu$ $n$ $n-2$ $n$

Clădire

Să fie un arbore cu vârfuri numerotate după numere . Construcția codului Prufer al arborelui T se realizează prin eliminarea secvențială a vârfurilor din arbore până când rămân doar două vârfuri. În acest caz, de fiecare dată când este selectat vârful final cu cel mai mic număr, iar numărul singurului vârf cu care este conectat este scris în cod. Rezultatul este o succesiune formată din numere , eventual cu repetări. $T$ $\{1,2,\puncte,n\}$ $(p_{1},\dots ,p_{n-2})$ $\{1,2,\puncte,n\}$

Exemplu

Pentru arborele din diagramă, vârful 1 este cel mai mic vârf terminal numerotat, deci este eliminat primul, iar 4 este scris în codul Prufer.

În continuare, vârfurile 2 și 3 sunt eliminate, astfel încât 4 este adăugat de două ori la cod.

Vârful 4 este acum nodul terminal și are cel mai mic număr, așa că este eliminat și 5 este adăugat la cod.

Au mai rămas doar două vârfuri, așa că codul este scris în întregime, iar procesul se oprește.

Rezultatul este un cod Prufer (4,4,4,5).

Restaurarea arborilor

Pentru a restabili arborele prin cod, să pregătim o listă de numere de vârf . Să alegem primul număr , care nu se găsește în cod. Adăugați o margine , apoi îndepărtați din și din . $p=(p_{1},\dots,p_{n-2})$ $s=(1,\dots,n)$ $i_1$ $(i_{1},p_{1})$ $i_1$ $s$ $p_{1}$ $p$

Repetăm procesul până când codul devine gol. În acest moment, lista conține exact două numere și . Rămâne să adăugați o margine și copacul este construit. $p$ $s$ $i_{n-1}$ $n$ $(i_{n-1},n)$

Proprietăți

Dacă este gradul vârfului cu număr , atunci apare exact ( ) ori în codul Prufer . $d_{i}$ $i$ $i$ $d_{i}-1$

Aplicații

Din codul Prufer rezultă formula Cayley , adică numărul de arbori care se întind dintr -un graf complet cu vârfuri este egal cu . Dovada rezultă din faptul că codul Prufer oferă o bijecție între copaci care se întind și secvențele de lungimi ale numerelor. $\Pi _{n}$ $n$ $n^{{n-2}}$ $n-2$ $n$
Codul Prufer permite, de asemenea, să generalizeze formula lui Cayley în cazul în care sunt date grade de vârfuri, dacă este o succesiune de grade a unui arbore, atunci numărul de arbori cu astfel de grade este egal cu coeficientul multinominal $(d_{1},\dots ,d_{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)!}}.

Codul Prufer este folosit pentru a construi arbori aleatori.

Link -uri

↑ Prüfer, H. Neuer Beweis eines Satzes über Permutationen (germană) // Arh. Matematică. Fizic.. - 1918. - Bd. 27 . - S. 742-744 .