Königsbergi hidak problémája
A königsbergi hét híd a matematika történelmileg híres problémája. Leonhard Euler 1735-ben oldotta meg a problémát. Ez vezetett a gráfelmélet kezdetéhez. Ez aztán a topológia fejlődéséhez vezetett.
A poroszországi Königsberg (ma Kalinyingrád, Oroszország) városa a Pregel folyó két oldalán feküdt. Két nagy szigetet foglalt magában, amelyeket hét híd kötött össze egymással és a szárazfölddel.
A probléma az volt, hogy megtaláljuk a módját annak, hogy minden egyes hídon egyszer és csak egyszer menjünk át a városon. A szigetekre a hidakon kívül semmilyen más útvonalon nem lehetett eljutni. Minden hidat minden alkalommal teljesen át kellett kelni. A sétának nem kellett ugyanazon a helyen kezdődnie és végződnie. Euler bebizonyította, hogy a problémának nincs megoldása.
Königsberg Euler korabeli térképe, amely a hét híd tényleges elrendezését mutatja, kiemelve a Pregel folyót és a hidakat.
Euler analízise
Először is, Euler rámutatott, hogy az egyes szárazföldi tömegeken belüli útvonal megválasztása nem számít. Az útvonal egyetlen fontos tulajdonsága az, hogy milyen sorrendben haladunk át a hidakon. Ezért a problémát absztrakt fogalmakra változtatta. Ezzel lefektette a gráfelmélet alapjait. A szárazföldek és az azokat összekötő hidak listáján kívül minden más jellemzőt eltávolított. A gráfelmélet nyelvén minden egyes szárazföldi tömeget egy absztrakt "csúcsra" vagy csomópontra cserélt. Ezután minden hidat egy absztrakt kapcsolattal, egy "éllel" helyettesített. Egy él (út) rögzítette, hogy két csúcs (szárazföldi tömegek) milyen összeköttetésben áll egymással. Ily módon egy gráfot alkotott.
→
→ 
A rajzolt grafikon a probléma absztrakt képe. Az élek tehát tetszőlegesen összekapcsolhatók. Csak az a fontos, hogy két pont összekapcsolódik-e vagy sem. A gráf képének megváltoztatása nem változtatja meg magát a gráfot.
Ezután Euler megfigyelte, hogy (a séta végpontjait kivéve), amikor egy csomópontba egy hídon keresztül lépünk be, a csomópontot egy hídon keresztül hagyjuk el. A gráf bármelyik sétaútján az, hogy hányszor lépünk be egy csúcsba, egyenlő azzal, hogy hányszor hagyjuk el azt. Ha minden hídon pontosan egyszer mentünk át, akkor ebből az következik, hogy minden földtömeg esetében (kivéve a kiindulási és célpontnak választottakat) az adott földtömeget érintő hidak száma páros kell, hogy legyen. Ez azért van így, mert ha n híd van, akkor pontosan 2n alkalommal halad át rajta. Az eredeti feladatban szereplő mind a négy szárazföldet páratlan számú híd érinti (az egyiket 5 híd érinti, a másik hármat pedig 3). Legfeljebb két olyan tömeg van, amely egy séta végpontja lehet. Tehát az a tétel, hogy a séta minden hidat egyszer keresztez, ellentmondáshoz vezet.
Modern nyelven Euler megmutatja, hogy a csomópontok fokozataitól függ, hogy lehetséges-e egy gráfon való séta, amely minden élen egyszer keresztez vagy sem. Egy csomópont foka az azt érintő élek száma. Euler megmutatja, hogy a séta szükséges feltétele, hogy a gráf összefüggő legyen, és pontosan nulla vagy két páratlan fokú csomópontja legyen. Ezt az Euler által megállapított eredményt később Carl Hierholzer bizonyította be. Az ilyen sétát ma Euler-útnak vagy Euler-sétának nevezzük. Ha vannak páratlan fokú csomópontok, akkor bármelyik Euler-útvonal az egyiknél kezdődik és a másiknál végződik. Mivel a történelmi Königsberget ábrázoló gráfnak négy páratlan fokú csomópontja van, nem lehet Euler-útvonala.
Euler munkáját 1735. augusztus 26-án mutatták be a Szentpétervári Akadémián. Solutio problematis ad geometriam situs pertinentis (A hely geometriájával kapcsolatos probléma megoldása) címmel 1741-ben jelent meg a Commentarii academiae scientiarum Petropolitanae című folyóiratban. Angolul a The World of Mathematics című könyvben olvasható.
Jelentősége a matematika történetében
A matematika történetében Euler Königsberg hídproblémájának megoldását tekintik a gráfelmélet első tételének. A gráfelmélet ma már általánosan a kombinatorika egyik ágának tekinthető.
A hidak jelenlegi állapota
A hét eredeti hídból kettő megsemmisült Königsberg második világháborús bombázása során. Két másik hidat később lebontottak. Helyükre modern autópálya épült. A másik három híd megmaradt, bár közülük csak kettő származik Euler korából (az egyiket 1935-ben építették át). Így 2000-ben öt híd volt Kalinyingrádban.
A gráfelmélet szempontjából két csomópontnak most már 2. fokú, a másik kettőnek pedig 3. Ezért most már lehetséges egy Euler-útvonal, de mivel az egyik szigeten kell kezdődnie és a másik szigeten kell végződnie, a turisták számára nem praktikus.
Kapcsolódó oldalak
- Icosian játék
- Hamiltoni útvonal
- Víz, gáz és villany
- Utazó eladó probléma
