ITT0030 Diskreetne matemaatika II - eksamikonspekt
n-tipuliste märgendamata puude arv rahuldab võrratusi ehk
(kui n>30). See tähendab, et puudub algoritm arvutamaks n-tipuliste märgendamata puude
täpset arvu. Teada on vaid antud vahemik, kuhu see arv langeb.
a). Alumine tõke tuleneb sellest järeldusest, et iga n-tipulist puud saab erinvate
märgenditega märgendada täpselt n! viisil.
b). Ülemine tõke tuleneb aga juurega puude kõikvõimalike planaarkoodide arvust
On ju selge, et puid peab olema vähem kui erinevaid planaarkoode, kuna planaarkoodid pole
üheselt määratudki. Seega on ülemiseks tõkkeks 22(n-1).
Planaarkood e. binaarkood- tehnika, mida kasutatakse märgendamata puude esitamiseks
ning salvestamiseks. Kuna kõiki puu servi läbitakse 2 korda: edasi ning tagasi minnes, on n-
tipulise puu binaarkoodis 2(n-1) kahendkohta. Binaarkoodi põhjal saab puu üheselt taastada.
*Erinevalt Prüferi koodist, ei ole mingi puu planaarkood üheselt määratud e. unikaalne,
annaabi.ee 
