A königsbergi hídprobléma: Euler, gráfelmélet és topológia
Fedezd fel a königsbergi hídprobléma történetét: Euler bizonyítása, a gráfelmélet és topológia születése, és miért nincs megoldás a hídséta rejtvényére.
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.
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
Keres