A következő kombinatorika szeminárium ideje
helye a szokásossá váló
és előadá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