Gráfelmélet elemei tematika

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
• Feladat: Kirándulók a tó két prtján ...
• Elérhetőség reláció és ennek 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ő, összefüggő részgráf keresése
• Fák; ekvivalens definíciók; ághajtás
• Feladat: Táblázat különböző sorokkal ...
• Vonal, Euler-vonal fogalma
• Vonal növelései
• Euler-tétel
• Hamilton-kör, Hamilton-út
• Utak növelése
• Hosszú út keresésére vonatkozó algoritmusok; Dirac-tétel
• Pósa-tétel
• 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; háromszorosan összefüggő gráfok, síkgráfok színezése
• Feladat: Egyenesek metszéseinek színezése ...
• Átszínezések
• Alkalmazások: síkgráfok színezése
• Klikk, klikkek és színez'esek kapcsolata
• Feladat: Körök és színezéseik ...
• 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
• Kőnig-akadály
• Páros gráfokra vonatkozó párosítási tételek
• Tutte-akadály
• Tutte-tétel, Berge-formula
• Független ponthalmaz, lefogó ponthalmaz, klikkek fogalma és kapcsolatuk
• Turán-gráfok
• Turán-tétel kimondása és bizonyítása az előadáson ismertetett egyszerű esetben
• Ramsey-számok
• Ramsey-tétel