Königsbergi hidak

A Wikipédiából, a szabad lexikonból.

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

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.

[szerkesztés] 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, 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.

→ →

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-vonalnak nevezzük, illetve egy zárt Euler-vonalnak, a fenti feltételnek megfelelő bejárását 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 nyitott Euler-vonal legyen 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.

[szerkesztés] 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 kapcsolodó 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ő.

[szerkesztés] A königsbergi hidak 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.).^[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]