A königsbergi hidak problémája

A tizennyolcadik században Königsberg városának lakói hosszú ideig egy fejtörővel bajlódtak: a városon átfolyik a Pregolja folyó, amely két szigetet alkot. A folyón összesen hét híd vezet a szigetekre. Lehetséges-e egyetlen vasárnapi séta alatt mind a hét hídon átmenni, de mindegyiken pontosan egyszer? Nézzük meg, hogyan álltak a hidak a folyón:

Lehetséges-e, hogy valahol elkezdjük a sétánkat, és pontosan egyszer bejárjuk az összes hidat? Megpróbálhatjuk: a bal alsó sarokban kezdünk, felfelé haladunk, aztán fokozatosan jobbra, így:

Látjuk, hogy a hét hídból hatot jártunk be, az egyik hidat kihagytuk. Megpróbálhatunk másik utat…

Megint csak a hét hídból hatot jártunk be Königsbergben. Majdnem úgy tűnik, hogy lehetetlen egyetlen sétával mindegyik hídon pontosan egyszer átmenni. Egy napon a híres matematikus, Leonhard Euler belebotlott ebbe a problémába. Mit híres – Euler a matematika igazi legendája volt, róla nevezték el az Euler-féle számot is. Euler azt mondta magában, hogy megfejti ezt a fejtörőt. Azzal kezdte, hogy megjelölte az egyes szigeteket vagy városrészeket, amelyekbe és amelyekből hidak vezettek:

Euler most a következőképpen gondolkodott: ha egy szigetre páros számú híd vezet, ezeket a hidakat egyetlen séta alatt bejárhatjuk, bárhol is kezdjük. Egyszerűen: az egyik hídon megérkezünk a szigetre, a másikon elmegyünk – a bejárandó hidak száma kettővel csökkent. Ahhoz, hogy az egyik hídon megérkezzünk a szigetre, és a másikon eltávozzunk, két híd kell. Ha egy szigetre hat híd vezet, háromszor látogatjuk meg a szigetet. Például képzeljük el, hogy a B szigetre négy híd vezetne így:

Akkor egyetlen vasárnapi sétával bejárhatjuk az összes hidat, bárhol kezdjük. Próbáld ki! Az ábrán bejelöltem egy utat. Képzeljük el, hogy a B szigetre még egy híd vezetne a D szigetről:

Látjuk, hogy az általunk választott út nem teszi lehetővé, hogy az összes hidat pontosan egyszer bejárjuk. Valamelyik hídon vissza kellene mennünk a B szigetre, aztán átmenni a D szigetre. De választhatunk másik utat. Elkezdhetjük a sétánkat a B szigeten, és akkor képesek vagyunk pontosan egyszer bejárni az összes hidat:

A sétánkat a B szigeten kezdtük, felmentünk az A területre, aztán hídon vissza B-re, a C területre, aztán vissza a B szigetre, és végül a D szigetre. Ha tehát olyan szigeten kezdünk, amelyre páratlan számú híd vezet, képesek vagyunk pontosan egyszer bejárni az összes hídját. Vagy mehetünk egészen fordítva – kezdhetünk a D szigeten, és a B szigeten fejezhetjük be.

Euler így észrevette, hogy ahhoz, hogy az összes hidat pontosan egyszer be lehessen járni, teljesülnie kell, hogy vagy az összes szigetre páros számú híd vezet, vagy lehet két sziget, amelyre páratlan számú híd vezet – az egyik páratlan hídszámú szigeten kezdünk, a másikon fejezzük be. Az összes többi szigetre páros számú hídnak kell vezetnie. Ha megnézzük az eredeti hét hidat Königsbergben:

akkor látjuk, hogy minden szigetre páratlan számú híd vezet! Az A szigetre 3, a B-re 5, a C-re 3, a D-re pedig szintén 3. Ezért a fejtörőnek nincs megoldása – lehetetlen, hogy egyetlen vasárnapi sétán mind a hét hídon pontosan egyszer átmenjünk. Ha lebontanánk bármelyik hidat, a fejtörőnek hirtelen lenne megoldása. Bontsuk le például az egyik hidat a B és C sziget között:

Látjuk, hogy a B szigetre máris 4 híd vezet, a C szigetre pedig kettő. Az A és D szigetek hídjainak száma nem változott. Most már két sziget van páros hídszámmal és két sziget páratlan hídszámmal. Ha a sétánkat az egyik páratlan hídszámú szigeten kezdjük, képesek vagyunk pontosan egyszer bejárni az összes hidat. Az ábrán az A szigeten kezdtük, és a D szigeten fejeztük be.

Leonhard Euler tehát megoldott egy újabb híres matematikai problémát, és többé-kevésbé lefektette annak az alapjait, amit manapság gráfelméletnek nevezünk, és az ő tiszteletére nevezik a gráfelmélet nyelvén azt a gráfot, amelyben minden élt pontosan egyszer be lehet járni, Euler-gráfnak.