Legrövidebb út keresése gráfokon

Dátum
2007-03-19T09:53:10Z
Folyóirat címe
Folyóirat ISSN
Kötet címe (évfolyam száma)
Kiadó
Absztrakt

Az első gráfelméleti munkát – amely 1736-ban jelent meg – a híres svájci matematikus, Euler írta. A gráfelmélet kezdetben – matematikai szempontból nézve – meglehetősen jelentéktelennek látszott, mivel jórészt csak szórakoztató rejtvényekkel foglalkozott. A matematikának – és különösen alkalmazásainak – újabb fejlődése azonban hatalmas lendületet adott a gráfelméletnek. Az elektromos hálózatok és a molekuláris diagramok körében már a 19. században is alkalmaztak gráfokat. Jelenleg viszont a tiszta matematikának is vannak olyan fejezetei (mint például a matematikai relációk elmélete), amelyekben a gráfelmélet természetes segédeszköz. Emellett alkalmazzák sok gyakorlati jellegű probléma megoldásában is: ilyenek például a különböző párosítások, szállítási feladatok, csővezeték-rendszerek áramlási problémái és az általánosságban „programozásnak” nevezett feladatkörök. Némileg azért – ha nem is nagy súllyal – a rejtvények is megmaradtak a gráfelmélettel foglalkozó munkákban, elegendő itt (többek között) a nevezetes négyszínsejtésre gondolnunk. Szakdolgozatomban e nagy terület egy kis – de a gyakorlatban egyre jelentősebb – részével foglalkozom: a legrövidebb útkeresés problémájával. Fontosságára utal az is, hogy a gráfelmélet e területének igen nagy szakirodalma van. Jónéhányan adtak algoritmust a különböző gráftípusokhoz, ezekből a fontosabbakkal én is kiemelten foglakozom dolgozatom vonatkozó fejezeteiben. Szakmai feldolgozottsága ellenére a gráfelmélet a középiskolai oktatásban csekély szerepet kap. Igaz, hogy érettségi témakör, de már régóta nem volt ilyen feladat a vizsgákon. Ezért néhány helyen idő hiányában nem is foglalkoznak vele, pedig a gráfelméletet „látványossága” és a mindennapi életbe visszavezethető problémái miatt szívesen fogadná a legtöbb matematika iránt érdeklődő középiskolás is. Ezért a dolgozatom első részében ezt a réteget kívánom megszólítani, így megadom a megértéshez szükséges alapvető gráfelméleti fogalmakat. Ezek segítségével azok is könnyen megérthetik az itt leírtakat, akik eddig még nem találkoztak a matematika ezen részével. Munkám következő két fejezetében elsőként a súlyozatlan, majd a súlyozott gráfokra vonatkozó fontosabb algoritmusokat tárgyalom; végül az utolsó (negyedik) részben felvázolok néhány olyan problémát, amelyeket könnyen vissza lehet vezetni a tanult algoritmusokra.

Leírás
Kulcsszavak
gráfelmélet
Forrás