Pruferův zákoník

Pruferův kód mapuje na libovolný konečný strom s vrcholy posloupnost čísel (od do ) s možným opakováním. Vztah mezi stromem s označenými vrcholy a Pruferovým kódem je jedna ku jedné: každý strom odpovídá jedinečnému Pruferovu kódu a prvky sekvence kódu jsou spojeny s čísly vrcholů. Naopak strom s vrcholy lze jednoznačně obnovit z daného kódu z čísel . Kód sestrojil Heinz Prüfer při dokazování Cayleyho vzorce v roce 1918. [jeden] $n$ $n-2$ $jeden$ $n$ $n-2$ $n$

Budova

Nechť existuje strom s vrcholy očíslovanými čísly . Konstrukce Pruferova kódu stromu T se provádí postupným odstraňováním vrcholů ze stromu, dokud nezůstanou pouze dva vrcholy. V tomto případě se pokaždé vybere koncový vrchol s nejmenším číslem a do kódu se zapíše číslo jediného vrcholu, se kterým je spojen. Výsledkem je sekvence složená z čísel , případně s opakováním. $T$ $\{1,2,\tečky,n\}$ $(p_{1},\tečky ,p_{n-2})$ $\{1,2,\tečky,n\}$

Příklad

Pro strom v diagramu je vrchol 1 nejnižším terminálním vrcholem, takže je odstraněn jako první a 4 je zapsán do Pruferova kódu.

Jako další jsou odstraněny vrcholy 2 a 3, takže 4 je přidána do kódu dvakrát.

Vertex 4 je nyní koncový uzel a má nejnižší číslo, takže je odstraněn a ke kódu je přidána 5.

Zbývají pouze dva vrcholy, takže kód je zapsán celý a proces se zastaví.

Výsledkem je Pruferův kód (4,4,4,5).

Obnova stromu

Pro obnovu stromu pomocí kódu si připravíme seznam čísel vrcholů . Zvolme první číslo , které v kódu nenajdeme. Přidejte okraj a poté odeberte z az . $p=(p_{1},\tečky ,p_{n-2})$ $s=(1,\tečky ,n)$ $i_1$ $(i_{1},p_{1})$ $i_1$ $s$ $p_{1}$ $p$

Postup opakujeme, dokud se kód nevyprázdní. V tomto okamžiku seznam obsahuje právě dvě čísla a . Zbývá přidat okraj a strom je postaven. $p$ $s$ $i_{n-1}$ $n$ $(i_{n-1},n)$

Vlastnosti

Jestliže je stupeň vrcholu s číslem , pak se v Pruferově kódu vyskytuje přesně ( ) krát . $d_{i}$ $i$ $i$ $d_{i}-1$

Aplikace

Cayleyův vzorec vyplývá z Pruferova kódu , to znamená, že počet kostry celého grafu s vrcholy je roven . Důkaz vyplývá ze skutečnosti, že Pruferův kód poskytuje bijekci mezi kostrami a délkovými posloupnostmi čísel . $\Pi _{n}$ $n$ $n^{{n-2}}$ $n-2$ $n$
Pruferův kód také umožňuje zobecnit Cayleyho vzorec na případ, kdy jsou dány stupně vrcholů, pokud je posloupnost stupňů stromu, pak se počet stromů s takovými stupni rovná multinominálnímu koeficientu. $(d_{1},\tečky ,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ův kód se používá k vytváření náhodných stromů.

Odkazy

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