!!: 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 (amennyiben szerepelt előadáson) 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 !!
• 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 !!
• Menger tételei ! *
• Csúcsszínezés, élszínezés, kromatikus szám, élkromatikus szám !!
• 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 ! *
• Vizing-tétel ! *
• Síkgráfok: lerajzolás, szép lerajzolás !!
• Síkgráfok tartomány színezése, dualitás !!
• 4-szín-tétel és síkgráfok élszínezéseinek kapcsolata ! *
• Petersen-gráf !!
• Élkromatikus szám és a maximális fok kapcsolata ! *
• K₅ és K_3,3 nem síkgráfok ! *
• Topológikus részgráf, minor !!
• Kuratowski-tétel, Wagner-tétel ! *
• Szepen lerajzolt gráfok tartományainak határa
• Metszési paraméter !!
• Metszési lemma ! *
• Metszési lemma alkalmazásai *
• Módosított mohó algoritmus nagy klikk keresésére !!
• Turán-gráfok !!
• ext(n;T) függvény !!
• ext(n;F) becslései, ha F fa ! *
• Erdős-Stone-tétel ! * (csak kimondás, egyszerű irány)
• Ramsey-algoritmus (2 szín) !!
• Ramsey-számok definíciója (két szín, c szín, k-asok szíbezése) !!
• Schur-tétel ! *
• Van der Waerden tétele (csak kimondás) *
• Sűrűségi változatok, r_k(n) függvény definíciója !!
• Erdős-Turán-sejtés, Szemerédi-tétel *
• Párosítás ok gráfokban!!
• Véletlen algoritmus teljes párositás létezésének tesztelésére páros gráfokban ! *
• Schwartz-lemma ! *
• Párosítási feladat lineárisalgebrai megfogalmazása és lineráris programozási relaxációja
• Mohó párosítási algoritmus és analízise !!
• Lefogó ponthalmazok, párosítások és lefogások közötti kapcsolat !!
• Javító ú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ás 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 ! *
• Gráfok sajátértékei !!
• Gráfok sajátértékeinak alaptulajdonságai ! *
• A kromatikus szám becslése (Hoffman-tétel) ! *
• Moore-gráfok *
• Barátság tétel *
• Erősen reguláris gráfok !!