A königsbergi hidak problémája

A königsbergi hidak problémája híres matematikai probléma, amelyet Leonhard Euler oldott meg. A probléma története, hogy a poroszországi Königsberg (most Kalinyingrád, Oroszország) városban hét híd ívelt át a várost átszelő Prégel folyón úgy, hogy ezek a folyó két szigetét is érintették. A königsbergiek azzal a kérdéssel fordultak Eulerhez, vajon végig lehet-e menni az összes hídon úgy, hogy mindegyiken csak egyszer haladjanak át, és visszaérjenek a kiindulópontba. 1736-ban Euler bebizonyította, hogy ez lehetetlen.

Königsberg térképe Euler idejében, kiemelve a Prégel folyó és a hidak elhelyezkedése

A történethez hozzátartozik az a legenda is, hogy 1750 körül állítólag a königsbergi elit tagjai rendszeresen sétálgattak vasárnaponként a hidakon, hogy egy olyan útvonalat találjanak, amely megfelel a fenti feltételeknek.

Euler megoldása

A bizonyítás során Euler a problémát a gráfelmélet nyelvén fogalmazta meg, azaz leegyszerűsítette azt: a földeket, tehát a folyó partjait és a szigeteket csúcsoknak, a hidakat pedig éleknek tekintette. Az így létrehozott csomópontok és élek pedig egy gráfot határoznak meg.

→ →

Euler észrevette, hogy a problémát az így létrehozott gráf csúcsainak a fokszámára lehet visszavezetni. A csúcs fokszáma alatt az adott csúcshoz csatlakozó élek számát értjük. A konkrét esetben a hidak elhelyezkedése alapján megalkotott gráfban három csúcsnak 3 a fokszáma, egynek pedig 5. Euler rájött, hogy akkor és csak akkor létezik ebben az adott gráfban a hidakon pontosan egyszer végighaladó séta, ha minden csúcs fokszáma páros. A fenti feltételnek eleget tevő összefüggő gráfokat ma zárt Euler-gráfnak nevezzük, az élek sorozatát, amelyeken a bejárás megvalósul, pedig Euler-vonalnak illetve egy zárt Euler-vonalnak. A fenti feltételnek megfelelő bejárást zárt Euler-sétának hívjuk. Mivel a königsbergi hidak gráfjában több páratlan fokszámú csúcs is található, ezért Euler eredményéből következik, hogy nem lehet bejárni a königsbergi hidakat a fent megkövetelt módon.

A gráfelméletet megalapozó Euler-cikk

Ha a kiinduló pontnak és a célpontnak nem kell azonosnak lennie, akkor nyitott Euler-vonalról, illetve nyitott Euler-sétáról beszélünk. Annak a feltétele, hogy egy gráf élei nyitott Euler-vonalat alkossanak az, hogy összefüggő legyen, és pontosan kettő darab páratlan fokszámú csúcsa legyen. Ebben az esetben a nyitott Euler-séta kiinduló és végpontja pontosan a két páratlan fokszámú csúcsa a gráfnak.

Matematikai jelentősége

A matematika történetében a königsbergi hidak problémáját, illetve ennek Euler-féle megoldását tartják az első gráfelméleti problémának. Azóta a gráfelmélet a kombinatorika egy önálló területévé vált.

Ezen túlmenően az, hogy Euler felismerte, hogy a probléma megoldásának a kulcsa a hidak, illetve pontosabban az egy partszakaszhoz kapcsolódó hidak számában, nem pedig ezek konkrét elhelyezkedésében keresendő, a topológiai szemlélet legkorábbi megjelenésének is tekinthető.

A königsbergi hidak napjainkban

Königsberg hídjai napjainkban

A hét eredeti königsbergi híd közül kettőt leromboltak a második világháború alatt a szövetséges bombázásokban. Két további hidat később az oroszok egy modern főúttal helyettesítettek. A fennmaradó három híd megmaradt (jóllehet ezek közül csak kettő származik Euler idejéből, mert a harmadikat a németek még 1935-ben újjáépítették).

Gráfelméleti fogalmakkal élve a jelenlegi négy csúcs közül kettőnek 2 a fokszáma, kettőnek pedig 3, így ma már elméletileg be lehetne járni a königsbergi hidakat, ha a kiinduló és végpontnak nem kell azonosnak lennie (Euler-vonal), azonban mivel a két páratlan fokszámú csúcs éppen a két szigeten helyezkedik el, így a bejárást az egyik szigeten kellene elkezdeni és a másikon befejezni, ami nem tűnik túl praktikus megoldásnak.

Irodalom

• Andrásfai Béla: Ismerkedés a gráfelmélettel, Tankönyvkiadó, Budapest, 1973

További információk

• Euler eredeti publikációja (latinul)