!!: 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 !!
• 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étel ! *
• Párosítás, lefogás !!
• Párosítások és lefogások közötti kapcsolat !!
• Véletlen algoritmus teljes párositás létezésének tesztelésére páros gráfokban ! *
• Schwartz-lemma ! *
• 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 ! *
• 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 !!
• 4-szín-tétel és síkgráfok élszínezéseinek kapcsolata ! *
• Élkromatikus szám és a maximális fok kapcsolata ! *
• Vizing-tétel ! *
• 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 ! *
• 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 ! *
• Schur-tétel ! *
• r_k(n) függvény definíciója !!
• Erdős-Turán-sejtés/Szemerédi-tétel (csak kimondás)
• Turán-tétel ! *
• ext(n;T) függvény !!
• ext(n;F) becslései, ha F fa ! *
• Erdős-Stone-tétel (bizonyítás nélkül) ! *