Prufer-koodi

Prufer-koodi kartoittaa mielivaltaiseen äärelliseen puuhun , jossa on pisteet , numerosarjan (alkaen - ) mahdollisine toistoineen. Suhde puun, jossa on otsikoita, ja Prufer-koodin välillä on yksi yhteen: jokainen puu vastaa yksilöllistä Prufer-koodia, ja koodisekvenssin elementit liitetään kärkinumeroihin. Päinvastoin, puu, jolla on pisteet , voidaan palauttaa yksilöllisesti annetusta koodista numeroista . Koodin rakensi Heinz Prüfer todistaessaan Cayleyn kaavan vuonna 1918. [yksi] $n$ $n-2$ $yksi$ $n$ $n-2$ $n$

Rakentaminen

Olkoon puu, jonka kärjet on numeroitu numeroilla . Puun T Prufer-koodin rakentaminen suoritetaan poistamalla peräkkäin pisteitä puusta, kunnes jäljelle jää vain kaksi kärkeä. Tässä tapauksessa joka kerta, kun valitaan pienimmän numeron omaava loppupiste, ja koodiin kirjoitetaan sen ainoan kärjen numero, johon se on yhdistetty. Tuloksena on sekvenssi , joka koostuu numeroista , mahdollisesti toistoista. $T$ $\{1,2,\pisteet,n\}$ ${\näyttötyyli (p_{1},\pisteet ,p_{n-2})}$ $\{1,2,\pisteet,n\}$

Esimerkki

Kaavion puulle kärkipiste 1 on alin numeroitu päätepiste, joten se poistetaan ensin ja 4 kirjoitetaan Prufer-koodiin.

Vertices 2 ja 3 poistetaan seuraavaksi, joten 4 lisätään koodiin kahdesti.

Vertex 4 on nyt päätesolmu ja sillä on pienin numero, joten se poistetaan ja koodiin lisätään 5.

Jäljellä on vain kaksi kärkeä, joten koodi kirjoitetaan kokonaan ja prosessi pysähtyy.

Tuloksena on Prufer-koodi (4,4,4,5).

Puiden entisöinti

Jos haluat palauttaa puun koodin perusteella, valmistetaan luettelo kärkinumeroista . Valitaan ensimmäinen numero , jota ei löydy koodista. Lisää reuna ja poista sitten . $p=(p_{1},\dots ,p_{n-2})$ $s=(1,\pisteet ,n)$ $i_1$ $(i_{1},p_{1})$ $i_1$ $s$ $p_{1}$ $s$

Toistamme prosessia, kunnes koodi tyhjenee. Tässä vaiheessa luettelo sisältää täsmälleen kaksi numeroa ja . Vielä on lisättävä reuna , ja puu on rakennettu. $s$ $s$ $i_{n-1}$ $n$ ${\näyttötyyli (i_{n-1},n)}$

Ominaisuudet

Jos on pisteen aste numerolla , niin se esiintyy Prufer - koodissa täsmälleen ( ) kertaa . $d_{i}$ $i$ $i$ $d_{i}-1$

Sovellukset

Cayleyn kaava seuraa Prufer-koodia , eli kokonaisen graafin , jossa on pisteet, virittävien puiden lukumäärä on yhtä suuri kuin . Todistus seuraa siitä tosiasiasta, että Prufer-koodi antaa bijektion virittävien puiden ja pituisten lukujonojen välillä . $\Pi _{n}$ $n$ $n^{{n-2}}$ $n-2$ $n$
Prufer-koodin avulla voidaan myös yleistää Cayleyn kaava tapaukseen, jossa on annettu kärkien asteet, jos on puun astejono, niin puiden määrä tällaisilla asteikoilla on yhtä suuri kuin moninomikerroin ${\näyttötyyli (d_{1},\pisteet ,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-koodia käytetään satunnaisten puiden rakentamiseen.

Linkit

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