Gráfelméleti algoritmusok – tételek és algoritmusok a párosítások témaköréből

A tétel rövid nézete
dc.contributor.advisorTurjányi, Sándor
dc.contributor.authorZákány, Irma Ildikó
dc.contributor.departmentDE--TEK--Természettudományi Karen
dc.date.accessioned2006-07-24T15:36:14Z
dc.date.available2006-07-24T15:36:14Z
dc.date.created2005
dc.date.issued2006-07-24T15:36:14Z
dc.description.abstractNapjainkban újból virágzásnak indult a gráfelmélet, köszönhetően annak, hogy az informatikában sok eredmény alkalmazásra talál, s ez ösztönzőleg hat a kutatásokra. Ez a tudományterület hatalmas kiterjedésű. Átfogó tárgyalása és ismerete emberfeletti munkát igényelne. Egy kis szeletébe próbálok betekintést nyújtani diplomamunkámmal, mégpedig a párosítások elméletébe. Éltem a feltételezéssel, hogy ezt a munkát egy a témában kevéssé járatos olvasó is a kezébe veheti, s ezért az I. fejezetet az alapfogalmak megismertetésének szenteltem. Bár első látásra sok fogalom került felsorolásra, mégsem jelenthet nagy nehézséget azok megértése, mivel egyszerűek, és elnevezéseik igen szemléletesek. A tudományág viszonylag fiatalnak számít a matematika ágai között, így gyakori, hogy ugyanazt az objektumot több különböző néven is fellelhetjük a szakirodalomban. A fejezet összeállítása során törekedtem arra, hogy a leggyakrabban használt terminológiával dolgozzak. A II. fejezetben térünk rá a párosítások témakörére. A szakkönyveket követve először páros gráfokkal foglalkozunk. Ezek olyan gráfok, amelyeknek csúcshalmaza két diszjunkt halmaz uniójára bontható, s élek csak a két halmaz elemeit köthetik össze. Az effajta gráfoknál még a tételek és definíciók egyszerűbb alakot öltenek. A II. fejezet 1. része ennek a gráftípusnak a bemutatására hivatott. A 2. részben kezdjük ténylegesen vizsgálni a párosításokat. Először páros, majd a 3. részben általános gráfok esetén vizsgálódunk. Párosítás adott gráf esetén több is lehet. Aki ezeknek a száma iránt érdeklődik, a 4. részben szerezhet információkat ezzel kapcsolatban, amely a párosítási polinomról szól. Érdekes kapcsolódási pontot jelent az algebra tudományterületéhez az, hogy polinomot tudunk definiálni párosításokhoz, amely ráadásul sok érdekes tulajdonsággal is rendelkezik. A III. fejezet jelenti diplomamunkám lényegi részét. Ebben kapunk választ arra az igen fontos kérdésre, hogy hogyan találhatunk maximális párosítást vagy teljes párosítást egy gráfban. Nagy örömmel tölt el az, hogy sok magyar matematikust üdvözölhetünk a tudományág jeles képviselői között. A fejezetet éppen ezért a König Dénestől származó úgynevezett „magyar módszerrel” indítottam. Erre épülnek Edmonds eredményei, majd ezt követően a Ford-Fulkerson algoritmus révén a folyamok elméletébe is kitekintünk. A fejezetet a kínai postás problémája zárja, amely már a példa párosítási algoritmusok alkalmazására is. A továbbiakban az ebben a témakörben született újabb eredményekből választottam. A IV. fejezetben olyan eredményeket igyekeztem bemutatni, amelyek révén a párosítások témakörének a matematika más területeivel való kapcsolatára láthatunk példát. Remélem diplomamunkám hagyományos szerepén túl segítséget is nyújt a téma iránt érdeklődők számára.en
dc.description.correctorN.I.
dc.description.degreeBaen
dc.format.extent40en
dc.format.extent450446 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/2437/223
dc.language.isohuen
dc.rightsno_restrictionen
dc.subjectpárosításen
dc.subjectteljes párosításen
dc.subjectmaximális párosításen
dc.subjectalgoritmusen
dc.subjectmagyar módszeren
dc.subjectgráfen
dc.subjectpáros gráfen
dc.subjectfolyamen
dc.titleGráfelméleti algoritmusok – tételek és algoritmusok a párosítások témakörébőlen
Fájlok
Eredeti köteg (ORIGINAL bundle)
Megjelenítve 1 - 1 (Összesen 1)
Nincs kép
Név:
Diplomamunka_667.pdf
Méret:
439.89 KB
Formátum:
Adobe Portable Document Format
Leírás:
Diplomamunka
Megjelenítés
Engedélyek köteg
Megjelenítve 1 - 1 (Összesen 1)
Nincs kép
Név:
license.txt
Méret:
2.72 KB
Formátum:
Item-specific license agreed upon to submission
Leírás:
Letöltés
Gyűjtemények
Hallgatói dolgozatok (Informatikai Kar)