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.