Königsbergi hidak problémája

A Wikipédiából, a szabad enciklopédiából
Königsberg térképe Euler idejében, kiemelve a Prégel folyó és a hidak elhelyezkedése

A königsbergi hidak problémája egy híres matematikai probléma, amit 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 egyúttal visszaérjenek a kiindulópontba. 1736-ban Euler bebizonyította, hogy ez lehetetlen.

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[szerkesztés | forrásszöveg szerkesztése]

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, azaz a folyó partjait beleértve a szigeteket is csomópontoknak, a hidakat pedig éleknek tekintette a mai megfogalmazás szerint. Az így létrehozott csomópontok és élek pedig egy gráfot határoznak meg.

Konigsberg bridges.png7 bridges.svgKönigsberg graph.svg

Euler észrevette, hogy a problémát az így létrehozott gráf csomópontjainak a fokszámára lehet visszavezetni. A csomópont fokszáma alatt az adott csomóponthoz csatlakozó élek számát értjük. A konkrét esetben a hidak elhelyezkedése alapján megalkotott gráfban három pontnak 3 a fokszáma, egynek pedig 5. Euler bebizonyította, hogy akkor és csak akkor létezik ebben az adott gráfban a hidakon pontosan egyszer végighaladó séta, ha minden csomópont 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úcspont 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.

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úcspontja legyen. Ebben az esetben a nyitott Euler-séta kiinduló és végpontja pontosan a két páratlan fokszámú pontja a gráfnak.

Matematikai jelentősége[szerkesztés | forrásszöveg szerkesztése]

A gráfelméletet megalapozó Euler-cikk

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[szerkesztés | forrásszöveg szerkesztése]

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).[1]

Gráfelméleti fogalmakkal élve a jelenlegi négy csúcspont 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úcspont pont 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.[2]

Irodalom[szerkesztés | forrásszöveg szerkesztése]

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

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

További információk[szerkesztés | forrásszöveg szerkesztése]