Gráfelméleti algoritmusok
| dc.contributor.advisor | Turjányi, Sándor | |
| dc.contributor.author | Breszkócs, Péter Lajos | |
| dc.contributor.department | DE--TEK--Természettudományi és Technológiai Kar--Matematikai Intézet | hu_HU |
| dc.date.accessioned | 2010-05-07T07:29:32Z | |
| dc.date.available | 2010-05-07T07:29:32Z | |
| dc.date.created | 2010-05-06 | |
| dc.date.issued | 2010-05-07T07:29:32Z | |
| dc.description.abstract | Az 1. fejezet első részét a gráfelméleti alapfogalmak bevezetésének szenteltem. Ennek elsődleges célja, hogy a témában kevésbé járatos olvasó számára is egyszerűbbé váljon az ezt követő, esetleg nehezebbnek tűnő fejezetek megértése is. A fejezet második része főként a 3. fejezetben előforduló fogalmak megértését segíti, de megemlítjük a híres P=NP problémát is. A 2. fejezet három részre tagolódik. Az első részben a páros gráfokkal foglalkozom. A páros gráfok olyan gráfok, amelyeknél a csúcspontok két diszjunkt halmaz uniójára bonthatók úgy, hogy az összes élre teljesül, hogy az egyik végpont az egyik halmazban, míg a másik végpont a másik halmazban van. A fejezet második része e páros gráfok párosításaival foglalkozik. Párosítás nem csak páros gráfok esetén létezhet, hanem általános gráfok esetén is. Ennek tárgyalására hivatott a harmadik alfejezet. Ebben a részben két híres magyar matematikus Kőnig Dénes és Egerváry Jenő tiszteletére magyar-módszernek elnevezett eljárás ismertetése következik. 3. fejezetben érünk el, diplomamunkám legfontosabb részéhez, amelyben említést teszek gráfok kiterjeszthetőségéről is. Ebben a fejezetben vizsgálom az úgynevezett karom-mentes gráfok BM-kiterjeszthetőségéhez szükséges és elegendő feltételeket. Bemutatom még az NP illetve co-NP problémákat is, ahol NP probléma alatt olyan problémát értünk, amelynek megoldására létezik olyan algoritmus amely polinomiális idő alatt megoldja azt. Végül pár szót ejtek néhány további, ebben a témában vizsgálatra érdemes kérdésekről is. | hu_HU |
| dc.description.corrector | gj | |
| dc.description.course | matematikus | hu_HU |
| dc.description.degree | régi képzés | hu_HU |
| dc.format.extent | 35 | hu_HU |
| dc.identifier.uri | http://hdl.handle.net/2437/95722 | |
| dc.language.iso | hu | hu_HU |
| dc.subject | NP probléma | hu_HU |
| dc.subject | BM kiterjeszthetőség | hu_HU |
| dc.subject.dspace | DEENK Témalista::Matematika | hu_HU |
| dc.title | Gráfelméleti algoritmusok | hu_HU |