Turjányi, SándorLosonczi, László2007-03-192007-03-1920022007-03-19http://hdl.handle.net/2437/1313Az 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.36225791 bytesapplication/pdfhugráfelméletDEENK Témalista::MatematikaDEENK Témalista::Informatikaip