Vikipedija

Septyni Karaliaučiaus tiltai: Skirtumas tarp puslapio versijų

Naršyti istoriją interaktyviai
← Prieš tai darytas keitimasKitas pakeitimas →
Ištrintas turinys Pridėtas turinys
VizualusVikitekstas
YurikBot (aptarimas | indėlis)
25 557 keitimai
S robotas Pridedama: fi:Königsbergin siltaongelma
Lang-Bot-as (aptarimas | indėlis)
106 625 keitimai
S Automatinis brūkšnių taisymas
Eilutė 1:
[[Image:Konigsberg bridges.png|right|thumb|200px|<small>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.
 
[[Image:KaralTiltuGrafas.png|right|thumb|165px|<small>Tiltus atitinkantis grafas]]
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.
 
[[Kategorija:Grafų teorija]]
Rodomas puslapis "https://lt.wikipedia.org/wiki/Septyni_Karaliaučiaus_tiltai"