"kahendkohta" - 1 õppematerjal

ITT0030 Diskreetne matemaatika II - eksamikonspekt

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, kuna puu juureks võib alati valida erinevaid tippe. [38]. Kooskõlad graafis. Berge'i teoreem. Kooskõlaks nimetatakse orienteerimata graafi G = (V,E) servade sellist alamhulka ME, kus mistahes kaks serva ei oma kahekaupa võetuna sama otspunkti. Kooskõlaline e. küllastunud tipp- tipu nimetatakse kooskõlastatuks, kui ta on mõne hulka M