Septyni Karaliaučiaus tiltai: Skirtumas tarp puslapio versijų

[[Image:Konigsberg bridges.png|right|thumb|200px|Karaliaučiaus tiltai]]

'''Septynių Karaliaučiaus tiltų''' uždavinys – [[grafų teorija|grafų teorijos]] vienas iš pirmųjų uždavinių, kilęs iš realios situacijos. Uždavinio formuluotė – ar įmanoma apeiti septynis [[Karaliaučius|Karaliaučiaus]] tiltus per Priegliaus upę (pav.) kiekvieną tiltą pereinant tik vieną kartą ir grįžtant į pradinį tašką.

 

Pirmasis šį uždavinį išsprendė [[Leonardas Euleris|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.