Kombinatorika és gráfelmélet
Egy hosszú előadásjegyzet 10 kisebb részre bontva: a kombinatorika alapjaitól (skatulya-elv, permutációk, variációk, kombinációk, binomiális azonosságok) a gráfelmélet fő fejezeteiig (Euler- és Hamilton-körök, fák, síkbarajzolhatóság, színezések, Ramsey-számok, gráfmátrixok és irányított gráfok).
1. Alapfogalmak és a skatulya-elv
Halmazok, multihalmazok, rendezett n-esek, függvények, relációk, ekvivalenciareláció, skatulya-elv és alkalmazásai.
2. Permutációk, variációk, kombinációk
Faktoriális, Stirling-formula, binomiális együttható, Pascal-háromszög, ismétlés nélküli és ismétléses permutáció, variáció, kombináció.
3. Binomiális együtthatók és azonosságaik
Leképezések száma, szimmetria, elnyelési tulajdonságok, sorösszegek, Vandermonde- és hokiütő-azonosság, binomiális és polinomiális tétel.
4. Permutációk paritása, ciklusok és a szita-formula
Inverzió és paritás, szimmetrikus csoport, ciklusfelbontás, tartalmazás-kizárás elve, Euler-féle φ-függvény, fixpontmentes permutációk.
5. Gráfelméleti alapfogalmak, fokszámok, Havel–Hakimi-tétel
Gráf, fokszám, kézfogási tétel, Havel–Hakimi-tétel, teljes gráfok, komplementer gráf, él/csúcs törlése, él összehúzása.
6. Részgráfok, izomorfizmus, séták és utak
Feszítő/feszített részgráf, klikk, izomorfizmus, séta/vonal/út/kör, összefüggőség, komponens, távolság.
7. Euler-vonalak, Hamilton-körök, fák
Euler zárt/nyílt tétele, Fleury-módszer, Hamilton-út/kör, Ore- és Dirac-tétel, nyakláncszabály, fák és erdők.
8. Páros gráfok és síkbarajzolhatóság
Páros gráfok jellemzési tételei, teljes páros gráf, Euler-formula, Platóni testek, élfelosztás/élösszevonás, Kuratowski- és Fáry–Wagner-tétel.
9. Gráfszínezés és Ramsey-számok
Kromatikus szám és polinom, Brooks-tétel, Ötszín-tétel, kromatikus index, kétszínes és többszínes Ramsey-számok.
10. Gráfok mátrixai és irányított gráfok
Szomszédsági és illeszkedési mátrix, irányított gráfok, irányított Euler-vonal és Hamilton-kör, DAG-ok, topologikus sorrend.