"113195" - 1 õppematerjal

Diskreetse matemaatika elemendid, eksami konspekt

tsükliks. b. Graafi, kus leidub Euleri tsükkel, nimetatakse Euleri graafiks. c. Nt, postiljoni marsruudi valimine, et ühtegi tänavat mitu korda ei läbiks. d. Euleri graafi leidumise kriteerium. Sidusas graafis leidub Euleri tsükkel parajasti siis, kui graafi iga tipu aste on paarisarv. d.i. Tõestus. https://moodle.ut.ee/mod/url/view.php?id=107318 lk 56. d.ii. https://moodle.ut.ee/mod/resource/view.php?id=113195 lk 28. 39) a. Ahelat, mis läbib graafi kõik tipud täpselt üks kord, nimetatakse Hamiltoni ahelaks. b. Tsüklit, mis läbib graafi kõik tipud täpselt üks kord, nimetatakse Hamiltoni tsükliks. c. Graafi, kus leidub Hamiltoni tsükkel, nimetatakse Hamiltoni graafiks. d. Nt, reisiva müügimehe probleem (TSP). e. Hamiltoni tsükli olemasolu kontrolliks ei ole teada ühtegi kergesti kontrollitavat tarvilikku ja piisavat tingimust