Gráfparaméterek, párosítások
Itt szuper érthetően elmeséljük, hogy mi az a független ponthalmaz és lefogó ponthalmaz, hogyan lehet ezeket megkeresni egy gráfban, és milyen összefüggések vannak a gráfparaméterek között. Megnézzük, mennyi lehet a független ponthalmazok maximális száma és a lefogó ponthalmazok minimális száma. Gallai első tétele. Azt is elmeséljük, hogy mi az a független élhalmaz és lefogó élhalmaz, hogyan lehet ezeket megkeresni egy gráfban, és milyen összefüggések vannak a gráfparaméterek között. Megnézzük, mennyi lehet a független élhalmazok maximális száma és a lefogó élhalmazok minimális száma. Gallai második tétele. Mindent megtudhatsz a gráfparaméterekről, A független és lefogó ponthalmazok és élhalmazok elemszámáról, a Gallai tételekről. Megnézzük, hogyan lehet különböző gráfoknál kiszámolni a gráfparaméterek értékét. Gráfparaméteres feladatok megoldással. Megnézheted, mit jelent a párosítás, mi az a teljes párosítás, mit jelent a maximális párosítás. Megnézzük az alternáló utas algoritmust a javító utak keresésére, amivel egy párosítás javítható. Hogyan lehet a gráfokat tesztelni, hogy van-e bennük maximális párosítás? Megnézzük, miről szól a Tutte-tétel, és nézünk rá néhány példát. Párosítás gráfokban, maximális párosítás keresése alternáló utas algoritmussal. Végezetül gráfparaméterekkel kapcsolatos egyenlőtlenségekről lesz szó. Megnézzük, hogyan lehet egyszerűen és szemléletesen bizonyítani ezeket a gráfparaméterekkel kapcsolatos állításokat. Független és lefogó ponthalmaz és élhalmaz elemszáma, Gallai tételek és még sok izgalmas dolog.
