Prufer kode

Prufer-koden afbildes til et vilkårligt endeligt træ med knudepunkter en sekvens af tal (fra til ) med mulige gentagelser. Forholdet mellem et træ med mærkede hjørner og en Prufer-kode er en-til-en: hvert træ svarer til en unik Prufer-kode, og elementer i kodesekvensen er forbundet med topnumrene. Omvendt kan et træ med toppunkter entydigt gendannes fra en given kode fra tal . Koden blev konstrueret af Heinz Prüfer , mens han beviste Cayleys formel i 1918. [en] $n$ $n-2$ $en$ $n$ $n-2$ $n$

Konstruktion

Lad der være et træ med toppunkter nummereret med tal . Konstruktionen af Prufer-koden for træet T udføres ved sekventielt at fjerne toppunkter fra træet, indtil der kun er to toppunkter tilbage. I dette tilfælde, hver gang endepunktet med det mindste tal vælges, og nummeret på det eneste toppunkt, som det er forbundet med, skrives ind i koden. Resultatet er en sekvens bestående af tal , muligvis med gentagelser. $T$ $\{1,2,\dots,n\}$ $(p_{1},\dots ,p_{n-2})$ $\{1,2,\dots,n\}$

Eksempel

For træet i diagrammet er toppunkt 1 det laveste nummererede endepunkt, så det fjernes først, og 4 skrives til Prufer-koden.

Hjørnepunkt 2 og 3 fjernes derefter, så 4 tilføjes to gange til koden.

Vertex 4 er nu terminalknudepunktet og har det laveste nummer, så det fjernes og 5 tilføjes koden.

Der er kun to hjørner tilbage, så koden skrives fuldt ud, og processen stopper.

Resultatet er en Prufer-kode (4,4,4,5).

Trærestaurering

For at gendanne træet efter kode, lad os udarbejde en liste over topnumre . Lad os vælge det første tal , som ikke findes i koden. Tilføj en kant , og fjern derefter fra og fra . $p=(p_{1},\dots ,p_{n-2})$ $s=(1,\dots ,n)$ $i_1$ $(i_{1},p_{1})$ $i_1$ $s$ $p_{1}$ $s$

Vi gentager processen, indtil koden bliver tom. På dette tidspunkt indeholder listen præcis to tal og . Det er tilbage at tilføje en kant , og træet er bygget. $s$ $s$ $i_{n-1}$ $n$ $(i_{n-1},n)$

Egenskaber

Hvis er graden af toppunktet med tal , så forekommer det nøjagtigt ( ) gange i Prufer-koden . $d_{i}$ $jeg$ $jeg$ $d_{i}-1$

Ansøgninger

Cayley-formlen følger af Prufer-koden , det vil sige, at antallet af spændende træer i en komplet graf med hjørner er lig med . Beviset følger af det faktum, at Prufer-koden giver en bijektion mellem spændende træer og længdesekvenser af tal. $\Pin}$ $n$ $n^{{n-2}}$ $n-2$ $n$
Prufer-koden gør det også muligt at generalisere Cayleys formel til det tilfælde, hvor grader af hjørner er givet, hvis er en sekvens af grader af et træ, så er antallet af træer med sådanne grader lig med den multinominelle koefficient $(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)!}}.