!!: 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

• Egyszerű gráf, hurokél-nélküli gráf, gráf fogalma !!
• Fokszám fogalma, fokszámokra vonatkozó egyszerű állítások !!
• Séta !!
• Elérhetőség reláció és ennek ekvivalenciareláció volta !!
• Csúcsok és élek elhagyása gráfokból, feszített részgráf, részgráf !!
• Gráfok komponensei !!
• Összefüggő gráfok !!
• Fák; ekvivalens definíciók !!
• Feszítőfa !!
• Ághajtás !!
• Szomszédsági mátrix !!
• Szomszédsági mátrix hatványaiban szereplő számok gráfelméleti értelmezése *
• Pont-él-illeszkedési mátrix !!
• Pont-él-illeszkedési mátrix aldeterminánsai *
• Kirchoff-tétel *!
• Teljes párosítás, páros gráf !!
• Schwartz-lemma *
• Véletlen algoritmus teljes párosítás létezésének tesztelésére !!
• Az analizís !*
• Vonal, Euler-vonal fogalma !!
• Vonal növelései !*
• Euler-tétel !*
• Kínai postás probléma !!
• A kínai postás probléma átfogalmázása párosító útrendszer keresésére !*
• Algoritmus a kínai postás problémára *
• Út, kör !!
• Hamilton-kör, Hamilton-út !!
• Utak növelése !!
• Utak csavarása
• Hosszú út keresésére vonatkozó algoritmus; Dirac-tétel !*
• Utazóügynök probléma !!
• Utazóügynök probléma háromszög egyenlőtlenséget teljesítő inputtal !!
• Approximációs algoritmus minimalizálási/maximalizálási feladatra !!
• 2-approximációs algoritmus !*
• 1.5-approximációs algoritmus !*
• Hálózatok, folyamok, vágás, folyam értéke, vágás kapacitása !!
• Egy folyam értéke és egy vágás kapacitása közötti kapcsolat !*
• Javító út egy folyamra !!
• Javító utas javítás !*
• A folyamok alaptétele !*
• Ford-Fulkerson-algoritmus !!
• MFMC tétel !*
• Egész értékú kapacitásfüggvény esete !*
• Kőnig-tétel !*
• Menger-tételei és az egyszerű irány azonosítása, indoklása !!
• k-szorosan élösszefüggő, k-szorosan összefüggő gráfok karakterizációja !*
• Párosítások !!
• Lefogó ponthalmazok és kapcsolata a párosításokkal !!
• Javító út (párosításra vonatkozó) !!
• Kőnig-akadály !!
• Páros gráfokra vonatkozó párosítási tételek !*
• Magyar-módszer !*
• Edmonds-algoritmus !*
• Tutte-akadály fogalma; Tutte-tétel kimondása és a nyilvánvaló irány indoklása !!
• Berge-formula és a két oldala közötti nyilvánvaló egyenlőtlenség indoklása !!
• Gráfok színezése, kromatikus szám !!
• Két-színezhető gráfok jellemzése !*
• Mohó színezési algoritmus !!
• Alkalmazások: nem reguláris összefüggő gráfok, síkgráfok színezése !*
• Brooks tétel kimondása *
• Kempe-átszínzés: síkgráfok öt-színezése !*
• Klikkek és kapcsolata a színezéssel !!
• Példa háromszög nélküli, nagy kromatikus számú gráfokra !*
• Független ponthalmaz, klikkek, komplementer gráf !!
• Mohó algoritmus nagy független halmaz keresésére !!
• Mohó algoritmus amalízise !*
• Mohó algoritmus módosítása !!
• Módosított mohó algoritmus amalízise *
• Turán-gráfok; Turán-tétel !*
• Ramsey-számok !!
• Ramsey-tétel !*