Kombinatorika I., matematikus szak, I. évfolyam
Tematika, 1999. õsz
- Gráfelméleti alapfogalmak:
egyszerû gráf, gráf, irányított gráf;
részgráf, feszített részgráf;
séta, vonal, út, kör egy G gráfban;
fokszám.
- Gráfok összefüggõsége:
összefüggõség, komponensek;
feszítõfák;
minimális összefüggõ gráfok,
fák ekvivalens definíciói;
fák növekedése, fák éleinek száma.
- Kétszeresen élösszefüggõ gráfok:
elvágó élek;
kétszeresen élösszefüggõ gráfok
ekvivalens definíciói;
kétszeresen élösszefüggõ komponensek;
kétszeresen élösszefüggõ gráfok fülfelbontása.
- Kétszeresen összefüggõ gráfok:
(csak kimondani az elhangzottakat!)
elvágó pontok;
kétszeresen összefüggõ gráfok
ekvivalens definíciói;
kétszeresen összefüggõ komponensek;
kétszeresen összefüggõ gráfok fülfelbontása.
- Magasabb fokú összefüggõség:
k-szorosan összefüggõ és
élösszefüggõ gráfok ekvivalens
definíciói és kapcsolatuk Menger-tételeivel.
Menger tételeinek kimondása és
az édiszjunkt utakra vonatkozó változat
bizonyítása.
- Párosítások:
párosítások fogalma;
páros gráfokra vonatkozó párosítási tételek
(Kõnig tételei, Hall-tétel, Frobenius-tétel);
javító utak;
magyar módszer és helyessége;
Kõnig-tétel bizonyítása;
Tutte-akadály, Tutte-tétel;
Berge-formula kimondása és a nyilvánvaló irány
azonosítása és indoklása.
- Vonalak, körök:
Euler-vonal, zárt Euler-vonal;
Euler-tétel;
Hamilton-kör, Hamilton-út;
akadályok Hamilton-kör létezésére;
Dirac-tétel.
- Független ponthalmazok:
független ponthalmazok, lefogó ponthalmazok,
klikkek és kapcsolatuk;
mohó algoritmus független ponthalmaz keresésére,
Turán-tétel.
- Gráfok színezései:
gráfok kromatikus száma;
kis kromatikus számú gráfok,
2-színezhetõ gráfok jellemzése;
gráfok kromatikus számának
és maximális fokszámának
kapcsolata, Brooks-tétel kimondása
és háromszorosan összefüggõ
gráf esetén a tétel bizonyítása;
gráfok kromatikus számának és a maximális
méretû klikk nagyságának kapcsolata,
példa háromszög nélküli nagy
kromatikus számú gráfra.
- Gráfelméleti problémák:
redukciók az elõadáson elhangzott példák alapján.
- Extremális gráfelmélet:
Turán tételének átfogalmazásai, Turán-gráfok és
a Turán-tétel erósebb változatának kimondása;
C4-et nem tartalmazó gráfok élszáma;
extremális gráfelmélet egy alkalmazása.
- Ramsey-elmélet:
Ramsey-számok, Ramsey-tétele;
Ramsey-tétel általánosításai;
Ramsey-számok alsó becslése;
Ramsey-tételének egy alkalmazása.
- Síkgráfok:
gráfok síkra rajzolása, íkgráfok;
síkra rajzolt gráfok, tartományok, Euler-formula;
topológikus részgráf, minor, Kuratowski-tétel kimondása;
síkgráfok színezése, ötszín tétel.
* * *
\noindent
- Halmazrendszerek alapfogalmai:
Fokszámok, fokszámok összegére vonatkozó tétel.
- Halmazrendszerek lefogási és független
élrendszereire vonatkozó problémák:
tau és nû paramétere, példa (pince folyosókkal...);
mohó algoritmus halmazrendszerek lefogására,
példa (vállalat dolgozói...)
Lovász tétele.
- Blokkrendszerek:
(v,k,l)-blokkrendszerek;
oszthatósági feltételek.
- Steiner-rendszerek:
Steiner-rendszerek létezésére vonatkozó szükséges
feltételek;
Steiner-rendszerek geometriai konstrukciói;
Steiner-rendszerek rekurzív konstrukciói;
Steiner-rendszerek létezésére vonatkozó tétel.
- Véges projektív síkok:
véges projektív síkok;
véges projektív síkok paramétere;
véges projektív síkok mint speciális blokkrendszerek.
- Halmazrendszerek extremális elmélete:
Sperner-rendszerek, Sperner tétele;
Erdõs--Ko--Rado-tétel.