Septyni Karaliaučiaus tiltai
Septyni Karaliaučiaus tiltai yra istoriškai garsi matematikos problema. Leonardas Euleris išsprendė šį uždavinį 1735 m. Tai lėmė grafų teorijos pradžią. Vėliau tai paskatino topologijos plėtrą.
Prūsijos Karaliaučiaus miestas (dabar Kaliningradas, Rusija) buvo išsidėstęs abipus Pregelio upės. Jį sudarė dvi didelės salos, kurias tarpusavyje ir su žemynu jungė septyni tiltai.
Problema buvo rasti būdą, kaip pereiti miestą per kiekvieną tiltą vieną kartą ir tik vieną kartą. Salų nebuvo galima pasiekti jokiais kitais keliais, išskyrus tiltus. Kiekvienas tiltas kiekvieną kartą turėjo būti pereitas iki galo. Pasivaikščiojimas neturėjo prasidėti ir baigtis toje pačioje vietoje. Euleris įrodė, kad uždavinys neturi sprendimo.
Eulerio laikų Karaliaučiaus žemėlapis, kuriame pavaizduotas tikrasis septynių tiltų išdėstymas, išryškinant Pregelio upę ir tiltus
Eulerio analizė
Pirma, Euleris pažymėjo, kad maršruto pasirinkimas kiekvienos sausumos masyvo viduje neturi reikšmės. Vienintelė svarbi maršruto savybė yra tiltų kirtimo tvarka. Taigi jis pakeitė problemą į abstrakčią. Taip buvo padėti grafų teorijos pagrindai. Jis pašalino visas savybes, išskyrus sausumos masyvų ir juos jungiančių tiltų sąrašą. Grafų teorijos kalba kiekvieną sausumos masyvą jis pakeitė abstrakčia "viršūne" arba mazgu. Tada kiekvieną tiltą jis pakeitė abstrakčia jungtimi - briauna. Briauna (kelias) fiksavo, kurios dvi viršūnės (sausumos masyvai) buvo sujungtos. Taip jis sudarė grafą.
→
→ 
Nubraižytas grafikas yra abstraktus problemos vaizdas. Taigi briaunos gali būti sujungtos bet kokiu būdu. Svarbu tik tai, ar du taškai yra sujungti, ar ne. Pakeitus grafo paveikslėlį, pats grafas nepasikeičia.
Toliau Euleris pastebėjo, kad (išskyrus galutinius ėjimo taškus), kai į viršūnę įeinama tiltu, iš viršūnės išeinama tiltu. Bet kuriame grafo ėjime į viršūnę įeinančių kartų skaičius yra lygus iš jos išeinančių kartų skaičiui. Jei kiekvienas tiltas buvo peržengtas lygiai vieną kartą, vadinasi, kiekviename žemės masyve (išskyrus pradžiai ir pabaigai pasirinktus tiltus) tiltų, liečiančių tą žemės masyvą, skaičius turi būti lyginis. Taip yra todėl, kad jei tiltų yra n, tai per jį važiuojama lygiai 2n kartų. Tačiau visas keturias pradiniame uždavinyje nurodytas sausumos mases liečia nelyginis tiltų skaičius (vieną iš jų liečia 5 tiltai, o kitus tris - po 3 tiltus). Yra ne daugiau kaip dvi masės, kurios gali būti galutiniai ėjimo taškai. Taigi teiginys, kad pasivaikščiojimas kiekvieną tiltą kerta po vieną kartą, veda prie prieštaravimo.
Kalbant šiuolaikine kalba, Euleris parodė, kad ėjimas per grafą, kertant kiekvieną briauną po vieną kartą, priklauso nuo mazgų laipsnių. Mazgo laipsnis yra jį liečiančių briaunų skaičius. Euleris parodo, kad būtina vaikščiojimo sąlyga yra ta, kad grafas būtų sujungtas ir turėtų lygiai nulį arba du nelyginio laipsnio mazgus. Šį Eulerio nurodytą rezultatą vėliau įrodė Carlas Hierholzeris. Toks ėjimas dabar vadinamas Eulerio keliu arba Eulerio ėjimu. Jei yra nelyginio laipsnio mazgų, tai bet kuris Eulerio kelias prasidės viename iš jų ir baigsis kitame. Kadangi grafas, vaizduojantis istorinį Karaliaučių, turi keturis nelyginio laipsnio mazgus, jis negali turėti Eulerio kelio.
1735 m. rugpjūčio 26 d. Eulerio darbas buvo pristatytas Sankt Peterburgo akademijai. Jis buvo paskelbtas kaip Solutio problematis ad geometriam situs pertinentis (Problemos, susijusios su padėties geometrija, sprendimas) žurnale Commentarii academiae scientiarum Petropolitanae 1741 m. Jis išleistas anglų kalba leidinyje "The World of Mathematics".
Reikšmė matematikos istorijoje
Matematikos istorijoje Eulerio Karaliaučiaus tilto problemos sprendimas laikomas pirmąja grafų teorijos teorema. Dabar grafų teorija paprastai laikoma kombinatorikos šaka.
Dabartinė tiltų būklė
Du iš septynių originalių tiltų buvo sunaikinti per Antrojo pasaulinio karo bombardavimą Karaliaučiuje. Kiti du buvo nugriauti vėliau. Jų vietoje nutiestas modernus greitkelis. Kiti trys tiltai išliko, nors tik du iš jų yra iš Eulerio laikų (vienas buvo atstatytas 1935 m.). Taigi 2000 m. Kaliningrade buvo penki tiltai.
Pagal grafų teoriją du iš mazgų dabar yra 2 laipsnio, o kiti du - 3 laipsnio, todėl dabar įmanomas Eulerio kelias, bet kadangi jis turi prasidėti vienoje saloje ir baigtis kitoje, jis nepraktiškas turistams.
Susiję puslapiai
- Icosian žaidimas
- Hamiltono kelias
- Vanduo, dujos ir elektra
- Keliaujančio pardavėjo problema
Klausimai ir atsakymai
K: Kas yra septynių Karaliaučiaus tiltų problema?
A: Septyni Karaliaučiaus tiltai - tai garsi matematinė problema, kurioje reikia rasti būdą, kaip pereiti per miestą, kiekvieną iš septynių tiltų kertant tik vieną kartą.
K: Kas išsprendė septynių Karaliaučiaus tiltų problemą?
A: 1735 m. Leonhardas Euleris išsprendė septynių Karaliaučiaus tiltų problemą.
K: Ką lėmė septynių Karaliaučiaus tiltų problemos sprendimas?
Atsakymas: Septynių Karaliaučiaus tiltų problemos sprendimas paskatino grafų teorijos pradžią, kuri vėliau paskatino topologijos vystymąsi.
K: Kur yra Karaliaučius?
A: Karaliaučius yra Prūsijoje, kuri dabar priklauso Kaliningradui (Rusija).
K: Koks buvo Karaliaučiaus miesto planas?
A: Kionigsbergas buvo išsidėstęs abipus Pregelio upės ir apėmė dvi dideles salas, kurios tarpusavyje ir su žemynu buvo sujungtos septyniais tiltais.
K: Kokie buvo reikalavimai sprendžiant septynių Karaliaučiaus tiltų problemą?
A: Sprendžiant uždavinį reikėjo rasti būdą, kaip pereiti miestą per kiekvieną tiltą tik vieną kartą, kiekvieną kartą pereinant kiekvieną tiltą iki galo. Salų nebuvo galima pasiekti jokiais kitais keliais, išskyrus tiltus, o pasivaikščiojimas neturėjo prasidėti ir baigtis toje pačioje vietoje.
Klausimas: Ar Euleris įrodė, kad septynių Karaliaučiaus tiltų uždavinys turi sprendimą?
Atsakymas: Ne, Euleris įrodė, kad septynių Karaliaučiaus tiltų uždavinys neturi sprendinio.
