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 5759 (graafide isomorfism). Lk 62, ülesanded 3741. Ülesanne 4
IAPB21 Korrutan pooled 8-ga läbi. 8 15 8 12 (J 17) Y (X ) Nüüd leian y-i. 2 11 + 4 (J 17) 22 + 4 (J 17) -18 (J 17) Y (X ) Kontroll: 1) vp = 2 11 + 16 4 (J 17) pp = 4 (J 17); pp = vp 2) vp = 5 11 - 5 16 9 (J 17); pp = 9 (J 17); pp = vp Seega on leitud lahendid õiged. Vastus: 11 (J 17) ja 16 (J 17) ÜLESANNE 4. Eeldan graafide joonistamisel, et tegemist on märgendamata graafiga ja samuti et tegemist ei ole multigraafiga, st kaks tippu ei saa olla omavahel seotud rohkem kui ühe kaarega. Samuti eeldan, et tipp ei saa olla iseendaga ühendatud. Iga tipu juurde märgin ka selle tipu astme, et eri graafe oleks lihtsam üksteisest eristada. 1) Alustan võimalusest, kui mul pole ühtegi serva ehk ükski graafi tipp pole teisega ühendatud.
R3 = {(x, y): x on yi-i vanavanaisa mööda isaliini} c. Näide 2. Olgu X = ja R {(x, y): |x y| 3}. Siis R3 = {(x, y): |x y| 3n} d. Teoreem relatsiooni astmest Rn. Olgu R hulgal X defineeritud binaarne relatsioon, n 1. Paar (x, y) kuulub astmesse Rn parajasti siis, kui hulgas X leiduvad elemendid z0, z1, ..., zn nii, et z0 = x, zn = y ja iga i = 0, 1, ..., n 1 korral (zi, zi+1) R. Graafide terminites tähendab teoreem: (x, y) Rn relatsiooni R graafis leidub selline suunatud ahel pikkusega n, mille esimene element on x ja viimane element y. e. **Tõestus. https://moodle.ut.ee/mod/url/view.php?id=107318 lk 101 102. 29) a. Def. Relatsiooni R sulundiks vaadeldava omaduse suhtes nimetatakse (sisalduvuse mõttes) vähimat relatsiooni, mis sisaldab R ja millel on vaadeldav omadus. b
33 Lihttsükkel o Kui tsükkel ei läbi ühtegi tippu ega serva kaks korda, siis nimetatakse teda lihttsükliks. Teoreem lihtahela ja lihttsükli leidumisest o Teoreem. Kui graafi iga tipu aste on vähemalt l ≥ 2, siis leidub graafis lihtahel pikkusega l ja lihttsükkel pikkusega vähemalt l + 1. o Järeldus. Igas graafis, milles on servi vähemalt sama palju kui tippe, leidub tsükkel. 37. Graafide isomorfism. Isomorfsuse näitamine ja ümberlükkamine. [2] Graafide isomorfism o DEF: Graafe G = (V, E) ja G’ = (V’, E’) nimetatakse isomorfseteks, kui leidub bijektiivne funktsioon f: V → V’ nii, et graafis G on serv tippude u ja v vahel parajasti siis, kui graafis G’ on serv tippude f(u) ja f(v) vahel. o Isomorfseid graafe võib lugeda matemaatilises mõttes samadeks Isomorfsuse näitamine ja ümberlükkamine
omavad ühesugust struktuuri vaatamata erinevale välimusele. Homomorfism on kujutus ühest struktuurist teise sama tüüpi struktuuri, kus säilivad vaadeldavad seosed. Invariant on objekti omadus, mis jääb vaadeldavate teisenduste korral muutumatuks. Invariantsed on näiteks liikumisseadused elementaarosakeste teooriates, klassikalises mehaanikas. Kui teisendus ei muuda ühtki objekti omadust, siis on tegu invariantide süsteemiga ja see on täielik invariant. Nt. isomorfsete graafide täielik invariant on nende ühine struktuur. Variant on invariandi vastand, see on teisend, keeleüksuse (keelendi) esinemiskuju. 7. ,,Tähestik" ja ,,grammatika". Sünkroonia ja diakroonia. Tähestik ja grammatika on omavahel süntaktilises seoses. Omamoodi on ,,tähestik" ehk märgid ja ,,grammatika" ehk märkide loogiline järjestus mistahes märgisüsteemil, näiteks noodikirjal. Sünkroonia printsiipi tutvustas Saussure, sellest sai üks strukturalismi põhimõtteid. Selle kohaselt
[23]. Kord- ja algarvud. Algarvude jaotus, algarvulisuse kontroll, Eratosthenese sõel. [24]. Naturaalarvude kanooniline kuju. Suurim ühistegur ja vähim ühiskordne. [25]. Fermat teoreem. Pseudoalgarvud ja Carmichaeli arvud. [26]. Eukleidese algoritm. [27]. Lineaarsed diofantilised võrrandid. [28]. Täisarvude kongruentsid. Kongruentsi omadusi. [29]. Moodularitmeetika. [30]. Algarvulisuse Fermat` test. Miller-Rabini test. [31]. Graafid ja graafide omadused. Ahelad ja tsüklid graafis. [32]. Euleri graafid. Hamiltoni tsüklid. [33]. Puud. Puude omadused. [34]. Graafi vähima kaaluga aluspuud. [35]. Märgendatud puud. Puude esitamine arvuti mälus. [36]. Prüferi kood. Märgendatud puude loendamine. Cayley teoreem. [37]. Märgendamata puude arv. [38]. Kooskõlad graafis. Berge'i teoreem. [39]. Kooskõlad kahealuselises graafis. Halli teoreem. [40]. Tasandiline graaf. Euleri valem: seos tasandilise graafi tippude, servade ja tahkude
Omadused - Servade lõikumispunktid ehk graafi tipud - Servad ehk ühendused - Alamgraafid ehk eraldiseisvad hulgad - Ruumiosa (pale või regioon) servade vahel või väljaspool neid - Planaarsed ühendused kõik lõikumised on tasandil - Mitteplanaarne ristumised on viidud mitmesse tasapinda - Graafide isomorfus kahe graafi vahel on võimalik määrata üks-ühene vastavus kõigi servade ja tippude vahel - Võib esineda suletud ringe ja tsükleid, kui ei esine, on tegu puuga. Suunatud atsükliline graaf (kanalisatsioon); Tsükliline graaf (transport) - Tipu järk sinna suubuvate servade arv - Euleri võrrand V+F=E+S. V-tippude arv; F-palede arv servade vahel;
baas on selline minimaalne tippude osahulk, kus selle osahulga tippudest leidub tee selle graafi mistahes teise tipuni. 22. Mis on graafi sõltumatute tippude hulk? Kas ta on suurim või väikseim võimalik hulk? Graafi sõltumatute tippude hulk on graafi tippude selline osahulk, kus suvalised 2 tippu selles hulgas pole graafil kaarega seotud. 23. Millised graafid on isomorfsed? Graafid on isomorfsed, kui neil on samapalju tippe ja samapalju kaari ning nende graafide nii tipud kui ka kaared on seatavad üks-ühesesse vastavusse selliselt, et mõlemas graafis seovad vastavad kaared vastavaid tippe. 24. Mille poolest võivad isomorfsed graafid teineteisest erineda? Isomorfsed graafid võivad teineteisest erineda tippude ja kaarte tähistuse ning paigutuse pooles. 25. Mis on pöördgraaf? Orienteerimata graafi pöördgraaf on samade tippudega orienteerimata graaf, mis sisaldab kaari nende tippude vahel, kus esialgses graafis pole kaart ja vastupidi
vaadeldavad seosed. Isomorfism on üks homoformismi vorm. Invariant on objekti omadus, mis jääb vaadeldavate teisenduste korral muutumatuks. Invariantsed on näiteks liikumisseadused elementaarosakeste teooriates, klassikalises mehaanikas. Kui teisendus ei muuda ühtki objekti omadust, siis on tegu invariantide 6 süsteemiga ja see on täielik invariant. Nt. isomorfsete graafide täielik invariant on nende ühine struktuur. Variant on invariandi vastand, see on teisend, keeleüksuse (keelendi) esinemiskuju. Variant – mitu tähendust, mitu varianti (hallivatimees, haavikuemand-jänes) Invariant – üks mõiste, nt ema Saussure räägib, et tuleb hakata uurima keelt, mitte kõnet. Võiks keelt sügavamalt uurida, siis tekib strukturalism jne. Jagab keele pisikestemaks üksusteks. Homomorfism – ratas ja BMW
Marsruutimise Iga kiht lisab saadud andmetele juurde kindla päise ja edastab tulemuse temast madalamal olevale kihile. Vastuvõtmisel võtab iga kiht saadakse kliendist palju teada. kujutamiseks kasutatakse graafe. Graafid kujutavad ruutereid ja graafide servad on füüsilised ühendused. ,,Hea" rada tähendab enamasti talle määratud päise maha. 14.FTP odavat rada. Marsruutimise elemendid: sammude arv, maksumus, viivitus, läbilaskevõime Strateegiad: fixed routing on reguleeritud, 5
Lõpmatu hulga võimsus leitakse, seades tema elemendid bijektiivsesse vastavusse (üks- ühesesse) mõne tuntud võimsusega hulga (näiteks naturaalarvude hulga) elementidega. 4. Graafid. Puude esitused. Programmide esitamine puuna Mittejärjestatud ja mitteorienteeritud graaf on paar G = (A,R), kus A on tippude hulk ja kaarte hulk R on seos hulgal A. Graafi saab esitada paaride hulgana (A + R analüütiliselt, või predikaadina) või joonisena. Graafide võrdsus: Graafid G1 = (A1, R1) ja G1 = (A2, R2) on võrdsed ehk isomorfsed, kui leidub selline bijektiivne kujutus f: A1 A2 nii, et aR1b = f(a)R2f(b) Kui igale tipule a G1-st leidub tipp b G2-st, millele saab vastavusse seada samade tippude kaared ja kõik G2 tipud saavad ka kaetud. Kui kaar R1 järgi on esimese graafi tippude vahel, siis on see ka samade teise graafi tippude vahel ja kui seda pole, pole kummaski. Graafi märgendus:
identifikaatorit, mis ei ole unikaalsed globaalses mõttes, vaid igas ruuteris hoitakse vastavuste tabelit, mille järgi saab teada, kuhu antud identifikaatoriga pakett on vaja edasi saata. (Tee algpunktist lõpppunkti on paljuski nagu telefonivõrgu puhul.) 27. MARSUUTIMINE ==> Marsruutimise eesmärk on leida hea tee saatjast vastuvõtjasse, mis tähendab üldjuhul kõige kiiremat teed. /// Marsruutimise kujutamiseks kasutatakse graafe. Graafid kujutavad ruutereid ja graafide servad on füüsilised ühendused. // ,,Hea" rada tähendab enamasti odavat rada. // Marsruutimise elemendid: sammude arv, maksumus, viivitus, läbilaskevõime. //// ==> Kas globaalse või hajutatud infoga: Globaalne: kõik ruuterid omavad infot topoloogia, ühenduskulude kohta (Link state algoritmid). // Hajutatud: ruuter teab oma naabreid, ühenduskulu naabriteni; kogu tee maksumuse arvutamine iteratiivne, vahetatakse infot naabrite vahel (Distance vector algoritmid).
mõttes, vaid igas ruuteris hoitakse vastavuste tabelit, mille järgi saab teada, kuhu antud identifikaatoriga pakett on vaja edasi saata. (Tee algpunktist lõpppunkti on paljuski nagu telefonivõrgu puhul.) 27. MARSUUTIMINE ==> Marsruutimise eesmärk on leida hea tee saatjast vastuvõtjasse, mis tähendab üldjuhul kõige kiiremat teed. /// Marsruutimise kujutamiseks kasutatakse graafe. Graafid kujutavad ruutereid ja graafide servad on füüsilised ühendused. // „Hea“ rada tähendab enamasti odavat rada. // Marsruutimise elemendid: sammude arv, maksumus, viivitus, läbilaskevõime. //// ==> Kas globaalse või hajutatud infoga: Globaalne: kõik ruuterid omavad infot topoloogia, ühenduskulude kohta (Link state algoritmid). // Hajutatud: ruuter teab oma naabreid, ühenduskulu naabriteni; kogu tee maksumuse arvutamine iteratiivne, vahetatakse infot naabrite vahel (Distance vector algoritmid).
annaabi.ee 
