A következő kombinatorika szeminárium ideje

november 22. (péntek), 10:45 (modulo a pesti vonat késése),

helye a szokásossá váló

Kalmár Intézet, Árpád tér, szemináriumi szoba (második emelet, a folyosó vége)

és előadása:

Pap Gyula (ELTE): Fenyők és k-fenyők lefogása

Egy irányított gráf egy feszítő részgráfját fenyőnek hívjuk, ha minden csúcs be-foka legfeljebb 1, és irányítatlan értelemben véve egy fa. Egy fenyőnek a 0-befokú csúcsát hívjuk gyökérpontnak. Egy adott D irányított gráfban könnyű eldönteni, létezik-e fenyő, sőt, Edmonds illetve Fulkerson munkái alapjána a súlyozott feladat is megoldható: egy adott élsúlyozott gráfban tudunk találni minimális költségű fenyőt. Megoldható mind a rögzített gyökérpontú változat, és a szabadon választható gyükérpontos változat is. Az előadásban a következő problémát tekintjük: adott élsúlyozott gráf esetén határozzunk meg egy minimális elemszámú élhalmazt, melyek lefogják az összes minimális költségű fenyőt - azaz egy olyan minimális elemszámú élhalmazt, melynek törlése "tönkretesz" minden minimális költségű fenyőt.

k-fenyőnek olyan részgráfot nevezünk, mely előáll k darab éldiszjunkt fenyő uniójaként. (A k fenyő gyökerei függetlenül, szabadon választható ebben a változatban.) Edmonds fenyőtétele alapján ismert, hogyan találunk egy adott irányított gráfban k-fenyő, illetve jellemezhetjük, mikor nem létezik ilyen. Az előadásban a k-fenyők lefogásával is foglalkozunk, azaz adott k és D esetén keresünk egy minimális élhalmazt, melyek törlése "tönkretesz" minden k-fenyőt.

Az említett két lefogási feladat legjobb tudomásunk szerint korábban meglepő módon megoldatlan volt; az előadásban polinomiális algoritmust adunk meg mindkettőre. A két algoritmus, bár jelentősen eltér egymástól, egy közös pontjuk az, hogy Bárász, Becker és Frank egy eredményére épít, mely szerint az úgynevezett "tömör" halmazok családja rendelkezik Helly-tulajdonsággal. Egy ponthalmazt tömörnek nevezünk, ha minden valódi részhalmazának nagyobb a be-foka.

Az előadásban bemutatott munka közös Bernáth Attilával.

Minden érdeklődőt szeretettel várunk,

Péter

Supported by TÁMOP-4.2.2.A-11/1/KONV-2012-0073, Telemedicine Oriented Research in the Fields of Mathematics, Informatics and Medical Sciences