Kēnigsbergas tiltu problēma

Kēnigsbergas septiņi tilti ir vēsturiski svarīga matemātikas problēma. 1736. gadā šveicietis Leonards Eilers pierādīja, ka šai problēmai neeksistē atrisinājums, taču tas kļuva par pamatu grafu teorijas pirmsākumiem.

Problēmas būtība ir tāda, ka nepieciešams atrast ceļu Kēnigsbergas pilsētā (mūsdienu Kaļiņingradā), kurā ir septiņi tilti, lai katrs tilts tiktu šķērsots tikai vienu reizi. Kēnigsberga atradās Prēgeles upes krastā, kas pilsētā veido divas salas.

Leonards Eilers pierādīja (mūsdienu grafu teorijas terminoloģijā), ka neorientētā saistītā grafā, kura virsotņu pakāpe ir pāra skaitlis, eksistē cikls, kas ļauj apiet visas grafa šķautnes, virzoties pa katru šķautni vienu reizi un atgriezties virsotnē, no kuras ceļš uzsākts.

Šis cikls tika nosaukts Eilera vārdā.

Vēsture

Jau izsenis Kēningsbergas iedzīvotāju vidū pastāvēja jautājums par šo matemātisko mīklu: kā nokļūt uz visiem pilsētas tiltiem, šķērsojot Prēgeles upi, lai nevienu no tiem nenāktos šķērsot divas reizes. Daudzi Kēnigsbergas iedzīvotāji mēģināja atrisināt šo problēmu, gan teorētiski, gan praktiski, piemēram, pastaigas laikā. Tomēr pierādīt vai atspēkot maršruta iespējamību neviens nevarēja.

1736. gadā par problēmu ar septiņiem tiltiem ieinteresējās izcils matemātiķis, Pēterburgas Zinātņu akadēmijas loceklis Leonards Eilers, par to viņš rakstīja vēstulē Itālijas matemātiķim un inženierim Marinoni 1736. gada 13. martā.

Vēstulē Eilers rakstīja, ka viņš varētu atrast formulu, kuru izmantojot būtu viegli noteikt, vai ir iespējams iet pāri visiem tiltiem nešķērsojot divreiz nevienu no tiem. Šajā gadījumā atbilde bija "nē".

Eilera dotais uzdevuma risinājums

Eilera laika Kēnigsbergas karte ar iezīmētu upi un septiņiem tiltiem

Kēnigsbergas septiņu tiltu problēmai atbilstošais grafs

Pilsētas vienkāršotā shēmā (diagrammā) tilti atbilst līnijām (malas grafikā), un pilsētas daļas - līnijas slēguma punkti (virsotnes).

Eilers nonāca pie šādiem secinājumiem:

Nepāra virsotņu skaits nedrīkst būt pāra skaitlis.
Ja visas virsotnes ir pāra, tad ir iespējams, nepaceļot zīmuli no papīra, zīmēt grafu, un jūs varat sākt jebkurā virsotnē un pabeigt to tajā pašā virsotnē.
Ja tieši divas virsotnes ir nepāra, tad ir iespējams, nepaceļot zīmuli no papīra, zīmēt grafu, un jūs varat sākt ar kādu no nepāra virsotnēm un pabeigt to citā nepāra virsotnē.
Ja ir vairāk par 2 nepāra virsotnēm, tad nav iespējams uzzīmēt grafu, nepaceļot zīmuli no papīra.

Kēnigsbergas tiltiem bija četras nepāra virsotnes - tātad ir neiespējamiiet pāri visiem tiltiem, nepārejot nevienu no tiem divreiz.

Tālāka vēsture

1905. gadā tika uzcelts Imperatora tilts, kas pēc tam tika iznīcināts Otrā pasaules kara laikā. Pastāv leģenda, ka tilts tika uzbūvēts pēc ķeizara rīkojuma, kurš nespēja atrisināt Kēnigsbergas tiltu problēmu un kuru izjokoja zinātnieki, sakot, ka ja tiks uzbūvēts astotais tilts, tad problēma būs atrisināta.

Uz Imperatora tilta atbalstiem 2005. gadā bija uzbūvēts Jubilejas tilts.

2016. gadā Kēnigsbergā (Kaļiņingradā) bija astoņi tilti.

Ārējās saites

Encyclopædia Britannica raksts (angliski)
Königsberg Bridge Problem (angliski)

Šis ar matemātiku saistītais raksts ir nepilnīgs. Jūs varat dot savu ieguldījumu Vikipēdijā, papildinot to.