Septiņi Kēnigsbergas tilti ir vēsturiski slavena matemātikas problēma. Šo problēmu 1735. gadā atrisināja Leonhards Eulers. Tas aizsāka grafu teoriju. Tas vēlāk noveda pie topoloģijas attīstības.

Kēnigsbergas pilsēta Prūsijā (tagad Kaļiņingrada, Krievija) atradās abpus Pregeles upei. Tā ietvēra divas lielas salas, kas bija savienotas viena ar otru un ar cietzemi ar septiņiem tiltiem.

Problēma bija atrast veidu, kā izstaigāt pilsētu, šķērsojot katru tiltu vienu reizi un tikai vienu reizi. Uz salām nevarēja nokļūt pa citiem ceļiem, kā tikai pa tiltiem. Katrs tilts katru reizi bija jāšķērso pilnībā. Pastaiga nedrīkēja sākties un beigties vienā un tajā pašā vietā. Ēlers pierādīja, ka šai problēmai nav risinājuma.

Eilera ideja — pārveidot problēmu par grafu

Eilers problēmu vienkāršoja, pārveidojot to par abstraktu shēmu: katru sauszemes gabalu (divas salas un divas krasta daļas) viņš attēloja kā punktu (virsotni), bet katru tiltu — kā līniju (malu), kas savieno divas virsotnes. Tādējādi pilsētas tiltu tīklojums kļuva par saistītu grafu ar četriem virsotnēm un septiņām malām.

Kā Eilers pierādīja, ka risinājuma nav

Galvenā novērojuma doma ir šāda: katru reizi, kad gājējs nonāk kādā vietā, lai izietu tālāk, viņam jāienāk pa vienu tiltu un jāiziet pa citu — tas nozīmē, ka noņemtie (izmantojamie) tilti katrā "vidējā" vietā ir pāru skaitā. Tāpēc, ja maršruts nav slēgts (sākas un beidzas dažādās vietās), tikai divās vietās — sākuma un beigu punktā — var būt nepāra skaits izejošu tiltu; visām pārējām vietām jābūt pāra skaitā.

Formulēti matemātiski: par saistītu grafu ir spēkā sekojošs nosacījums:

  • ja visas virsotnes ir pāra pakāpes, grafā eksistē slēgts ceļš, kas ietver visas malas tieši vienu reizi (t.s. Eulerova cikla);
  • ja tieši divas virsotnes ir nepāra pakāpes, eksistē atvērts ceļš, kas sākas vienā un beidzas otrā no šīm nepārajām virsotnēm (t.s. Eulerova taka);
  • ja ir vairāk nekā divas nepāra virsotnes, tad nav iespējams iziet cauri visām malām tieši vienu reizi.

Konkrētajā Kēnigsbergas gadījumā grafā bija četras virsotnes, un visu šo virsotņu pakāpes (tiltu skaits, kas pievienots katrai zemes daļai) izrādījās nepāra — konkrēti 3, 3, 3 un 5 (kopā 14 malas = 2·7). Tā kā nepāroto virsotņu bija vairāk nekā divas, Eilera secinājums bija skaidrs: nav iespējams izstaigāt pilsētu tā, lai katru tiltu šķērsotu tieši vienu reizi.

Vēsturisks un teorētisks nozīmīgums

Eilera raksts (1736. gadā publicētais "Solutio problematis ad geometriam situs pertinentis") tiek uzskatīts par grafu teorijas dzimšanu. Lai gan Eilers neizmantoja mūsdienu terminus "grafi" vai "virsotnes", viņa ideja par objektu savienojumu un to īpašību analīzi atklāja jaunu matemātikas virzienu. No šīs vienkāršās uzbūves attīstījās gan grafu teorija, gan topoloģijas sākotnējās idejas par pozīcijas īpašībām, kas nemainās deformējot objektu.

Mūsdienās Eilera princips un Eulerova taka ir plaši izmantoti — no pilsētplānošanas un maršrutu optimizācijas līdz ķīmijas molekulārām struktūrām un datortīklu analīzēm. Kēnigsbergas tiltu problēma palikusi par klasiķu piemēru, kas parāda, kā vienkārša, ikdienišķa uzdevuma pārdomāšana var novest pie jaunas teorijas radīšanas.