Metszési és diszjunktsági gráfok

Abstract

A dolgozatban olyan gráfokat vizsgálunk, melyeknek csúcsaihoz halmazok tartoznak úgy, hogy a szomszédság feltétele valamilyen módon a halmazok metszetéhez kapcsolódik. Például a diszjunktsági és metszési gráfokat, ahol pontosan azok a csúcsok szomszédosak, melyekhez rendelt halmazok diszjunktak, illetve nem diszjunktak. Megmutatjuk, hogy minden egyszerű gráf tekinthető metszési, ezáltal diszjunktsági gráfnak is, a csúcsokhoz megfelelő halmazokat rendelve. Majd azt vizsgáljuk, hogy ez a hozzárendelés hogyan tehető meg a lehető legkevesebb elem felhasználásával. Ezt követően olyan speciális metszési gráfoknak vizsgáljuk egyes tulajdonságait, amelyek csúcshalmaza egy véges halmaz hatványhalmaza. Foglalkozunk azzal a változattal is, ahol a szomszédos részhalmazok metszetének elemszáma egy rögzített szám. Az utolsó három fejezetben pedig olyan gráfokat, a a Kneser-, Johnson- és általánosított Johnson-gráfokat mutatjuk be, amelyeknek csúcsai egy véges halmaz összes, azonos elemszámú részhalmaza, és a szomszédság feltétele, hogy a részhalmazok metszetének elemszáma egy rögzített szám.