Kromatikus szám, klikk, perfekt gráfok
Itt mindent megtudhatsz a gráfok kromatikus számáról. Elmeséljük, mit is jelent a kromatikus szám pontosan, hogyan kell kiszámolni, mire kell figyelni. Megnézzük, hogy mi az a klikk, és mi köze van a klikknek a kromatikus számhoz. Gyorsan és egyszerűen megtudhatod, hogy mi az a klikk, és mit jelent egy gráf klikkszáma. Megnézzük, hogyan kell kiszámolni, mi a kapcsolat a klikkszám és a kromatikus szám között, és kiderül, hogy vannak olyan perfekt gráfok, ahol a klikkszám és a kromatikus szám megegyezik. Megtudod, mit jelent az, hogy feszített részgráf, mik azok a perfekt gráfok, hogyan lehet őket felismerni. Megnézzük a perfekt gráfok klikkszámát és kromatikus számát, és kiderül néhány nagyon izgalmas dolog. Megnézheted, mit jelent a gráfok mohó színezése, hogyan kell elkészíteni egy gráf mohó színezését, és ez alapján becslést adni a kromatikus számra. A kromatikus szám alsó és felső becslése, példák. Az is kiderül, hogy mi az a Brooks-tétel. Megnézheted, mi az élkromatikus szám, hogyan lehet meghatározni egy gráf élkromatikus számát. Kiderül, hogyan működik a Vizing-tétel, és hogyan használhatjuk az élkromatikus szám kiszámolására. Élszínezés feladatok, megoldással, gráfok élkromatikus száma és élszínezése. Elmeséljük, mik azok az intervallumgráfok, hogyan keletkeznek, és mi az értelmük. Megnézzük az intervallumgráfok tulajdonságait, és azt, hogyan lehet egy gráfról eldönteni, hogy intervallumgráf-e vagy sem. Intervallumgráf feladatok megoldással. Ráadásul azt is megnézzük, hogyan kell kiszámolni egy páros gráf élkromatikus számát és kromatikus számát. Feladatok páros gráfok kromatikus számaival kapcsolatban, König Dénes tétele. Végezetül pedig röviden és szuper-érthetően elmeséljük, mi az a Mycielski-konstrukció, mi köze van a gráfok színezéséhez, a kromatikus számhoz és a klikkszámhoz. Mycielski gráfok, Grötzsch gráf.
