Legrövidebb út keresése gráfokon

A tétel rövid nézete
dc.contributor.advisorTurjányi, Sándor
dc.contributor.authorLosonczi, László
dc.contributor.departmentDE--TEK--Informatikai Karen
dc.date.accessioned2007-03-19T09:53:10Z
dc.date.available2007-03-19T09:53:10Z
dc.date.created2002
dc.date.issued2007-03-19T09:53:10Z
dc.description.abstractAz 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.en
dc.description.degreeBaen
dc.format.extent36en
dc.format.extent225791 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/2437/1313
dc.language.isohuen
dc.rights.accessipen
dc.subjectgráfelméleten
dc.subject.dspaceDEENK Témalista::Matematikaen
dc.subject.dspaceDEENK Témalista::Informatikaen
dc.titleLegrövidebb út keresése gráfokonen
Fájlok
Eredeti köteg (ORIGINAL bundle)
Megjelenítve 1 - 1 (Összesen 1)
Nincs kép
Név:
Szakdolgozat_32.pdf
Méret:
220.5 KB
Formátum:
Adobe Portable Document Format
Leírás:
Szakdolgozat
Megjelenítés
Engedélyek köteg
Megjelenítve 1 - 1 (Összesen 1)
Nincs kép
Név:
license.txt
Méret:
2.45 KB
Formátum:
Item-specific license agreed upon to submission
Leírás:
Letöltés
Gyűjtemények
Hallgatói dolgozatok (Informatikai Kar)