Mester kurzus tematika
2009, ősz
!!: 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
- Gráf, egyszerű gráf, hurokélnélküli gráf !!
- Fokszámok, fokszámsorozat !!
- Realizációs tételek ! *
- Fák, ághajtásos növekedés, levélcsípéses lebontás !!
- Adott fokszámsorozattal rendelkező fák száma *
- Cayley-tétel *
- 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 !
- Szomszédsági mátrix !!
- Permanens fogalma és a párosítások !
- Véletlen algoritmus telejes párosítás létezésére páros gráfban ! *
- MP(G), MP~(G) és a köztük lévő 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 ! *
- Edmonds-algoritmus *
- Tutte-akadály !!
- Tutte-akadály és teljes párosítások kapcsolata ! *
- 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 ! *
- Élkromatikus szám és páros számok ! *
- Hajós-operációk ! *
- Derékbőség !!
- Derékbőség és kromatikus szám kapcsolata ! *
- Síkgráfok tartományainak határa !!
- Euler-tétel ! *
- Topológikus részgráf, minor !!
- Kuratowski-tétel, Wagner-tétel ! *
- Metszési paraméter !!
- Metszési lemma *
- Metszési lemma alkalmazásai *
- Sajátértékek !!
- Sajátértékek és kromatikus szám kapcsolata *
- Moore-gráfok !
- (d,2)-Moore-gráfok *