Diskreetsed struktuurid (2)

Kontrolltöö lahendused Diskreetsed struktuurid 1. variant Ülesanne 1. 15 inimese hulgas on A ja B omavahel sõbrad ning C ja D omavahel vaenlased. Mitmel viisil saab need inimesed jaotada 5 ühesuuruseks rühmaks nii, et sõbrad kuuluksid samasse rühma, aga vaenlased erinevatesse rühmadesse? Rühmade järjekord oluline ei ole. Lahendus. Iga rühm peab sisaldama 3 inimest. Paigutame A ja B esimesse rühma. Kui selle rühma kolmas liige on C, siis tuleb ülejäänud 12 inimest jao- tada 4 ühesuuruseks rühmaks, ülesande tingimused saavad sellega täidetud. Eeldame esialgu, et nende 4 rühma järjekord on oluline. Valime 3 inimest esimesse rühma, selleks on 123 võimalust. Ülejäänud 9 inimesest valime 3 inimest teise rühma, milleks on 93 võimalust. Lõpuks valime 6 inimesest 3, kes moodustavad kolmanda rühma, selleks on 63 võimalust. Sellega on rühmade koosseisud määratud. Üldse on võimalusi seega 12 3 · 93 · 63 . Et aga tegelikult nende 4 rühma omavaheline järjekord oluline ei ole, siis on jaotusvõimalusi 1 12 9 6 · · · = 15400. 4! 3 3 3 Kui inimestega A ja B samasse rühma kuulub D, siis on võimalusi samuti 15400. Kui inimestega A ja B samasse rühma ei kuulu C ega D, siis selle rühma kolmanda liikme valimiseks järelejäänute hulgast on 11 võimalust. Seejärel inimesele C kahe paarilise valimiseks on 10 2 võimalust (keelatud on lisaks kolmele esimese rühma liikmele veel C ja D), edasi inimesele D kahe paarilise valimiseks on 82 võimalust (keelatud on kahe eelmise rühma liikmed ja D). Ülejäänud 6 inimesest tuleb moodustada 2 rühma. Valime 6 inimesest 3, milleks on 63 võimalust, ning et rühmade järjekord pole oluline, jagame tulemust veel arvuga 2!. Kokku on võimalusi
10 8 1 6 11 · · · · = 138600. 2 2 2! 3
Vaadeldud kolm juhtu on üksteist välistavad ja katavad kõik variandid, liitmisreegli põhjal on võimaluste arv seega 15400+15400+138600 = 169400. Märkus. Rühmade järjekorra muutumist on vaja arvestada ainult nende rühmade puhul, mis saavad moodustamisprotsessis tekkida mitmel erineval sammul . Näiteks rühm, mis sisaldab inimesi A ja B, saab tekkida ainult esimesel sammul, seetõttu ei ole vaja võtta arvesse (hüpoteetilist) juhtu, kus see rühm tekib nt neljandal sammul. Teiste sõnadega, järjekorra muutumist pole vaja arvestada nende rühmade puhul, mida me saame ise juba eelnevalt mingi tunnuse alusel järjestada. Materjal õpikus. Lk 14 (kombinatsioonid). Lk 19 (korrutamis- ja liitmis - reegel). Lk 21, ülesanded 16, 17. Lk 22, ülesanded 21­23. Ülesanne 2. ingivi keeles on 1 ühetäheline ja 1 kahetäheline sõna. Igast sõnast pikkusega n on võimalik ühe tähe juurdekirjutamisega saada 2 sõna pikkusega n + 1 ning igast sõnast pikkusega n - 1 on võimalik kahe tähe juurdekirjutamisega saada 8 sõna pikkusega n + 1. Kõik saadavad sõnad on erinevad ja rohkem sõnu pikkusega n + 1 ei ole. Leida avaldis , millest on võimalik ainult naturaalarvu n järgi välja arvutada, mitu sõna pikkusega n keeles leidub. 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 36­40 (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. 0 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 1 0 1 1 1 0 0 1 0 G= 0 1 1 0 0 1 H= 1 1 0 0 0 1 1 1 0 0 0 1 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 0
Lahendus. Joonistades välja graafide täiendid, leiame, et graafi G täiend on tsükkel tippudega 1, 4, 5, 3, 2, 6 ning graafi H täiend on tsükkel tippudega 1, 2, 5, 4, 3, 6. Et kaks sama tippude arvuga tsüklit on isomorfsed, siis on ka graafid G ja H isomorfsed. Üks isomorfism on näiteks bijektsioon , mis teisendab graafi G tipud graafi H tippudeks järgmisel viisil: (1) = 1, (2) = 3, (3) = 4, (4) = 2, (5) = 5, (6) = 6. Materjal õpikus. Lk 57­59 (graafide isomorfism). Lk 62, ülesanded 37­41.
Ülesanne 4. Mitu serva peab 9-tipulisel graafil vähemalt olema, et selles graafis kindlasti ei leiduks sildu ? Lahendus. Oletame, et graafis leidub sild ja uurime, milline saab olla sel juhul graafi suurim servade arv. Sild peab ühendama kahte komponenti, mis selleks, et servade arv oleks suurim, peavad eraldi võetuna olema täisgraafid. Teame, et n-tipulise täisgraafi servade arv on n(n-1) 2 . 9-tipulise graafi tipud võivad jaguneda kas (1, 8), (2, 7), (3, 6) või (4, 5). Esimesel juhul on graafi maksimaalne servade arv 1 + 0 + 8·7 2 = 29, teisel juhul 1 + 1 + 7·62 = 23, kolmandal juhul 1 + 3 + 6·5 2 = 19 ja neljandal juhul 1 + 2 + 2 = 17. Seega kui 9-tipulisel graafil on rohkem kui 29 serva, st 4·3 5·4
vähemalt 30 serva, siis ei saa selline graaf sisaldada ühtegi silda. Materjal õpikus. Lk 53­55 (sidusus). Ülesanne 5. Teha kindlaks, kas järgmine positiivsete reaalarvude hulgal määratud relatsioonekvivalents . 2 Lahendus. Võrdus xy2 = xy on samaväärne võrdusega x3 = y 3, sest põhi- hulga elemendid on positiivsed reaalarvud. Järelikult võ. Kontrollime ekvivalentsi omaduste kehtivust.
· Relatsioon on refleksiivne, sest iga positiivse reaalarvu x korral kehtib x3 = x3 , st (x, x) R.
· Relatsioon on sümmeetriline, sest kui x3 = y 3, siis ka y 3 = x3 , st kui (x, y) R, siis ka (y, x) R.
· Relatsioon on transitiivne , sest kui x3 = y 3 ja y 3 = z 3 , x3 = z 3 , st kui (x, y) R ja (y, z) R, siis ka (x, z) R.
Seega see relatsioon on ekvivalents. Materjal õpikus. Lk 90­92 (ekvivalentsirelatsioon). Lk 94­95, ülesanded 5­10, 19­24. Kontrolltöö lahendused Diskreetsed struktuurid 2. variant Ülesanne 1. Raamat Mittediskreetne matemaatika koosneb 4-st peatükist, igaühes 7 teoreemi. Eksamiülesannete komplekt peab sisaldama 10 teoreemi tõestust, sealjuures igast peatükist vähemalt 2. Mitu võimalust on koostada nendele tingimustele vastav teoreemide tõestustest koosnev eksamikomplekt aines Mittediskreetne matemaatika? Lahendus. Kui komplekt sisaldab 4 teoreemi ühest peatükist ja ülejäänu- test igaühest 2, siis selle peatüki valikuks , millest võetakse 4 teoreemi, on 4 võimalust ja teoreemide endi valikuks 74 võimalust. Kolmest ülejäänud pea- tükist on igaühe puhul kahe teoreemi valimiseks 72 võimalust. Et kõigil sam- mudel on valikuvõimaluste arvud üksteisest sõltumatud, siis korrutamisreegli 3 põhjal saab niisuguseid eksamikomplekte koostada 4· 74 · 72 = 1296540 tük- ki. Kui komplekt sisaldab kahest peatükist kummastki 3 teoreemi ja ülejää- nud kahest kummastki 2 teoreemi, siis nende peatükkide valikuks, millest võetakse 3 teoreemi, on 42 võimalust. Teoreemide endi valikuks on 3 vali- tava teoreemiga peatükkide puhul 73 võimalust, 2 valitava teoreemiga pea- tükkide puhul aga 72 võimalust. Siin on võimalikke eksamikomplekte seega 4 2 2 2 · 73 · 72 = 3241350. Sellega on kõik teoreemide valikuviisid ammendatud , võimalusi on kokku 1296540 + 3241350 = 4537890. Materjal õpikus. Lk 14 (kombinatsioonid). Lk 19 (korrutamis- ja liitmis- reegel). Lk 22, ülesanded 21­23. Lk 21, ülesanne 15. Ülesanne 2. Teatav algoritm kulutab sisendandmete mahu n korral ülesan- de lahendamiseks kaks korda nii palju aega kui sisendandmete mahu n - 1 korral pluss veel kolm korda nii palju aega kui mahu n - 2 korral. Leida aval- dis, millest on võimalik ainult naturaalarvu n järgi välja arvutada algoritmi tööaeg sisendandmete mahu n korral, kui mahu 0 korral on tööaeg 1 ajaühik ja mahu 1 korral 2 ühikut. Lahendus. Olgu An algoritmi tööaeg sisendandmete mahu n korral. Üles- ande tingimuste põhjal kehtib seos An = 2An-1 + 3An-2 . Algtingimused on A0 = 1, A1 = 2. Karakteristliku võrrandi q 2 - 2q - 3 = 0 lahendid on q1 = 3, q2 = -1. Järelikult rekurrentse võrrandi üldlahend on
An = c1 · 3n + c2 · (-1)n .
Algtingimuste põhjal saame võrrandisüsteemi
c1 + c2 = 1 3c1 - c2 = 2,
mille lahendid on c1 = 43 , c2 = 14 . Algoritmi tööaeg sisendandmete mahu n korral on seega
3 n 1 3n+1 + (-1)n An = · 3 + · (-1)n = . 4 4 4 Materjal õpikus. Lk 36­40 (teist järku rekurrentsete võrrandite lahenda- mine). Ülesanne 3. Teha kindlaks, kas järgmise naabrusmaatriksiga antud suuna- tud graaf on tugevalt sidus. 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1 1 G= 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0
Lahendus. Joonistades välja selle suunatud graafi, nä nii, et esimese hulga ühestki tipust ei vii kaart teise hulga ühessegi tippu. Järelikult ei ole või- malik esimese hulga tippudest pääseda teise hulga tippudesse, st graaf ei ole tugevalt sidus. Materjal õpikus. Lk 79­81 (tugev ja nõrk sidusus). Lk 85, ülesanded 6­11.
Ülesanne 4. Puu tippude astmed on 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 4 ja x. Leida x. Lahendus. Puul on 12 tippu, tipuastmete summa on 19 + x. Teiselt poolt on tipuastmete summa valemi S = 2(n - 1) põhjal 2 · (12 - 1) = 22. Seega 19 + x = 22, millest x = 3. Materjal õpikus. Lk 64 ( teoreem 2). Lk 74, ülesanded 4­8. Ülesanne 5. Teha kindlaks, kas järgmine positiivsete täisarvude hulgal mää on ekvivalents. Lahendus. Kontrollime ekvivalentsi omaduste kehtivust.
· Relatsioon on refleksiivne, sest iga positiivse täisarvu x korral kehtib x2 x = xx2 , st (x, x) R.
· Relatsioon on sümmeetriline, sest kui x2 y = xy 2 , siis ka y 2x = yx2 (need kaks võrdust on teineteisega samaväärsed), st kui (x, y) R, siis ka (y, x) R.
· Relatsioon on transitiivne, sest kui x2 y = xy 2 ja y 2z = yz 2 , siis nende võrduste korrutamisel saame x2 y 3z = xy 3 z 2 , millest võime järeldada, et x2 z = xz 2 , sest y 3 on eelduse kohaselt positiivne täisarv (st nullist erinev). Järelikult on ka transitiivsuse tingimus täidetud: kui (x, y) R ja (y, z) R, siis ka (x, z) R.
Seega see relatsioon on ekvivalents. Materjal õpikus. Lk 90­92 (ekvivalentsirelatsioon). Lk 94­95, ülesanded 5­10, 19­24. Kontrolltöö lahendused Diskreetsed struktuurid 3. variant Ülesanne 1. Kirjanduskriitikute kongressil tuleb kritiseerimisele 7 novelli, 7 romaani, 7 luulekogumikku ja 7 naljakogumikku. Selleks, et Toomas saaks kongressil kriitikuna osaleda, peab ta läbi lugema täpselt 10 teost, sealjuu- res igast zanrist vähemalt 2 teost. Mitmel viisil on Toomasel võimalik seda tingimust täita (raamatute lugemise järjekord pole oluline)? Lahendus. Kui Toomas loeb ühest liigist 4 teost ja ülejäänutest igaühest 2, siis selle liigi valikuks, millest ta loeb 4 teost, on 4 võimalust ja teoste endi valikuks 74 võimalust. Kolmest ülejäänud liigist on igaühe puhul kahe teose valimiseks 72 võimalust. Et kõigil nendel valikutel on võimaluste arvud üks- teisest sõltumatud, siis korrutamisreegli põhjal saab sel juhul teoseid valida 3 4 · 74 · 72 = 1296540 viisil. Kui Toomas loeb kahest liigist kummastki 3 teost ja ülejäänud kahest liigist kummasti 2 teost, siis nende liikide valikuks, millest ta loeb 3 teost, on 42 võimalust. Teoste endi valikuks on 3 valitava teosega liikide puhul 7 3 võimalust, 2 valitava teosega liikide puhul aga 72 võimalust. Siin on 2 2 võimalusi seega 42 · 73 · 72 = 3241350. Sellega on kõik teoste valikuviisid ammendatud, võimalusi on liitmisreegli põhjal kokku 1296540 + 3241350 = 4537890. Materjal õpikus. Lk 14 (kombinatsioonid). Lk 19 (korrutamis- ja liitmis- reegel). Lk 22, ülesanded 21­23. Lk 21, ülesanne 15. Ülesanne 2. Kevadine õhutemperatuur muutub nii, et kahe järjestikuse päe- va temperatuuride aritmeetiline keskmine võrdub alati neile vahetult eelne- va päeva temperatuuriga. Vaatlusperioodi esimesel päeval on temperatuur 0 kraadi ja teisel päeval 1 kraad . Leida avaldis, millest on võimalik ainult na- turaalarvu n järgi välja arvutada, milline on õhutemperatuur n-ndal päeval. Lahendus. Olgu An õhutemperatuur n-ndal päeval. Ülesande tingimuste põhjal kehtib seos 12 (An + An-1 ) = An-2 , millest
An = -An-1 + 2An-2 .
Algtingimused on A1 = 0, A2 = 1. Karakteristliku võrrandi q 2 + q - 2 = 0 lahendid on q1 = -2, q2 = 1. Järelikult rekurrentse võrrandi üldlahend on
An = c1 · (-2)n + c2 .
Algtingimuste põhjal saame võrrandisüsteemi
-2c1 + c2 = 0 4c1 + c2 = 1,
mille lahendid on c1 = 16 , c2 = 13 . Õhutemperatuur n-ndal päeval on seega
1 1 1 - (-2)n-1 An = · (-2)n + = . 6 3 3 Materjal õpikus. Lk 36­40 (teist järku rekurrentsete võrrandite lahenda- mine). Ülesanne 3. Leida, mitu erinevat (isomorfismi täpsuseni) aluspuud on järg- mise naabrusmaatriksiga antud graafil. 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 G= 1 1 0 0 0 0 0 1 1 0 0 1 1 0 0 0 1 0
Lahendus. Joonistades välja selle graafi, näeme, et ta koosneb tsüklist 1, 4, 2, 5, 6, mille külge tipus 5 kinnitub rippuv tipp 3. Selle graafi aluspuu saame parajasti siis, kui jätame tsüklist ühe serva ära. Põhimõtteliselt erinevaid viise selle serva ärajätmiseks on 3: jätta ära kas serv 56, serv 61 või serv 14. Ülejäänud servade 42 ja 25 ärajätmine annab vaadeldutega isomorfsed aluspuud (42 ärajätmine on samaväärne 61 ärajätmisega ja 25 ärajätmine 56 ärajätmisega). Materjal õpikus. Lk 71 (graafi aluspuu), lk 65 (tsüklomaatiline arv), lk 66­67 ( teoreemid 3 ja 4). Ülesanne 4. Puu tippudest k tippu on astmega 4, ülejäänud tipud on lehed. Leida puu tippude arv. Lahendus. Olgu x selle puu lehtede arv, tippude koguarv on siis k + x. Ühelt poolt on puu tipuastmete summa 4k + x, teiselt poolt aga valemi S = 2(n - 1) põhjal 2(k + x - 1). Järelikult 4k + x = 2(k + x - 1), millest x = 2k + 2 ning puu tippude arv on k + x = 3k + 2. Materjal õpikus. Lk 64 (teoreem 2). Lk 74, ülesanded 4­8. Ülesanne 5. Teha kindlaks, kas järgmine reaalarvude hulgal mää on mitterange järjestus. Lahendus. Relatsioon ei ole mitterange järjestus, sest ta ei rahulda anti- sümmeetrilisuse omadust: näiteks (3, -3) R ja (-3, 3) R (st 3 | - 3| ja -3 |3|), aga 3 = -3. Materjal õpikus. Lk 92­93 (mitterange ja range järjestus). Lk 94­95, üles- anded 5­10.