Feladat: létezik-e lehetséges útvonal

Königsberg városa a Pregel folyó partjain és szigetein épült. A város XVIII. századi hídjait az ábra mutatja. Abban az időben a városban találós kérdésként gondolkodtak azon, hogy lehet-e egy sétát úgy tervezni, hogy valaki elindul a lakásából, és pontosan egyszer átsétál a városnak mind a hét hídján, és visszatér a lakásába.

Megoldás létezik-e lehetséges útvonal

A hidak Ezt hogyan láthatnánk be? Elemezzük az ábrát. Fontos-e az, hogy melyik híd köti össze a két szigetet, és melyek vezetnek az egyik partról a szigetre? Más részlet, például a hidak hossza, a szigetek területe számottevő-e? Ezek a kérdések feleslegesek, mert a probléma szempontjából lényegtelen dolgokra irányítják a figyelmet. A feladatban mindössze a szárazföldek és a hidak fontosak. Ha csak ezeket vesszük figyelembe, akkor ábránka másik ábra lesz. Ezen az ábrán a pontok a szárazföldeket, két pontot összekötő vonal pedig egy-egy hidat jelképez.

Ha a második ábrát nézzük, akkor a königsbergi séta helyett kérdésünk a következő lehet: Az ábrán látható vonalat ceruzával megrajzolhatnánk-e úgy, hogy az egyik pontjából elindulva minden vonalon pontosan egyszer haladunk végig, majd visszatérünk a kiindulási pontunkhoz, közben ceruzánkat nem emeljük fel a papírról?

Ha rajzunkat így kezdjük el, akkor rajzolás közben pont-vonal-pont-vonal-pont-... felváltva követik egymást. A végén a kiindulási ponthoz kell visszajutnunk, emiatt minden pontban páros számú vonal futna össze. Az ábrán (azaz a königsbergi térképen) nem ezt látjuk, ott minden pontban páratlan számú él fut össze.

Ezért ilyen sétát nem tervezhetünk.

Az előző ábra könnyűvé tette a kérdés tisztázását. Ezért ezzel az ábrázolási móddal érdemes külön foglalkoznunk. Az ilyen ábráknak önálló nevet is adunk, gráfnak nevezzük.

A hidak sematikus ábrája

Euler

Euler 1736-ban írt egyik tanulmányában megmutatta, hogy a „königsbergi séta” megoldhatatlan, azaz nem lehet olyan sétát tervezni, amely mind a hét hídon pontosan egyszer vezetne át.

L. Euler (1707 -1783) svájci születésű matematikus, aki hosszú ideig Szentpétervárott dolgozott, a matematika sok területén maradandót alkotott. Nagy jelentőségű alkotásai mellett szórakoztató matematikai feladatok tisztázásával is foglalkozott.