Informatikai és Hírközlési Minisztérium Oktatási Minisztérium Apache Php Mysql Fazekas Mihály Gyakorlóiskola
  Bejelentkezás
Üdvözöljük a Matematika portálon!  
Beharangozó: Frank András: Euler séták és általánosításaik!

Frank András

Optimális Euler-séták

Euler-séták és általánosításaik

2007. szeptember 25.

Matematikai népszerűsítő munkák egy közkedvelt feladata arra hívja fel az olvasót, hogy adott ,,rajz" vonalain a ceruza felemelése nélkül haladjon végig, minden vonalon pontosan egyszer, és térjen vissza a kiinduló pontba. A hagyomány szerint Königsberg város polgárai kértek fel L. Eulert, hogy adjon matematikai bizonyítékot arra, miért nem sikerül senkinek a városukat átszelő folyó két szigetét és a partokat összekötő hét hídon úgy végigmenni, hogy mindegyik hídon pontosan egyszer haladjunk át. Euler kimutatta, hogy a megoldhatóság azon múlik, hogy a szituációt reprezentáló gráfban vannak-e páratlan fokú csúcsok.

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

Mai szemmel nézve Euler eredménye igencsak egyszerű, ugyanakkor számos izgalmas általánosítás kiindulási pontjául szolgál. Például milyen feltétel mondható zárt Euler-séta létezésére, ha a gráf minden élének előre adott az iránya, amely előírja, hogy azon az élen merrefelé kell mennünk? Erre még nem nehéz rájönni, de ha irányított és irányítatlan élek egyaránt előfordulhatnak, akkor a zárt Euler-séta létezésének feltételét már kitalálni is nehéz, és akkor még a bizonyításról nem is szóltunk.

Amennyiben nem létezik Euler-séta, természetes megkérdezni, hogy mikor létezik a gráf éleinek olyan bejárása, ahol minden élen legalább egyszer végigmegyünk, de azon élek száma, amelyeken egynél többször legfeljebb 10 (vagy bármilyen előre megadott szám). Ennek a feladatnak a megoldásához már komoly elméletre van szükség.

Az előadás a gráfelmélet néhány alapvető optimalizálási problémája kapcsán bepillantást kíván nyújtani a kombinatorikus algoritmusok világába. Szeretném továbbá érzékeltetni, hogy gyakran a fentihez hasonló ártatlannak tűnő kérdések is izgalmas matematikai problémákhoz vezetnek.

Két egyszerű gyakorló példa:

1. Igazoljuk, hogy egy gráf éleit mindig lehet úgy irányítani, hogy minden csúcsra az oda bemenő élek száma és az onnan kilépő élek száma legfeljebb eggyel tér el.

2. Igazoljuk, hogy minden összefüggő gráfnak van olyan bejárása, amely minden élt egyszer vagy kétszer használ.

Kiemelt támogatónk 2006-ban:
Tigra Computer
Támogatóink 2003-ban:
Oktatási Minisztérium
Powered by:
Apache + Php + Mysql
Kapcsolat
hraskoa@fazekas.hu
Copyright © 2004-2010 Fazekas Mihály Fővárosi Gyakorló Általános Iskola és Gimnázium. Served by pingvin.