Diszkrét matematika mesterkurzus tematika
2010, ősz
Jelölések:
!!: Fontos definíció, TUDNI KELL
!: Alapösszefüggés
! *: [általában] Tétel, kimondani tudni kell, ha van triviális iránya, akkor azt is tudjuk azonosítani, de bizonyítása csak
akkor, ha a többi dolog már jól megy
*: Csak akkor, ha a többi dolog jól megy
Tematika:
- Gráf, egyszerű gráf, hurokélnélküli gráf !!
- Fokszámok, fokszámsorozat !!
- Realizációs tételek ! *
- Pont-él illeszkedési mátrix !!
- Pont-él illeszkedési mátrix négyzetes aldeterminánsai *
- Kirchoff-tétel ! *
- Hálózat, folyam, folyam értéke, javító út (folyamokra),
vágás, vágás kapacitása !!
- Javító út léte és a folyam optimalitása közötti kapcsolat !
- Folyam értéke és vágás kapacitása közötti kapcsolat !
- MFMC tétel ! *
- Ford-Fulkerson folyamalgoritmus *
- Ford-Fulkerson folyamalgoritmus futása, ha minden kapacitás
egész ! *
- k-szorosan élösszefüggő gráfok, k-szorosan összefüggő gráfok !!
- Ponthalmaz határa !!
- Ponthalmaz határának kapcslata az élösszefüggéssel !
- Minimális k-szorosan élösszefüggő gráfok *
- Élek összecsippentése !!
- Élek összecsippentése és kapcsolatuk az élösszefüggéssel ! **
- Szubmoduláris egyenlőtlenség ! *
- Menger tétel kimondása !
- Menger-tétel *
- Párosítás, lefogás !!
- Párosítások és lefogások közötti kapcsolat !
- Javíto út párosításokra !!
- Javító út léte és a párosítás optimalitása közötti kapcsolat ! *
- Javító út keresés javító útkezedemények mohó növelesével
(magyar módszer): gyökerek, címkék (külső/belső), kereső erdő,
sikeres/sikertelen keresés !!
-
- Kőnig-akadály !!
- Kőnig-akadály és viszonya a legnagyobb párosít'as méretéhez ! *
- Edmonds-algoritmus *
- Tutte-akadály !!
- Tutte-akadály és teljes párosítások kapcsolata ! *
- Tutte-tétel ! *
- Tutte-akadály viszonya a legnagyobb párosítás méretéhez ! *
- Berge-formula ! *
- Csúcsszínezés, élszínezés, kromatikus szám, élkromatikus szám !!
- Petersen-gráf !!
- Síkgráfok: lerajzolás, szép lerajzolás !!
- Síkgráfok tartomány színezése, dualitás !!
- Élkromatikus szám és a maximális fok kapcsolata ! *
- Hajós-operációk !!
- Hajós-operációk viszonya a nem-k-színezhetőséggel ! *
- Derékbőség !!
- Derékbőség és kromatikus szám kapcsolata ! *
- K5 és K3,3 nem síkgráfok !!
- Topológikus részgráf, minor !!
- Kuratowski-tétel, Wagner-tétel ! *
- Metszési paraméter !!
- Metszési lemma *
- Metszési lemma alkalmazásai *
- Schur-tétel ! *
- Van der Waerden tétel ! *
- rk(n) függvény !!
- Erdős-Turán-sejtés, Szemerédi-tétel ! *
- ext(n;T) függvény !!
- ext(n;F) becslései, ha F fa
- Erdős-Stone-tétel ! *
- ext(n;C2k) becslései ! *