A végső tematika az utolsó előadás végén pontosítva lesz.

• 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 elhagyása gráfokból, feszített részgráf
• Gráfok komponensei
• Összefüggő gráfok
• Vonal, Euler-vonal fogalma
• Vonal növelései
• Euler-tétel
• Minimális, az összes pontot tartalmazó, összefüggő részgráf keresése összefüggő gráfokban, feszítőfa
• Élek elhagyása gráfokból, feszítő részgráf
• Út, kör
• Hamilton-kör, Hamilton-út
• Utak növelése
• Hosszú út keresésére vonatkozó algoritmusok; Dirac-tétel
• Fák; ekvivalens definíciók; ághajtás
• Minimális költségű feszítőfa keresése
• Kínai postás problémája és az erre vonatkozó algoritmus
• Utazó ügynök problémája; az inputra vonatkozó háromszög egyenlőtlenség
• Közelítő algoritmusok
• Közelítő algoritmus az utazó ügynök problémára és approximációs tulajdonságának analízise
• Gráfok színezése
• 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
• Átszínezések
• Alkalmazások: síkgráfok színezése
• Példa háromszög nélküli, nagy kromatikus számú gráfokra
• Párosítások
• Lefogó ponthalmazok
• Párosítások növelései, Berge-tétel: ha egy párosítás nem maximális elemszámú, akkor javító úttal növelhető
• Javító út keresése javító út kezdemények növelésével
• A keresés teljes páros gráfokban: Magyar módszer
• Kőnig-akadály
• Páros gráfokra vonatkozó párosítási tételek
• 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
• Független ponthalmaz
• Mohó algoritmus független ponthalmaz keresésére és ennek analízise
• Módosított mohó algoritmus független ponthalmaz keresésére és ennek analízise
• Turán-gráfok; Turán-tétel kimondása
• Ramsey-számok
• Ramsey-tétel
• Ramsey-tétel egy alkalmazása