järjestatud paarid Vastavus on hulk, mis koosneb järjestatud paaridest Vastavuse W pöördvastavus on selline vastavus, mis seab vastavuse W sihthulga elementidele vastavaks tema lähtehulga elemente Milliseid tehteid saab teha vastavustega? Kompositsioon Funktsioon on kõikjal määratud ühene vastavus Üks-ühene funktsioon on injektsioon Kõikjale määratud funktsioon on sürjektsioon Kõikjale määratud üks-ühene funktsioon on bijektsioon Kui funktsioon on samaaegselt nii sürjektsioon kui ka injektsioon, siis on ta ka bijektsioon Millised võivad olla relatsiooni esitusviisid? Naabrusmaatriks, orienteeritud graaf, järjestatud paaride hulk Igal relatsioonil peab relatsioonikriteerium olema alati olemas? Väär Millised relatsioonide omadused on olemas ? Antitransitiivsus, Antirefleksiivsus, Refleksiivsus, Antisümmeetria, Sümmeetria, Transitiivsus Millised omadused graafil? Antirefleksiivsus Antisümmeetria
astendamine jagamine lahutamine Küsimus 7 Õige - Hinne 2,00 / 2,00 vali õiged mõisted : Funktsioon on määratud vastavus kõikjal ühene Küsimus 8 Õige - Hinne 1,00 / 1,00 vali õiged funktsioonide liigid (nimed) : injektsioon üks-ühene funktsioon on : bijektsioon kõikjale määratud üks-ühene funktsioon on : sürjektsioon kõikjale määratud funktsioon on : Küsimus 9 Õige - Hinne 1,00 / 1,00 Kui funktsioon on samaaegselt nii sürjektsioon kui ka injektsioon, siis on ta ka . . . sisesta õige termin : Vastus: bijektsioon Küsimus 10 Õige - Hinne 1,00 / 1,00 Millised võivad olla relatsiooni esitusviisid ? vali kõik õiged : Vali üks või enam:
Küsimus 7 Õige Hindepunkte 2,00/2,00 vali õiged mõisted : Funktsioon on kõikjal määratud ühene vastavus Küsimus 8 Õige Hindepunkte 1,00/1,00 vali õiged funktsioonide liigid (nimed) : üks-ühene funktsioon on : injektsioon kõikjale määratud funktsioon on : sürjektsioon kõikjale määratud üks-ühene funktsioon on : bijektsioon Küsimus 9 Õige Hindepunkte 1,00/1,00 Kui funktsioon on samaaegselt nii sürjektsioon kui ka injektsioon, siis on ta ka . . . sisesta õige termin : Vastus: bijektsioon Küsimus 10 Õige Hindepunkte 1,00/1,00 Millised võivad olla relatsiooni esitusviisid ? vali kõik õiged :
väärtused erinevad: 12 (1)(2); - sürjektiivseks ehk pealekujutuseks, kui iga jaoks leidub selline , et () = ; - bijektiivseks, kui funktsioon on injektiivne ja sürjektiivne. Injektiivsus tähendab, et ühelgi hulga elemendil pole rohkem kui üks originaal. Sürjektiivsus tähendab, et igal hulga elemendil leidub vähemalt üks originaal. Bijektiivsus tähendab, et igal hulga elemendil leidub täpselt üks originaal. Bijektsioon kui üksühene vastavus Hulgateooria seisukohalt on funktsioonid : paaride hulgad ={(,) | =()}. Bijektiivne funktsioon : on siis selline paaride hulk, kus 1. iga jaoks leidub parajasti üks paar, milles on esimene komponent, 2. iga jaoks leidub parajasti üks paar, milles on teine komponent. Bijektiivseid funktsioone nimetatakse ka üksühesteks vastavusteks hulkade ja elementide vahel (või lihtsalt hulkade ja vahel). Näiteid üksüheste vastavuste kohta. 1
Question 9 Kui funktsioon on samaaegselt nii sürjektsioon kui ka Correct injektsioon, siis on ta ka . . . Mark 1.00 out of sisesta õige termin : 1.00 Answer: bijektsioon Question 10 Millised võivad olla relatsiooni esitusviisid ? Correct vali kõik õiged : Mark 1.00 out of 1.00 Select one or more: naabrusmaatriks
2. ¿ A B¿ A+¿ B-¿ A B¿ ¿ 3. ¿ A =¿ A-¿ A B¿ 4. ¿ A × B¿A·B¿ TÕESTUS Loengu videos Definitsioon Hulka X nimetatakse lõpmatuks, kui ta ei ole lõplik. Näide: Hulgad N , Z ,Q , R ja C on kõik lõpmatud hulgad. Märkus. Lõpmatu hulga võimsuse defineerime hiljem, kui oleme tutvunud ekvivalentsusseose mõistega. Definitsioon Hulgad X ja Y on ekvivalentsed ehk sama võimsusega, kui leidub bijektsioon f :X Y . Asjaolu, et hulgad X ja Y on ekvivalentsed tähistatakse tavaliselt kas X Y või ¿ X¿Y ¿ . Näide: Kaks lõplikku hulka X ja Y on ekvivalentsed parajasti siis, kui nende elementide arvud on võrdsed. Näide: Hulgad N ja Y ={2,4,6,... } on ekvivalentsed. Bijektsiooniks f : N Y on f (n)=2 n iga nN korral. Teisisõnu, paarisarve on täpselt sama palju kui naturaalarve. Näide: Hulga N
funktsioonil gf : A C leidub pöördfunktsioon ja (gf )-1 = f -1g-1. Hulga karakteristlik funktsioon Olgu X universaalne hulk. Hulga A X karakteristlikuks funktsiooniks nimetatakse funktsiooni XA : X {0, 1}, kus XA(x)= 1, kui xA ; 0, kui x A. Lõpliku hulga võimsus on tema elementide arv. Lõpmatute hulkade võimsuste võrdlemiseks kasutatakse hulkade üksühese vastavuse mõistet. Ütleme, et hulgad A ja B on sama võimsusega, kui leidub bijektsioon f : A B. Tähis: A B, öeldakse ka, et hulgad A ja B on ekvivalentsed. Kehtivad omadused: · refleksiivsus: A A · sümmeetrilisus: kui A B, siis B A · transitiivsus: kui A B ja B C, siis A C Hulka, mis on sama võimsusega nagu naturaalarvude hulk, nimetatakse loenduvaks hulgaks. · Järelikult on loenduvad parajasti need hulgad, mis on esitatavad jadana {a0, a1, a2, . . .}. · Iga lõpmatu hulk sisaldab loenduvat osahulka.
104493 IAPB21 Nii parem- kui vasakpoolsel graafil on olemas 2 tippu, mille aste on 3, ja 4 tippu, mille aste on 2. Nüüd vaatan, kuidas on tipud omavahel ühendatud. Kaks märgendamata graafi G ja H on isemorfsed, kui nende tipuhulkade vahel leidub selline bijektsioon f: V(G) -> V(H), et tipud u ja v on naabrid graafis G parajasti siis, kui tipud f(u) ja f(v) on naabrid graafis H. Alustan tippude naabrussuhete uurimist tippudest, mille aste on 3. Vasakpoolses graafis on tipud astmega 3 ühendatud omavahel ühe servaga ja mõlemad tipud veel kahe tipuga, mille aste on 2. Kuid parempoolses graafis pole tipud astmega 3 omavahel servaga ühendatud ning mõlemad tipud astmega 3 on ühendatud kolme tipuga, mille aste on 2.
Ühene – lähtehulga elemendid on seotud ühe sihthulga elemendiga. Üks-ühene – üks lähtehulk on seotud ainult ühe sihthulgaga. Funktsioon on kõikjal määratud ühene vastavus. Funktsioon on osaliselt määratud, kui on mitte kõik lähtehulga elemendid on seotud. Sürjektsioon on kõikjale määratud funktsioon. Injektsioon on üks-ühene määratud funktsioon. Bijektsioon on kõikjale üks-ühene funktsioon. Binaarne relatsioon on vastavuse erijuht, kus lähethulk ja sihthulk on sama hulk. Binaarsuhte alushulk on hulk, mille relatsioon on määratud. Relatsioonikriteerium on binaarsuhet moodustav reegel. Relatsiooni saab esitada järjestatud paaride hulgana, naarbusmaatriksiga, graafina. Relatsiooni omadused, refkelsiivne, antiref, sümmeetriline, antisüm, transitiivne, antitrans.
14. Mis on funktsioon? Funktsioon on kõikjal määratud ühene vastavus. 15. Milline funktsioon on osaliselt määratud? Funktsioon on osaliselt määratud, kui lähtehulgas leidub vastavuses mitteosalevaid elemente. 16. Mis on pealekujutus? Pealekujutuseks nimetatakse sürjektsiooni. 17. Mis on sürjektsioon? Sürjektsioon on kõikjale määratud funktsioon. 18. Mis on injektsioon? Injektsioon on üks-ühene funktsioon. 19. Mis on bijektsioon? Bijektsioon on kõikjale määratud üks-ühene funktsioon. Bijektsioon on samaaegselt nii sürjektsioon kui ka injektsioon. 20. Mis järeldub bijektsiooni korral lähtehulga ja sihthulga võimsuste kohta? Bijektsiooni korral on lähtehulga ja sihthulga võimsused võrdsed. 21. Mis on binaarne relatsioon? Binaarne relatsioon on vastavuse erijuht, kus nii lähtehulk kui ka sihthulk on üks ja sama hulk. 22. Mis on binaarsuhte alushulk
b. Tsüklit, mis ei läbi ühtegi tippu kaks korda, nimetatakse lihttsükliks. c. Teoreem. Kui graafi iga tipu aste on vähemalt 2, siis leidub graafis lihtahel pikkusega l ja lihttsükkel pikkusega vähemalt + 1. c.i. Tõestus. https://moodle.ut.ee/mod/url/view.php?id=107318 lk 52 53 35) a. Graafe G = (V, E) ja G' = (V', E') nimetatakse isomorfseteks, kui leidub niisugune bijektsioon : V V', et graafis G on serv tippude u ja v vahel parajasti juhul, mil graafis G' on serv tippude (u) ja (v) vahel. b. Kahe graafi isomorfsuse näitamiseks tuleb mõlemas graafis tipud nummerdada nii, et samade numbritega tipud on kas mõlemas graafis servaga ühendatud või mõlemas ühendamata. c. Kahe graafi isomorfsuse ümberlükkamiseks piisab vähemalt ühe invariandi erinevuse väljatoomisest. 36) a
komponenti, siis kehtivad võrratused n-k <= m <= 2 o Järeldus: kui n-tipulisel graafil on vähem kui n-1 serva, siis see graaf on mittesidus (n-k )(n-k +1) o Järeldus: kui n-tipulisel graafil on rohkem kui 2 serva, siis see graaf on sidus Graafe G=(V,E) ja G1=(V1, E1) nimetatakse isomorfseteks, kui leidub bijektsioon f: V->V1 nii, et graafis G on serv tippude u ja v vahel parajasti siis, kui graafis G1 on serv tippude f(u) ja f(v) vahel o Näitamaks, et kaks graafi ei ole isomorfsed: näitame, et kas tippude arv, servade arv, tipuastmete järjend, lühima tsükli pikkus või erinevate lihtahelate arv kahe tipu vahel on erinevad o Neid suurusi nimetatakse invariantideks Tsüklit, mis sisaldab kõiki graafi tippe ja läbib graafi kõik servad täpselt üks
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 5759 (graafide isomorfism). Lk 62, ülesanded 3741. Ü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
c 6 — täielikult määratud funktsioon? 3 — sürjektsioon? d — injektsioon? 1 2 — bijektsioon? injektsioon Kui ϕ : A → B on injektsioon , siis | A | ≤ | B | BINAARSUHTED (KAHENDSUHTED) e. RELATSIOONID Binaarne relatsioon on vastavuse erijuht, kus nii lähtehulk kui ka Kõikjale määratud üks-ühene funktsioon on bijektsioon: sihthulk on üks ja sama hulk: ( "Relatsioon hulgal M" )
Vastavus AxB on üks-ühene, kui -1 {
-1 {
Tõestus. Paneme tähele, et iga fikseeritud m ∈ N puhul on hulk {n ∈ N | n + m ∈ N} induktiivne (selgitada!)z, lause 1.9 põhjal langeb ta hulgaga N kokku. Seega n + m ∈ N suvaliste m ∈ N ja n ∈ N korral. Korrutise jaoks on tõestus analoogiline (iseseisvalt!)z. Arvestades omadust 1.11, on N kui järjestatud korpuse F naturaalarvude hulga tähis, õigustatud. Nimelt, defineerides kujutuse ϕ : N → N ⊆ F võrdustega ϕ(∅) = 1 ja ϕ(S(n)) = n + 1, on kujutus ϕ bijektsioon, kooskõlas tehete ja järjestusega. See kujutus võimaldab samastada alapeatükis 1.2.1 defineeritud hulga N ja igas järjestatud korpuses leitava kõigi induktiivsete hulkade ühisosa N. Omadus 1.12 Hulga N vähim element on 1. Tõestus. Hulk {n ∈ N : n > 1} on induktiivne, seega sisaldab kõigi induktiivsete hulkade ühisosa N. Järelikult iga n ∈ N korral kehtib n > 1. Lemma 1.13 Kui m ∈ N ja m 6= 1, siis m − 1 ∈ N.
annaabi.ee 
