Diskreetsed struktuurid
Lahendus. Olgu An kõigi n-täheliste sõnade arv. Ülesande tingimuste põh-
jal kehtib seos
An+1 = 2An + 8An-1 .
Algtingimused on A1 = 1, A2 = 1.
Karakteristliku võrrandi q 2 - 2q - 8 = 0 lahendid on q1 = 4, q2 = -2.
Järelikult rekurrentse võrrandi üldlahend on
An = c1 · 4n + c2 · (-2)n .
Algtingimuste põhjal saame võrrandisüsteemi
4c1 - 2c2 = 1
16c1 + 4c2 = 1,
mille lahendid on c1 = 81 , c2 = - 41 . Kõigi n-täheliste sõnade arv on seega
1 n 1
An = · 4 - · (-2)n .
8 4
Materjal õpikus. Lk 3640 (teist järku rekurrentsete võrrandite lahenda-
mine).
Ülesanne 3. Teha kindlaks, kas järgmiste naabrusmaatriksitega antud graa-
fid on isomorfsed. Jaatava vastuse korral kirjutada välja isomorfism, eitava
vastuse korral põhjendada
annaabi.ee 
