Halmazrendszerek speciálkollégium, Hajnal Péter IX. 23. (1 óra)

Alapok

Definíció: Halmazrendszerek

Példa: Egyszerű gráfok, egyszerű gráfok egy-egy lehetséges hurokéllel az egyes csúcsoknál.

Definíció: Hipergráf (illeszkedési struktúra, illeszkedésgeometria)

Példa: 2^{V}, \binom{V}{k}, gráfok.

A speciálkollégiumban minden véges, kivéve ha másképp nem jelezzük.

Ábrázolás: Venn-diagramm.

⋆  ⋆  ⋆

Izomorfizmus

⋆  ⋆  ⋆

Alapinvariánsok: Pontok száma, élek száma, fokszámok, f-vektor.

⋆

Megjegyzés: Gráfok esetén a fokszám fogalom eltér a hipergráfként tekintett fokszámtól (hurokélek kettőt adnak a foksz’amhoz).

Definíció: Egy halmazfeletti multihalmazok halmaza, illetve a “párhuzamos éles definíció”: egy m : V ×E → függvény.

Definíció: Uniformitás.

⋆

Gráfelméleti analógiából vett optimalizálási kérdések. ν(H), τ(H), χ(H).

μ(H) bevezetése dualizálással.

Definíció: H halmazrendszer H^{∗} duálisa (általában hipergráf).

Független élek, lefogó pontok

Naív becslések

ν(H) és τ(H) becslése az alapparaméterekkel.

Mohó becslés

Mohó algoritmus outputjának mérete becsüli az optimumot.

A fedési feladatra fel is írjuk az algoritmust.

Az óra végén kimondjuk a problémát. Mit mondhatunk ezen becslés jóságára?