Septyni Karaliaučiaus tiltai — Eilerio uždavinys ir grafų teorijos pradžia
Sužinokite apie Septynių Karaliaučiaus tiltų uždavinį: Eilerio 1735 m. sprendimas pradėjo grafų teoriją ir įkvėpė topologijos raidą.
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.
Problemos modeliavimas grafu
Eulerio pagrindinė idėja buvo supaprastinti realią situaciją: kiekvieną sausumos plotą (krantą ar salą) atstovauti vienu tašku (viršūne), o kiekvieną tiltą — linija (kraštine) tarp tų taškų. Tokiu būdu miesto tilto tinklas tampa grafu. Karaliaučiaus atveju grafas turi 4 viršūnes (dvi salos ir du krantai) ir 7 kraštines (tiltus).
Šio konkretaus grafo viršūnių laipsniai (t. y. prie kiekvienos viršūnės einančių kraštinių skaičiai) yra: 5, 3, 3 ir 3. Visi keturi laipsniai yra nelyginiai — tai ir yra lemtingas momentas.
Eulerio įrodymas — paritetinis (poriškumo) argumentas
Euleris parodė paprastu paritetiniu argumentu, kodėl užduotis neturi sprendimo. Pagrindinė mintis:
- Jeigu pasivaikščiojimas prasideda vienoje vietoje ir baigiasi kitoje, tai kiekvieną kartą užėjus į vidinę viršūnę (ne pradinę ir ne galutinę) tenka ir išeiti — taigi kraštinės „naudojamos“ poromis. Todėl bet kuri vidinė viršūnė turi lyginį kraštinių skaičių (laipsnį).
- Jeigu marsrutas prasideda ir baigiasi tame pačiame taške (uždaras maršrutas), tai visos viršūnės turi lyginius laipsnius, nes kiekvienas įėjimas yra lydimas išėjimo.
Iš čia seka bendresnė taisyklė: sujungtame grafe maršrutas, einantis per kiekvieną kraštinę tik vieną kartą (vadinamas Eulerio taku), egzistuoja tik tuomet, kai odd (nelyginių laipsnių) viršūnių skaičius yra lygus 0 arba 2. Jeigu nelyginių viršūnių yra 0, galimas uždaras Eulerio ratas (Eulerio ciklas); jeigu jų yra 2, galimas atviras Eulerio takas, prasidedantis vienoje nelyginėje viršūnėje ir pasibaigiantis kitoje. Karaliaučiaus grafe nelyginių viršūnių yra 4, todėl reikalavimas nėra įvykdytas — sprendimo nėra.
Taip pat: sąlygos ir konstrukcijos
Svarbu pažymėti, kad minėta sąlyga yra tiek būtina, tiek ir (esant grafui, kurio dalys yra sujungtos) pakankama. Pakankamumui parinkti konstruktyvų metodą galima paminėti Hierholzero algoritmą: jis sukuria uždarą Eulerio ciklą, jei visi viršūnių laipsniai yra lyginiai, arba atvirą taką, jeigu yra tik dvi nelyginės viršūnės. Tačiau Karaliaučiaus pavyzdyje tokia konstrukcija neįmanoma dėl keturių nelyginių viršūnių.
Istorinė ir matematinė reikšmė
Šis, iš pirmo žvilgsnio žaismingas, uždavinys yra reikšmingas todėl, kad pirmą kartą aiškiai buvo parodyta: abstraktus objektų ryšių tyrimas (grafai) leidžia spręsti praktines užduotis be detalaus erdvinio vaizdavimo. Eulerio sprendimas laikomas grafų teorijos pradžia — vėliau ši sritis tapo svarbi daugelyje sričių: kompiuterių moksle, tinklų teorijoje, topologijoje, logistikos ir transporto planavime.
Karaliaučiaus tiltais paremtas uždavinys taip pat tapo populiariu galvosūkiu ir pavyzdžiu matematikos dėstymui: jis aiškiai demonstruoja, kaip formalizacija ir paprastas aritmetinis pagrindymas gali išspręsti klausimą, kurį sunku būtų išspręsti vien tik brėžiant kelią realioje žemėlapyje.
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.
Ieškoti