Prüferova sekvence - Prüfer sequence

v kombinační matematika, Prüferova sekvence (taky Prüferův kód nebo Prüferova čísla) a označený strom je jedinečný sekvence spojené se stromem. Posloupnost stromu na n vrcholy má délku n - 2 a lze je generovat jednoduchým iteračním algoritmem. Prüferovy sekvence byly poprvé použity Heinz Prüfer dokázat Cayleyův vzorec v roce 1918.^[1]

Algoritmus pro převod stromu na Prüferovu sekvenci

Lze vygenerovat Prüferovu sekvenci označeného stromu iterativním odstraněním vrcholů ze stromu, dokud nezůstanou pouze dva vrcholy. Zvažte konkrétně označený strom T s vrcholy {1, 2, ..., n}. V kroku i, odstranit list s nejmenším štítkem a nastavit iPrvním prvkem Prüferovy sekvence je označení souseda tohoto listu.

Prüferova sekvence označeného stromu je jedinečná a má délku n − 2.

Jak kódování, tak dekódování lze redukovat na celočíselné třídění radixů a paralelizovat.^[2]

Příklad

Označený strom s Prüferovou sekvencí {4,4,4,5}.

Zvažte výše uvedený algoritmus spuštěný ve stromu zobrazeném vpravo. Zpočátku je vrchol 1 list s nejmenším štítkem, takže se nejprve odstraní a 4 se umístí do Prüferovy sekvence. Dále budou odstraněny vrcholy 2 a 3, takže 4 bude přidáno ještě dvakrát. Vertex 4 je nyní list a má nejmenší štítek, takže je odstraněn a k sekvenci přidáme 5. Zůstávají nám jen dva vrcholy, takže se zastavíme. Pořadí stromu je {4,4,4,5}.

Algoritmus pro převod Prüferovy sekvence na strom

Nechat {a [1], a [2], ..., a [n]} být Prüferova sekvence:

Strom bude mít n + 2 uzly, očíslované od 1 na n + 2.Pro každý uzel nastavte jeho stupeň na počet, kolikrát se objeví v sekvenci plus 1. Například v pseudokódu:

 Převeďte-Prüfer-na-strom(A) 1 n ← délka[A] 2 T ← graf s n + 2 izolované uzly, očíslované 1 na n + 2 3 stupeň ← pole celých čísel 4 pro každý uzel i v T dělat 5     stupeň[i] ← 1 6 pro každou hodnotu i v A dělat 7     stupeň[i] ← stupeň[i] + 1

Dále pro každé číslo v pořadí a [i], najděte první uzel s nejnižším číslem, j, se stupněm rovným 1, přidejte hranu (j, a [i]) ke stromu a snižovat stupně j a a [i]. V pseudokódu:

 8 pro každou hodnotu i v A dělat 9     pro každý uzel j v T dělat10         -li stupeň[j] = 1 pak11 Vložit okraj[i, j] do T12             stupeň[i] ← stupeň[i] - 113             stupeň[j] ← stupeň[j] - 114             přestávka

Na konci této smyčky zůstanou dva uzly se stupněm 1 (zavolejte jim u, proti). Nakonec přidejte okraj (u, v) ke stromu.^[3]

15 u ← proti ← 016 pro každý uzel i v T17     -li stupeň[i] = 1 pak18         -li u = 0 pak19             u ← i20         jiný21             proti ← i22             přestávka23 Vložit okraj[u, proti] do T24 stupeň[u] ← stupeň[u] - 125 stupeň[proti] ← stupeň[proti] - 126 vrátit se T

Cayleyův vzorec

Prüferova sekvence označeného stromu na n vertices je jedinečná sekvence délky n - 2 na štítcích 1 až n. Pro danou sekvenci S délky n–2 na štítcích 1 až n, tady je unikátní označený strom, jehož sekvence Prüfer je S.

Okamžitým důsledkem je, že Prüferovy sekvence poskytují a bijekce mezi sadou označených stromů na n vrcholy a množina posloupností délky n - 2 na štítcích 1 až n. Druhá sada má velikost nⁿ⁻², takže existence této bijekce dokazuje Cayleyův vzorec, tj. že existují nⁿ⁻² označené stromy na n vrcholy.

Další aplikace^[4]

• Cayleyův vzorec lze posílit, aby dokázal následující tvrzení:

Počet koster v kompletním grafu ${ displaystyle K_ {n}}$ s titulem ${ displaystyle d_ {i}}$ zadáno pro každý vrchol ${ displaystyle i}$ se rovná multinomický koeficient

${ displaystyle { binom {n-2} {d_ {1} -1, , d_ {2} -1, , tečky, , d_ {n} -1}} = { frac {(n -2)!} {(D_ {1} -1)! (D_ {2} -1)! Cdots (d_ {n} -1)!}}}}$

Důkaz následuje pozorováním, že v pořadovém čísle Prüfer ${ displaystyle i}$ se objeví přesně ${ displaystyle (d_ {i} -1)}$ krát.

• Cayleyův vzorec lze zobecnit: označený strom je ve skutečnosti a kostra označeného kompletní graf. Umístěním omezení na vyjmenované Prüferovy sekvence mohou podobné metody poskytnout počet překlenujících stromů celku bipartitní graf. Li G je kompletní bipartitní graf s vrcholy 1 až n₁ v jedné přepážce a vrcholech n₁ + 1 až n v druhém oddílu počet označených spanning stromů G je ${ displaystyle n_ {1} ^ {n_ {2} -1} n_ {2} ^ {n_ {1} -1}}$, kde n₂ = n − n₁.
• Generování rovnoměrně rozložených náhodných Prüferových sekvencí a jejich převod do odpovídajících stromů je přímá metoda generování rovnoměrně rozložených náhodných značených stromů.

Reference

externí odkazy

• Prüferův kód - z MathWorld