Septyni Karaliaučiaus tiltai
Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Septynių Karaliaučiaus tiltų uždavinys - grafų teorijos vienas iš pirmųjų 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į išsprendė L. Oileris 1736 metais. 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 kelias). Tai yra įmanoma, jei grafas neturi nei vienos viršunės arba turi lygiai dvi viršūnes su nelyginiu briaunų skaičiumi.
