Septyni Karaliaučiaus tiltai
Septynių Karaliaučiaus tiltų uždavinys – vienas iš pirmųjų grafų teorijos uždavinių, kilęs iš realios situacijos. Uždavinio formuluotė – ar įmanoma apeiti septynis Karaliaučiaus tiltus per Priegliaus upę (pav.) kiekvieną tiltą pereinant tik vieną kartą ir grįžtant į pradinį tašką.
Pirmasis šį uždavinį 1736 m. išsprendė Leonardas Oileris.[1] Jis įrodė, kad sprendimas neįmanomas – nėra tokio maršruto, kad pereinant kiekvieną tiltą po kartą grįžtum į pradinį tašką. Problemos sprendimui L. Oileris panaudojo grafą (pav.), atitinkantį Karaliaučiaus tiltus.
L. Oileris įrodė, kad norimas grafo apėjimas galimas tik tada, jei nėra nei vienos viršūnės, besiliečiančios su nelyginiu briaunų skaičiumi. Toks kelias vadinamas Oilerio ciklu. Karaliaučiaus tiltų uždavinyje visos keturios grafo viršūnės liečiasi su nelyginiu briaunų skaičium, taigi netenkina sąlygos.
Taip pat yra ir kitas panašus uždavinys – kai reikia apeiti visas briaunas nebūtinai grįžtant į tą patį tašką (Oilerio maršrutas). Tai yra įmanoma, jei grafas neturi ne daugiau kaip dvi viršūnes su nelyginiais laipsniais.
Šaltiniai
[redaguoti | redaguoti vikitekstą]- ↑ Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". Comment. Acad. Sci. U. Petrop 8, 128–40.