Prufer kod

Prufer-koden mappar till ett godtyckligt ändligt träd med hörn en sekvens av tal (från till ) med möjliga upprepningar. Relationen mellan ett träd med märkta hörn och en Prufer-kod är en-till-en: varje träd motsvarar en unik Prufer-kod, och element i kodsekvensen är associerade med vertexnumren. Omvänt kan ett träd med hörn återställas unikt från en given kod från nummer . Koden konstruerades av Heinz Prüfer samtidigt som Cayleys formel bevisades 1918. [ett] $n$ $n-2$ $ett$ $n$ $n-2$ $n$

Byggnad

Låt det finnas ett träd med hörn numrerade med siffror . Konstruktionen av Prufer-koden för trädet T utförs genom att sekventiellt ta bort hörn från trädet tills endast två hörn återstår. I det här fallet skrivs varje gång ändpunkten med det minsta numret väljs, och numret på den enda vertex som den är ansluten till, in i koden. Resultatet är en sekvens som består av siffror , eventuellt med upprepningar. $T$ $\{1,2,\dots,n\}$ $(p_{1},\dots ,p_{n-2})$ $\{1,2,\dots,n\}$

Exempel

För trädet i diagrammet är vertex 1 den lägsta numrerade terminala vertexen, så den tas bort först och 4 skrivs till Prufer-koden.

Hörnen 2 och 3 tas bort härnäst, så 4 läggs till två gånger i koden.

Vertex 4 är nu terminalnoden och har det lägsta numret, så det tas bort och 5 läggs till i koden.

Det finns bara två hörn kvar, så koden skrivs i sin helhet och processen stannar.

Resultatet är en Prufer-kod (4,4,4,5).

Trädrestaurering

För att återställa trädet med kod, låt oss förbereda en lista med vertexnummer . Låt oss välja det första numret som inte finns i koden. Lägg till en kant och ta sedan bort från och från . $p=(p_{1},\dots ,p_{n-2})$ $s=(1,\dots ,n)$ $i_1$ $(i_{1},p_{1})$ $i_1$ $s$ $p_{1}$ $sid$

Vi upprepar processen tills koden blir tom. Vid det här laget innehåller listan exakt två siffror och . Det återstår att lägga till en kant , och trädet är byggt. $sid$ $s$ $i_{n-1}$ $n$ $(i_{n-1},n)$

Egenskaper

Om är graden av vertex med nummer , så förekommer det exakt ( ) gånger i Prufer-koden . $d_{i}$ $i$ $i$ $d_{i}-1$

Applikationer

Cayley-formeln följer av Prufer-koden , det vill säga antalet spännande träd i en komplett graf med hörn är lika med . Beviset följer av det faktum att Prufer-koden ger en bijektion mellan spännande träd och längdsekvenser av tal. $\Pi _{n}$ $n$ $n^{{n-2}}$ $n-2$ $n$
Prufer-koden tillåter också att generalisera Cayleys formel till fallet när grader av hörn ges, om är en sekvens av grader av ett träd, då är antalet träd med sådana grader lika med den multinominella koefficienten $(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)!}}.

Prufer-koden används för att bygga slumpmässiga träd.

Länkar

↑ Prüfer, H. Neuer Beweis eines Satzes über Permutationen (tyska) // Arch. Matematik. Phys.. - 1918. - Bd. 27 . - S. 742-744 .