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
• Gráfok kódolásai
• Séta, vonal, út
• Séta-, vonal-, út-növelés
• Szomszédsági mátrix hatványai és séták kapcsolata
• összefüggóség tesztelésére vonatkozó algoritmus; mátrix hatványozásra vonatkozó szubrutin
• Három gráfokkal kapcsolatos reláció és ezek ekvivalenciareláció volta
• Csúcsok, élek elhagyása gráfokból; részgráf, feszített részgráf, feszítő részgráf
• Gráfok komponensei
• összefüggő gráfok; minimális feszítő részgráf keresése
• Fák; ekvivalens definíciók; ághajtás
• Minimális költségű feszítőfa keresése és ennek általánosítása; példák
• Mohó algoritmus maximális költségű megengedett halmaz keresésére; optimális megoldás megtalálására vonatkozó szükséges és elégséges feltétel
• Gráfok kétszeresen élösszefüggő komponensei
• Kétszeresen élösszefüggő gráfok jellemzései; fülfelbontás
• Gráfok kétszeresen összefüggő komponensei
• Kétszeresen összefüggő gráfok jellemzései; fülfelbontás
• Euler-vonal fogalma
• Vonal növelései
• Euler-tétel
• Kínai postás problémája és az erre vonatkozó algoritmus
• Hamilton-kör, Hamilton-út
• Utak növelése
• Hosszú út keresésére vonatkozó algoritmusok; Dirac-tétel
• Közelítő algoritmusok
• Utazó ügynök problémája; az inputra vonatkozó háromszög egyenlőtlenség
• Két algoritmus az utazó ügynök problémára és approximációs tulajdonságuk analízise
• Gráfok színezése
• Két-színezhető gráfok jellemzése
• Mohó színezési algoritmus; heurisztikák az algoritmusban szereplő sorrend választására
• Alkalmazások: nem reguláris összefüggő gráfok; háromszorosan összefüggő gráfok, intervallumgráfok, síkgráfok színezése
• átszínezések
• Alkalmazások: síkgráfok színezése
• Példák háromszög nélküli, nagy kromatikus számú gráfokra
• Párosítások
• 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és páros gráfokban: Magyar módszer
• Páros gráfokra vonatkozó párosítási tételek
• Párosítási feladat egészértékű programozási feladatként való megfogalmazása és ennek LP relaxációja
• Páros gráfok esetén a relaxáció megoldása optimális a párosít'asi problémára (páros gráfok pont-él illeszkedési mátrixára vonatkozó tétel)
• Páros gráfokban teljes párosítás létezésével kapcsolatos lineáris algebrai állítások
• Véletlen algoritmus páros gráfban teljes párosítás létezésének tesztelése
• Javító út keresése gráfokban: 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
• Független ponthalmaz
• 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