Kuna ülesandes oli aga öeldud, et tegemist ei ole lihtahelaga, siis peaks tal olema vähemalt kaks sellist tippu, mis on ühendatud vähemalt kahe erineva lihtahelaga, nagu näiteks järgmisel joonisel. Joonis 2 Jooniselt on näha, et graafi ühest äärmisest tipust pääseb teise kahtepidi: kas läbides kõik alumised servad või läbides ka ülemist tippu. Antud graaf ei ole lihtahel, kuna lihtahel peab läbima kõik graafi servad täpselt 1 kord. Kui ma valin ühest äärest teise liikumiseks alumise tee, jääb mul kaks ülemist serva läbimata. Kui ülemise, siis jääb üks serv allpool läbimata. Selles graafis saan samuti eemaldada ükskõik missuguse äärmise tipu, ilma et graaf kaotaks sidususe. Lisaks saan eemaldada ka ülevalpool oleva tipu, ilma et graaf kaotaks sidususe.
vaheldumisi? 4. Igal poisil on tüdrukute hulgas tüpselt üks sõbranna. Mitu erinevat rivi saab moodustada, kui iga poiss peab seisma oma sõbranna kõrval? 5. Poiste hulgas pole Andrese ja Bruno suhted kõige paremad. Mitmel viisil saab eelmise punkti tingimusel rivi moodustada nii, et need kaks poissi ei seisa rivis kõrval? 2. Turniirid. 1. Defineerida turniir. 2. Tõestada, et igas turniiris leidub suunatud lihtahel, mis läbib kõiki tippe. 3. Tuua näide turniirist, mis pole tugevalt sidus, kuid ühe kaare summa vastupidiseks muutmisel tekib tugevalt sidus turniir. 4. Tõestada, et igas turniiris, mis pole tugevalt sidus, leidub kaar, mille suuna vastupidiseks muutmisel tekib tugevalt sidus turniir. 5. Olgu G turniir, mille iga tipu puhul leidub sinna sisenev ja sealt väljuv kaar. Kas võib väita, et selline turniir on alati tugevalt sidus? 3. Relatsioonid
jääkgraaf Baas: selline minimaalne tippude osahulk, kus selle osahulga tippudest leidub tee selle graafi mistahes tippu (orienteeritud graafis) Elementaarahel: elementaartee orienteerimata graafis Elementaartee: tee, mis ei läbi ühtki graafi tippu üle ühe korra Euleri ahel: läbib täpselt 1 kord kõik orienteerimata graafi kaared, aga ei lõpe oma algustipus. Euleri graaf: (orienteerimata) graaf, mis omab Euleri tsüklit. Euleri kontuur: suletud lihttee Euleri tsükkel: suletud lihtahel Hamiltoni graaf: (orienteerimata) graaf, mis omab Hamiltoni tsüklit Hamiltoni kontuur: läbib täpselt 1 kord kõik orienteeritud graafi tipud ja lõpeb oma algustipus Hamiltoni tsükkel: läbib täpselt 1 kord kõik orienteerimata graafi tipud ja lõpeb oma algustipus Isomorfsus: 2 graafi on isomorfsed, kui neil on sama tippude ja kaarte arv ning need on seatavad üks-ühesesse vastavusse nii, et mõlemas graafis seovad vastavad kaared vastavaid tippe
o Maksimaalne võimalik tipu aste n-tipulises graafis on n-1. Tipuastmete teoreem o Teoreem. Igas graafis on kõigi tippude astmete summa võrdne servade arvu kahekordsega. 32 o Tõestus. Iga serv suurendab oma kummagi otspunkti astet (ja seega ka astmete summat) kahe võrra. o Järeldus. Igas graafis on paaritu astmega tippe paarisarv. 35. Ahel, ahela otstipud ja sisetipud. Lihtahel. Teoreem lihtahelast. Kaugus. [2] Ahel, otstipud, sisetipud, lihtahel o DEF: Ahelaks nimetatakse graafi tippude järjendit v0, v1, …, vk, kus iga kaks järjestikust tippu on servaga ühendatud. o Tipud v0 ja vk on ahela otstipud, ülejäänud tipud on sisetipud. o Ahela servade arvu k nimetatakse ahela pikkuseks. o Ahel võib tippe ja servi sisaldada ka korduvalt. o Kui ahel ei sisalda korduvaid tippe ega servi, nimetatakse teda lihtahelaks. Teoreem lihtahelast
Näide lk 47 (Palm) Tipu aste tipust väljuvate servade arv. Teoreem: Igas graafis on kõigi tippude astmete summa võrdne servade arvu kahekordsega. Järeldus: Igas graafis on paaritu astemga tippe paarisarv. Ahel graafis tippude järjend, kus iga kaks järjestikust tippu on servaga ühendatud (esimene ja viimane on otstipud vahepeal sisetipud). Ahela pikkus on k kui selles on k+1 tippu. Ahel võib läbida mõnda tippu mitu korda. Lihtahel kõik tipud läbitakse üks kord. Tippude u ja v vaheline kaugus - tippude u ja v vahelise lihtahela pikkus Tsükkel ahel mis lõpeb samas tipus kus algab. Sidus graaf iga kahe tipu vahel leidub ahel. Euleri tsükkel tsükkel mis läbib kõik graafi servad täpselt üks kord. (graaf euleri graaf). Teoreem: Graafis leidub Euleri tsükkel parajasti siis, kui graaf on sidus ja tema iga tipu aste on paarisarv.
võrreldes kõigi keerulisemate struktuuridega. Massiivi elemendi väärtuse väljavahetamine (massiivi elemendile uue väärtuse omistamine) on tavaline omistamistehe ja selleks tehtava töö maht (kui element on indeksi järgi juba leitud) ei sõltu massiivi suurusest ega selle mõõtmete arvust. Page 5 Lihtahel (ingl singly linked list) koosneb elementidest, millest igaühes on lisaks rakenduse seisukohalt vajalikele andmetele ka järgmise elemendi aadress. Nii on ahela töötlemisel võimalik liikuda esimeselt elemendilt teisele, teiselt kolmandale ja nii edasi kuni ahela lõpuni. Ahela viimases elemendis on tühiviit, mis annabki märku ahela lõpust. Tavaliselt kasutatakse ahela hoidmiseks viita selle esimesele elemendile. Rohkem
võrreldes kõigi keerulisemate struktuuridega. Massiivi elemendi väärtuse väljavahetamine (massiivi elemendile uue väärtuse omistamine) on tavaline omistamistehe ja selleks tehtava töö maht (kui element on indeksi järgi juba leitud) ei sõltu massiivi suurusest ega selle mõõtmete arvust. Page 5 Lihtahel (ingl singly linked list) koosneb elementidest, millest igaühes on lisaks rakenduse seisukohalt vajalikele andmetele ka järgmise elemendi aadress. Nii on ahela töötlemisel võimalik liikuda esimeselt elemendilt teisele, teiselt kolmandale ja nii edasi kuni ahela lõpuni. Ahela viimases elemendis on tühiviit, mis annabki märku ahela lõpust. Tavaliselt kasutatakse ahela hoidmiseks viita selle esimesele elemendile. Rohkem
summas esinema paarisarv paaritut liidetavat. 33) a. Ahel graafis G on selline tippude järjend v0, v1, ..., vk, kus iga kaks järjestikust tippu on servaga ühendatud. Tippe v0 ja vk nimetatakse ahela otstippudeks, ahela ülejäänud tipud v1, ..., vk-1 on sisetipud. b. Kui kõik ahela tipud on erinevad, siis nimetatakse ahelat lihtahelaks. c. Teoreem. Kui graafis G leidub ahel tipust u tippu v, siis leidub graafis G ka lihtahel tipust u tippu v. c.i. Tõestus. https://moodle.ut.ee/mod/url/view.php?id=107318 lk 52. d. Tippude u ja v vahelise lühima lihtahela pikkust nimetatakse tippude u ja v kauguseks. 34) a. Ahelat, mis lõpeb samas tipus, kus algab, nimetatakse tsükliks. 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
suurusest. Selle operatsiooni ajakulu sõltub tavaliselt massiivi mõõtmete arvust, aga on igal juhul tühine võrreldes kõigi keerulisemate struktuuridega. Page 5 Massiivi elemendi väärtuse väljavahetamine (massiivi elemendile uue väärtuse omistamine) on tavaline omistamistehe ja selleks tehtava töö maht (kui element on indeksi järgi juba leitud) ei sõltu massiivi suurusest ega selle mõõtmete arvust. Page 6 Lihtahel (ingl singly linked list) koosneb elementidest, millest igaühes on lisaks rakenduse seisukohalt vajalikele andmetele ka järgmise elemendi aadress. Nii on ahela töötlemisel võimalik liikuda esimeselt elemendilt teisele, teiselt kolmandale ja nii edasi kuni ahela lõpuni. Ahela viimases elemendis on tühiviit, mis annabki märku ahela lõpust. Tavaliselt kasutatakse ahela hoidmiseks viita selle esimesele elemendile. Rohkem pole vaja, sest esimeselt elemendilt saame liikuda kõigi teisteni
võrdsed Ahelaks nimetatakse graafi tippude järjendit v0, v1, ..., vk (k0), kus iga kaks järjestikust tippu on servaga ühendatud o Tipud v0 ja vk on ahela otstipud o Ülejäänud tipud on ahela sisetipud Teeks nimetatakse ahelat, kus ükski serv ei kordu Lihtahelaks nimetatakse ahelat, kus ükski tipp ega serv ei kordu Teoreem lihtahelast: kui graafis G leidub ahel tipust u tippu v, siis leidub graafis G ka lihtahel tipust u tippu v Tippude u ja v vaheliseks kauguseks nimetatakse tippude u ja v vahelise lühima lihtahela pikkust Kinniseks ahelaks nimetatakse ahelat, mis algab ja lõpeb samas tipus Tsükliks nimetatakse kinnist ahelat, kus on vähemalt üks serv ja ükski serv ei kordu Lihttsükliks nimetatakse tsüklit, kus iga sisetipp esineb ainult ühe korra Teoreem lihtahela ja lihttsükli leidumisest: kui graafi iga tipu aste on
Tee on orienteeritud graafi kaartejärjestus. Lihttee on orienteeritud graafi tee, kus pole korduvaid kaari. Elementaartee on orienteeritud graafi tee, kus see ei läbi ühtegi tippu korduvalt. Graaf on sidus, kui ükskõik millisest tipust saab ükskõik millisesse teisse tippu. Graaf on ühepoolselt sidus, kui leidub tee ühest punktist teise või vastupidi. Ahel on orienteerimata graafi kaartejärjestus. Lihtahel on ahel, mis ei sisalda korduvaid kaari. Elementaarahel ei sisalda ühtegi tippu üle ühe korra. Suletud tee on tee orienteeritud graafil, mis lõppeb alguspunktis. Kontuur on tee mis lõppeb oma alguspunktis ning ei läbi ühtegi tippu korduvalt. Hamiltoni kontuur läbib igat tippu 1 kord orienteeritud graafil. Hamiltoni tsükkel läib kõik tipud 1 kord orienteerimata graafil.
töö ühes sekundis I 2 P R 10 Raivo PÜTSEP ELEKTRIAHELAD ALALISVOOLU LIHTAHELA ARVUTUS Lihtahel - ühe elektrienergia allikaga mittehargnev või hargahel. Lihtahela arvutus seisneb kõikide ahela suuruste määramises, R1 kasutades alalisvoolu seadusi ja reegleid. a ANDMED: LAHENDUS: I1 E = 12 V
töö ühes sekundis I 2 P R 10 Raivo PÜTSEP ELEKTRIAHELAD ALALISVOOLU LIHTAHELA ARVUTUS Lihtahel - ühe elektrienergia allikaga mittehargnev või hargahel. Lihtahela arvutus seisneb kõikide ahela suuruste määramises, R1 kasutades alalisvoolu seadusi ja reegleid. a ANDMED: LAHENDUS: I1 E = 12 V
järgmise kaare algustipuks on eelmise kaare lõpptipp. Lihttee on tee, kus pole korduvaid kaari. Elementaartee on tee, mis ei läbi ühtegi graafi tippu üle ühe korra. 9. Milline graaf on sidus? Milline graaf on ühepoolselt sidus? Orienteeritud graaf on sidus, kui igast tema tipust leidub tee mistahes teise tippu. Orienteeritud graaf on ühepoolselt sidus, kui tema mistahes kahe tipu a ja b korral leidub tee kas tipust a tippu b või tipust b tippu a. 10. Mis on ahel? Mis on lihtahel? Mis on elementaarahel? Orienteerimata graafi korral nimetatakse teele vastavat kaartejärjestust ahelaks. Orienteerimata graafi lihtahelale vastab orienteeritud graafi lihttee ja elementaarahelale vastab elementaartee. 11. Mis on suletud tee? Mis on kontuur? Mis on tsükkel? Suletud tee on tee orienteeritud graafil, mis lõppeb oma algustipus. Kontuur on suletud elementaartee orienteeritud graafil. Tsükkel on orienteerimata graafi suletud elementaarahel. 12
Orienteeritud graafid e. o-graafid- Graafi servade hulk E(G) koosneb suunatud servadest e. kaartest, mida on võimalik läbida vaid ühes defineeritud suunas. Sidus graaf- kui graafi mistahes tipust A leidub tee graafi mistahes teise tippu B siis öeldase, et tegu on sidusa graafiga. Tipu aste e. valents- graafi tipu aste on selle tippuga seotud servade arv. TEE e. ahel graafis G = (V,E) on servade järjestus tipust x tippu y. LIHTTEE e. lihtahel graafis G on selline tee, milles ei esine korduvaid tippe. KINNINE TEE on tee, kus x0 = xk e. tee lõppeb oma alguspunktis. TSÜKKEL on kinnine lihttee. Tähstsamaid teoreeme: *Suunamata lihtgraafis on alati paarisarv paaritu asmtega tippe. antud tingimus osutub sageli kasulikuks erinevate ülesannete lahendamisel, kus tippude valentside hulga järgi on vaja välja selgitada, kas antud graafi on ka reaalselt võimalik joonistada.
• Tee ehk ahel o Saab graafis leida ühest tipust teise tippu. o Teel on pikkus. o Selline kaarte järgnevus, kus ühe kaare lõpp-punkt on järgmise kaare alguspunktiks. o Kaks tippu v ja u on seotud, kui nende vahel on tee. Kaks tippu on seotud külgnevussuhtega, kui ühest tipust läheb kaar teise tippu • Elementaarahel – ahel, mis läheb igast tipust vaid ühe korra. • Lihtahel – ahel mis läheb igast servast vaid ühe korra. • Tsükkel – ahel, kus algus ja lõpp on samas tipus. • Hamiltoni tsükkel – elementaartsükkel (elementaarahel, mis lõppeb samas tipus), mis läbib kõiki graafi tippe. • Euleri tsükkel – lihttsükkel (lihtahel, mis lõppeb samas tipus), mis läbib kõiki graafi servi ühe korra. • Atsükliline graaf – graaf, kus puudub tsükkel
Passiivsed resistiivsed vooluahelad. SDER 3. loeng 10.02.2011 6 (6) Näiteid mittelineaarsete ahelate graafilise analüüsi kohta [3] Joonis 5.7. Mittelineaarahelaid on lihtsam analüüsida graafiliste lahenduste abil [3]. Elektroonika alused. Teema 5 Mõned elektrotehnika ja süsteemitehnika põhimõisted. Passiivsed resistiivsed vooluahelad. SDER 3. loeng 10.02.2011 7 (7) 5.1.4. Liht- ja liitahelad Lihtahel on ühe elektromotoorjõu allikaga ahel, mis võib omakorda olla kas mittehargnev või hargnev ahel (hargahel). Liitahel on kahe või enama elektromotoorjõu allikaga hargnev ahel. 5.1.5. Mittehargnevad vooluahelad. Jadaühendus Mittehargneva vooluahela elemendid on ühendatud järjestikku e. jadamisi. Mittehargnevas vooluahelas on kõigis selle osades voolutugevus ühesuurune. Elektriahela mistahes kinnises kontuuris toimivate elektromotoorjõudude algebraline
Suletud tee on tee orienteeritud graafil, mis lõppeb oma algustipus. Kontuur on suletud elementaartee orienteeritud graafil. Hamiltoni kontuur läbib (täpselt 1 kord) kõik orienteeritud graafi tipud (ja lõpeb algustipus). Orienteerimata graafi suletud elementaarahel on tsükkel. Hamiltoni tsükkel läbib (täpselt 1 kord) kõik orienteerimata graafi tipud. Euleri kontuur on suletud lihttee, mis läbib (1 kord) kõik orienteeritud graafi kaared. Euleri tsükkel on suletud lihtahel, mis läbib (1 kord) kõik orienteerimata graafi kaared. Euleri ahel läbib ka 1 kord kõik orienteerimata graafi kaared, kuid ei lõpe oma algustipus. Sidus graaf on Euleri graaf, kui tema kõikide tippude aste on paarisarvuline. Graafi 𝐺 = (𝑇, 𝐾) jääkgraaf on graaf 𝑄 = (𝑇, 𝐵), kus 𝐵 ⊂ 𝐾. Seega saadakse jääkgraaf osade kaarte ärajätmisega, kusjuures kõik tipud säilivad. Graafi -..- taandatud graaf on graaf 𝑄 = (𝐷, 𝐵), kus on
public void add(Object o) { return true; add(size, o); } } else return false; public boolean isEmpty() { } return size == 0; } } List lihtahelana(ingl. k. Linked list) - Ahelloend · Lihtahel koosneb üksteisega seotud tippudest · Iga tipu juurest on viit järgmisele tipule 12. Loeng Isetehtud list, Andmestruktuurid, Eksamiülesanded Magasin, järjekord Magasin - elemente lisatakse lõppu ja kätte saab elemente ainult lõpust 1. elemendi lisamine (push); 2. elemendi eemaldamine (pop); 3. LIFO Last In, First Out Järjekord - elemente lisatakse lõppu ja kätte saab elemente ainult algusest 1. elemendi lisamine (enqueue); 2
annaabi.ee 
