18. lekcija Kombinatorikas un grafu teorijas elementi PDF

Kombinatorikas un grafu teorijas elementi 18. lekcija Kursa saturs 1. Skaitīšanas kombinatorikas elementi un kombinatoriskās struktūras 2. Kārtošanas un meklēšanas algoritmi, citu algoritmu izstrāde 3. Matemātiskās spēles 4. Grafu teorijas elementi Grafa jēdziens un pam...

Kombinatorikas un grafu teorijas elementi 18. lekcija Kursa saturs 1. Skaitīšanas kombinatorikas elementi un kombinatoriskās struktūras 2. Kārtošanas un meklēšanas algoritmi, citu algoritmu izstrāde 3. Matemātiskās spēles 4. Grafu teorijas elementi Grafa jēdziens un pamatdefinīcijas. Grafu izomorfisms. Lemma par rokasspiedieniem Maršruti, grafu sakarīgums, koki. Cikli, Eilera cikls un ķēde Divdaļīgie grafi. Pilni grafi. Planāri grafi, Eilera formula Turnīri. Grīnberga teorēma. Kuratovska-Pontrjagina teorēma. Četru krāsu problēma. Interpretācijas ar grafu palīdzību Prasības kredītpunktu iegūšanai 1. Kombinatorikas elementi (20%) 2. Kārtošanas-meklēšanas algoritmi 3. Matemātiskās spēles (2.+3. 20%) 4. Grafu teorijas elementi (20%) Eksāmens (40%) Grafu teorija Grafa jēdziens un pamatdefinīcijas U Starp deviņām planētām ir kosmiskie sakari. Kosmosa kuģi lido pa šādiem maršrutiem: Zeme – Merkurs, Marss – Urāns, Plutons – Venēra, Jupiters – Marss, Zeme – Plutons, Saturns – Jupiters, Plutons – Merkurs, Neptūns – Saturns, Merkurs – Venēra, Urāns – Neptūns. Vai ar kosmosa kuģi var nokļūt no Zemes uz Marsu? Sasniedzamais rezultāts Zina pamatjēdzienus (vienkāršs neorientēts grafs, šķautnes galapunkti, virsotne incidenta šķautnei, blakusvirsotnes, blakusšķautnes, vienkāršs orientēts grafs, cilpa, multigrafs, izomorfi grafi, virsotnes pakāpe, apakšgrafs) un Lemmu par rokasspiedieniem Risina uzdevumus, izmantojot grafu teorijas pamatelementus. Nosaka virsotņu pakāpes, izomorfus grafus, apakšgrafus. Lieto Lemmu par rokasspiedieniem un tās sekas  1735. gads Kēnigsberga Leonards Eilers (1707-1783) 1852. gads  1878. g. angļu matemātiķis J.J.Silvester pirmo reizi lieto terminu «grafs» 1936.g. izdoto ungāru matemātiķa D.Kēniga grāmatu uzskata par pirmo nopietno grāmatu grafu teorijā, jo tajā ir apkopoti ļoti daudzi tā laika rezultāti (258 lpp.) 1959. g. pirmais latviešu matemātiķa J.Bārzdiņa zinātniskais raksts šajā nozarē Pamatjēdzieni Virsotne Šķautne Grafs Virsotnes – jēdzieni, šķautnes – saiknes. D Par vienkāršu neorientētu grafu sauc pāri 𝐺 = (𝑉, 𝐸), kur 𝑉 – grafa virsotņu kopa, 𝑉 ≠ ∅, 𝑉 – galīga (pretējā gadījumā saka, ka grafs ir bezgalīgs); 𝐸 – grafa šķautņu kopa; 𝐸 sastāv no kopas 𝑉 elementu nesakārtotiem pāriem (nav orientācijas) (𝐸 ⊂ 𝑉 × 𝑉); šķautnes savieno atšķirīgas virsotnes (t.i., nav cilpas); šķautnes savieno atšķirīgus virsotņu pārus. Piezīme. Apzīmējumi no vārdiem «vertex» un «edge» P Uzrakstīt virsotņu kopu un šķautņu kopu! 𝑉 = 𝑎, 𝑏, 𝑐, 𝑑 𝐸 = { 𝑎, 𝑏 , 𝑎, 𝑑 , 𝑏, 𝑑 , 𝑏, 𝑐 , 𝑐, 𝑑 }} 𝑉 = 4, 𝑉 − virsotņu skaits 𝐸 = 5, 𝐸 − šķautņu skaits Piezīme. Neorientētā grafā vienu un to pašu šķautni var pierakstīt gan {𝑎, 𝑏}, gan {𝑏, 𝑎}. Ievēro! Grafa šķautnes var krustoties arī citos punktos, kas nav grafa virsotnes. D Virsotnes 𝑣1 un 𝑣2 sauksim par šķautnes {𝑣1 , 𝑣2 } galapunktiem. Ja virsotne 𝑣 ir šķautnes 𝑒 galapunkts, tad saka, ka 𝒆 ir incidenta 𝒗 un 𝒗 ir incidenta 𝒆. Divas virsotnes sauc par blakusvirsotnēm, ja tās ir savienotas ar šķautni. Divas šķautnes sauc par blakusšķautnēm, ja tām ir kopīgs galapunkts.  Grafa šķautnes var būt arī sakārtoti virsotņu pāri. Tad tās sauc par orientētām šķautnēm. D Par vienkāršu orientētu grafu sauc pāri 𝐺 = (𝑉, 𝐸), kur 𝑉 – orientēta grafa virsotņu kopa, 𝑉 ≠ ∅; 𝐸 – orientēta grafa šķautņu kopa; 𝐸 sastāv no kopas 𝑉 elementu sakārtotiem pāriem (uz šķautnēm zīmē bultiņas, lai šķautnes (𝑢, 𝑣) un (𝑣, 𝑢) atšķirtu vienu no otras); nav cilpas; starp divām virsotnēm ir ne vairāk kā viena šķautne katrā virzienā. D Triviāls grafs Orientēts grafs ar cilpām Neorientēts grafs ar cilpām Multigrafs Orientēts multigrafs ar cilpām Vienkārši grafi Uzdevumi 1.-11. uzdevums U Kādā ciematā ir trīs mājas 𝐴, 𝐵, 𝐶; ūdens, gāzes un elektrības pieslēgpunkts. Katra māja savienota ar katru no šīm komunikācijām. Uzzīmēt atbilstošu grafu! = ≠ D Grafus 𝐺 un 𝐺′ sauc par izomorfiem, ja grafa 𝐺 virsotnes var pārdēvēt tā, lai iegūtu grafu 𝐺′, tas ir, divus grafus 𝐺 un 𝐺′ sauc par izomorfiem (apzīmē 𝐺 ≅ 𝐺′), ja eksistē tāda bijektīva atbilstība starp grafa 𝐺 un 𝐺′ virsotnēm, ka divas virsotnes ir blakusvirsotnes grafā 𝐺 tad un tikai tad, ja atbilstošās virsotnes ir blakusvirsotnes grafā 𝐺′. Bijektīvā atbilstība tiek saukta par izomorfismu. P Vai dotie grafi ir izomorfi? 𝑢 4 Izomorfi grafi 𝐺 ≅ 𝐺′ 𝑣 3 𝑤 2 𝑥 1 P Vai dotie grafi ir izomorfi? Nav izomorfi grafi D Par virsotnes 𝑣 pakāpi sauc šķautņu skaitu, kas incidentas virsotnei 𝑣 (katru cilpu ieskaita divas reizes). Apzīmē 𝑑(𝑣). Par orientēta grafa virsotnes 𝑣 pozitīvo (negatīvo) puspakāpi sauc ar 𝑣 incidento ieejošo (izejošo) šķautņu skaitu. Apzīmē attiecīgi ar 𝑑+ (𝑣) un 𝑑− (𝑣). Piezīme. Apzīmējums 𝑑(𝑣) no vārda «degree» Ko var ievērot? D Par grafa 𝐺 = (𝑉, 𝐸) apakšgrafu sauc grafu, kura virsotņu kopa ir kopas 𝑉 apakškopa un šķautņu kopa ir kopas 𝐸 apakškopa. Kā pārbaudīt, vai dotie grafi ir izomorfi? Virsotņu un šķautņu skaits Cilpas, multišķautnes Virsotņu pakāpes (maksimālā, minimālā u.tml.) Orientētos grafos arī vērsums Apakšgrafi (fiksēta garuma cikli, ķēdes) Uzdevumi 12., 13., 16. uzdevums MD 14., 15. uzdevums Literatūra un avoti https://youtu.be/82zlRaRUsaY https://de.du.lv/matematika/daugulis/daugulis.html http://susurs.mii.lu.lv/Graphlab/Education/grafuTeorijaLatvija/DA MBITIS/index.html http://susurs.mii.lu.lv/Graphlab/Education/grafuTeorijaLatvija/Jan isCirulis/jcgrafi.html A. Tucker. Applied Combinatorics. Wiley, 2012. J. Aldous, R. J. Wilson. Graphs and Applications: An Introductory Approach. Springer, 2000. https://www.youtube.com/watch?v=ADR7dUoVh_c – video – pārcelšanās pāri upei, cits uzdevums