19. nodarbība

19. nodarbība

1. Grafu teorija - ceļi, cikli.
2. Teorēma par Eilera ceļu grafā.
3. Dažādi uzdevumi par grafa sakarību un apstaigāšanu.

Uzdevumi

1. uzdevums. Valstī no katras pilsētas iziet 100 ceļi. No katras pilsētas var pašiem ceļiem aizbraukt uz jebkuru citu pilsētu. Vienu ceļu slēdz remonta dēļ. Pierādīt, ka joprojām var no jebkuras pilsētas aizbraukt uz jebkuru citu pilsētu! Kāds ir lielākais ceļu skaits, kurus var slēgt tā, lai joprojām var tikt no jebkuras pilsētas uz jebkuru citu, ja valstī ir 1000 pilsētu?
2. uzdevums. Kādā mājā ir 5 tumšas istabas un 4 apgaismotas istabas. Ir zināms, ka no divām tumšajām istabām (no katras) var aiziet uz 3 gaišajām istabām, bet no pārējām trim tumšajām – no katras var nokļūt divās gaišajās istabās.
   1. Vai var atrast tādu istabu apstaigāšanas secību, ka pēc tumšas istabas var nonākt gaišā istabā, pēc tam – tumšā, atkal gaišā utt., un atgriezties istabā, no kuras sākās apgaita, katrā istabā iegriežoties vienu reizi?
   2. Vai noteikti tāds cikls ies cauri visām gaišajām istabām?
   3. Vai var tādu ciklu izveidot cauri visām istabām?
   4. Ko var teikt par gadījumu, ja zināms tikai tas, ka šajā mājā ar 5 tumšām un 4 gaišām istabām ir atvērtas tikai 10 durvis, bet pārējās aizslēgtas?
   5. Pamēģiniet uzzīmēt tādu 5 istabu plānu, kur jebkuras divas istabas ir savienotas!
3. uzdevums. Muša sēdēja uz šaha dēlīša baltās stūra rūtiņas. Tad viņa rāpoja pa visiem baltajiem lauciņiem, neiegriežoties nevienā melnajā lauciņā, un negāja pāri vienam un tam pašām krustojumam (punkts, kas ir kopīgs 2 melnajiem un 2 baltajiem lauciņiem). Mušas ceļš sastāvēja no 17 taisniem nogriežņiem. Uzzīmējiet mušas maršrutu!
4. uzdevums. Plaknē ir uzzīmētas 100 riņķa līnijas. Zīmējums ir sakarīga figūra (nesastāv no vairākām daļām). Pierādīt, ka šo figūru var uzzīmēt ar vienu zīmuļa vilcienu!
5. uzdevums. Pierādīt, ka grafs, kurā ir n virsotnes un katras virsotnes pakāpe ir ne mazāka par (n-1)/2, ir sakarīgs!
6. uzdevums. Tūrists apstaigāja 6 ielas vecpilsētā, pa katru ielu tieši divas reizes. Izstaigāt šis ielas tā, lai pa katru no tām viņš būtu gājis tieši vienu reizi (neiegriežoties nekādās citās ielās), nav iespējams. Vai tā var būt, ja a) ielas beidzas ar strupceļu; b) katras ielas sākums un gals beidzas ar doto ielu krustojumu?
7. uzdevums. Tūrists sāka pastaigu pa Vecrīgu, izejot no viesnīcas Rīga. Apskatījis Doma laukumu, viņš vēlējās atgriezties pie viesnīcas, ejot pa tām ielām, pa kurām viņš bija gājis nepāra skaitu reižu. Vai viņam tas izdosies?