A Königsbergi hét híd problémája a matematika egyik legismertebb, történetileg meghatározó feladata. A gondolatot Leonhard Euler dolgozta fel és publikálta 1736-ban (Solutio problematis ad geometriam situs pertinentis), megmutatva, hogy a konkrét kérdésre nincs megoldás. Euler munkája kivezetett a gráfelmélet kezdetéhez, és hozzájárult a modern topológia fejlődéséhez.
A poroszországi Königsberg (ma Kalinyingrád, Oroszország) városa a Pregel folyó két oldalán és két nagy sziget köré épült. A szigeteket és a folyópartokat összesen hét híd kötötte össze, s a helyiek között népszerű feladat volt megtalálni azt a sétát, amely minden hidat pontosan egyszer érint.
A probléma pontos megfogalmazása: van-e olyan útvonal a város nyilvános közterületein, amely minden hídat egyszer és csak egyszer érint (azaz minden hidat egyszer teljesen át kell kelni), a séta tetszőleges ponton kezdődhet és végződhet, és nincs más áthaladási lehetőség, csak a hidak. Euler bebizonyította, hogy ennél a konkrét hidakból álló hálózati elrendezésnél ilyen séta nem létezik.
A gráfmodell és Euler érvelése
Euler a problémát leegyszerűsítette: a város szárazföldi részeit (a két parti területet és a két szigetet) csomópontokként, a hidakat pedig ezeket összekötő élekként kezelte. Így a hídprobléma egy hálózatra (gráfra) vezethető vissza, amelynek csúcsai és élei a megfelelő tereptárgyak leképezései.
Az érvelés lényege a csúcspáratlanosság (fokszám) vizsgálata:
- Minden belépés és kilépés egy csúcsból két hidat (két élt) használ. Ha egy sétában egy közbenső csúcson haladsz át, az oda- és onnanvezető hidakat párosával „fogyasztod el”.
- Ezért egy zárt út (kör, ahol ugyanott kezdődik és végződik) csak olyan csúcssorozatban lehetséges, ahol minden csúcsnak páros a fokszáma. Ha a séta különböző kezdő- és végponttal végződik, akkor pontosan két olyan csúcs lehet, amelyeknek páratlan a fokszáma (az egyik a kezdő, a másik a végpont).
- Általános következmény: egy összefüggő gráfban akkor és csak akkor létezik olyan út, amely minden élt pontosan egyszer érint (Euler-út), ha a páratlan fokszámú csúcsok száma 0 vagy 2; Euler-kör (zárt Euler-út) akkor létezik, ha minden csúcs póros fokszámú.
A konkrét königsbergi hálózatban négy szárazföldrész rendelkezett páratlan számú híddal, tehát a páratlan fokú csúcsok száma négy volt — több, mint kettő — ezért a feladatnak nincs megoldása.
Következmények és örökség
Euler megoldása azért volt áttörő, mert nem a hidak pontos helyét vagy a térkép geometriáját vizsgálta, hanem a kapcsolatokat absztrahálta; ez a gondolkodásmód nyitotta meg az utat a gráfelmélet számára. A gráfelmélet ma alapvető eszköz a hálózatok, logisztika, számítógép-tudomány, biológia és társadalomtudományok területén.
További kapcsolódó fogalmak és alkalmazások:
- Euler-út és Euler-kör: a fenti feltételek szerint eldönthető, hogy egy tetszőleges hálózaton lehetséges-e minden él egyszeri érintése.
- Chinese postman problem (kínai postás probléma): keres egy legrövidebb kört, amely minden utcát (élt) legalább egyszer bejár — ha az eredeti gráf nem Euler-út képes, kellő számú élt meg kell ismételni.
- Topológiai gondolkodás: Euler munkája hozzájárult ahhoz a szemlélethez, hogy a helyek közötti kapcsolatok tulajdonságai (pl. összefüggés, körök) fontosabbak lehetnek, mint a pontos geometriai formák. Ez az egyik alapja a mai topológiának és a hálózatelméletnek.
Összefoglalva: a königsbergi hídprobléma egyszerűnek tűnő kérdéséből született egy igen jelentős elméleti áttörés — a gráfelmélet kialakulása —, és Euler érvelése ma is alapvető tételként szerepel a kombinatorikus és topológiai szemléletű matematikában.
