Gráfparaméterek, párosítások

A témakör tartalma

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.



Független és lefogó ponthalmaz, Gallai első tétele

Független és lefogó élhalmaz, Gallai második tétele

Gráfparaméterek

Párosítás, maximális párosítás, teljes párosítás

Teljes párosítás, Tutte-tétel

Különböző trükkök a gráfparaméterek kiszámolására

Furmányos gráfparaméteres egyenlőtlenségek

FELADAT | Gráfparaméterek

FELADAT | Gráfparaméterek

FELADAT | Gráfparaméterek

FELADAT | Gráfparaméterek

FELADAT | Gráfparaméterek

FELADAT | Gráfparaméterek

FELADAT | Gráfparaméterek