Gráfok és matroidok kapcsolatai

OData támogatás
Konzulens:
Dr. Recski András
Számítástudományi és Információelméleti Tanszék

A matroidokat bizonyos értelemben tekinthetjük a mátrixok (és a gráfok) általánosításának, valójában azonban arról van szó, hogy a lineáris függetlenség koncepcióját terjesztjük ki egy axiómarendszerrel meghatározott részhalmazrendszerre. Kutatásuk a matematika számos területén vezethet mély eredményekhez: a lineáris algebra általánosításán túl sikerrel vethetok be kombinatorikai (kombinatorikus optimalizálási) és gráfelméleti környezetben is.

A dolgozat célja a matroidokkal kapcsolatos legfontosabb fogalmak számbavételén keresztül kaput nyitni egy, a jövobeni tervek szerint késobb nagy alapossággal tárgyalandó terület, egy bizonyos matroidcsalád felé: ezek azok a matroidok, amelyek definícióját különféle gráftípusok segítségével adhatjuk meg. Jelen munka végére jutunk el ennek a témakörnek a talán legeklatánsabb, legjobban feldolgozott példájához, a transzverzális matroidhoz. Addig azonban hosszú út vezet, hiszen csak a fogalmak precíz és alapos bemutatásán keresztül van lehetoség megérteni a matroidok jelentését, jelentoségét, viszonyát a gráfelmélet, a lineáris algebra és a kombinatorika ismert fogalmaihoz.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.