Sedm mostů města Královce

Sedm mostů města Královce je slavný, již vyřešený matematický problém, založený na skutečném místě a skutečné situaci. Pruské město Královec (též Königsberg, nyní Kaliningrad na území Ruska) leží na řece Pregole, která vytváří dva ostrovy. Ostrovy byly s okolním městem spojeny sedmi mosty.

Mapka Královce z Eulerových dob s vyznačením sedmi mostů

Otázka zní, zda je možné všechny mosty přejít tak, aby ten, kdo se o to pokouší, přešel přes každý most přesně jednou. Leonhard Euler jako první dokázal, že to možné není, odpovídající graf totiž nelze projít pomocí tzv. eulerovského tahu.

Řešení

→ →

Euler problém přeformuloval na základě své teorie grafů (viz obrázek výše) a dokázal, že v grafu, vytvořeném na základě mapy města Královce, eulerovský tah neexistuje (a tedy sedm mostů města Královce netvoří eulerovský graf). Pouze eulerovské grafy mají tu vlastnost, že je možné je „nakreslit jedním tahem“. Pokud tedy sedm mostů města Královce eulerovský graf netvoří, dokazuje to, že mosty není možné tímto způsobem přejít.

Dnešní stav

Dnes z původních mostů zbyly jen dva, jeden most byl nahrazen zvedacím, dva mosty byly zničeny za britského náletu v roce 1944 a další dva byly později nahrazeny novostavbou Sověty při stavbě silničního průtahu. Nově byl vybudován další most z jižního břehu na větší ostrov. Mimo ostrovy přes řeku pak na západě vznikl železniční most (nyní trvale rozložený), další silničně-železniční most a v roce 2011 na východě nová estakáda, která větší ostrov překračuje. Je tu tak celkem osm použitelných mostů. V nové konfiguraci mostů eulerovský tah existuje, ale je otevřený — začíná na menším z ostrovů a končí na jižním břehu.