Prüferjeva zveza

Prüferjeva zveza je postopek za pretvarjanje označenega drevesa z n vozlišči v (n-2)-terico števil. Značilnost tako dobljenega zaporedja števil je, da enolično določa neko drevo - možna je tudi obratna pot. Funkcija pretvorbe je torej bijekcija.

Postopek pretvorbe:

1. med listi poiščemo tistega, ki je največji glede na oznako
2. v zaporedje dodamo oznako (edinega) soseda tega lista, odstranimo list
3. ponavljamo dokler ne ostaneta samo še dve vozlišči

Stopnja točke v drevesu je 1 + število ponovitev v zaporedju ki ga dobimo s to pretvorbo.

Primer uporabe

Zbriši največji list in zapiši njegovega soseda.

1. zbrišemo 7, zapišemo 1
2. zbrišemo 6, zapišemo 8
3. zbrišemo 5, zapišemo 1
4. zbrišemo 4, zapišemo 1
5. zbrišemo 2, zapišemo 3
6. zbrišemo 3, zapisemo 8

dobimo: [1,8,1,1,3,8]

Obratna pretvorba:

1. določimo liste (tiste oznake ki ne nastopajo v zaporedju)
2. določimo povezavo med največjim listom in prvim členom preostalega zaporedja
   1. odstranimo list in skrajšamo zaporedje
   2. če se odstranjeni člen ne pojavi več v zaporedju, ga dodamo med liste
3. ponavljamo dokler ne izpraznimo zaporedja
4. dodamo povezavo med preostalima listoma

Primer uporabe

Zaporedoma dodajaj povezave med tekočim elementom koda in največjim listom.

Zgled: [2,3,2,8,2,1]

1. števila (med 1 in 8), ki v kodi manjkajo, so listi drevesa. Največji list (7) povežemo s prvim elementom kode (2).
2. povezava 72 listi: [4,5,6]
3. povezava 63 listi: [3,4,5]
4. povezava 52 listi: [3,4]
5. povezava 48 listi: [3,8]
6. povezava x2 x=8 listi: [2,3]
7. povezava y 1 y=3 listi: [1,2]
8. povezava uv u=1, v=2