"aluspuude" - 1 õppematerjal

ITT0030 Diskreetne matemaatika II - eksamikonspekt

prognoosimiseks bioloogias. *Veel üks huvitav jada omadus: gcd(Fn,Fm) = Fgcd(n,m) [17]. Lucas` arvud. Lucas' arvud on defineeritud täpselt sama lineaarse rekurrentse võrrandi baasil, mis Fibonacci arvudki. Erinevad on vaid algtingimused. Lucas' arvud avalduvad seega võrrandist: Ln = Ln-1 + Ln-2 , kus algtingimusteks L1= 1 ning L2= 3 *Lucas' arvujada leiab rakendust näiteks graafiteoorias, kuna tema abil on võimalik leida n- tipulise graafi kõikvõimalike aluspuude arvu. Täpsemalt kehtib seos T(Wn) = L2n ­ 2, kus n on esialgse graafi tippude arv. *Rakendusi leidub aga ka hulgateoorias: on avastatud, et mingi hulga A alamhulka suvalisel heuristilisel valikul on täpselt Ln sellist võimalust, mille korral valitud alamhulgas ei sisaldu kaht järjestikust arvu. *Arvuteoorias: selgub, et kui n on algarv, siis kehtib alati kongruents Ln 1 (mod n). *Lucas' arvujada on oma nime saanud prantsuse matemaatiku F.E.A.Lucas' järgi, kes