Nekikezdtem a záróvizsga utáni örömmatekozásnak, vagyis amikor olyan matekot tanulok, amit én szeretnék (érthető módon statisztikát pl. nagyon ritkán). Ennek egyik első lépéseként hétfőn elmentem egy Egres-szemináriumra, amelynek témája Kamiyama azon kérdése volt, amelyet Frank amúgy is említett már nekem, merthogy kapcsolódik a szakdolgozatomhoz: egy irányított gráfban adott költségfüggvény mellett legalább hány élt kell törölni, hogy a minimális r-fenyő (ez a Frank-féle magyarítása az arborescence szónak, azaz r-ből gyökereztetett fát jelent) költsége nőjön. Vagyis a minimális költségű fenyők egy minimális élfedését keressük.
Még négy ezzel kapcsolatos probléma is felmerül, itt már költségfüggvény nélkül:
- Egy, a csúcsokon adott F lamináris halmazrendszer elemeibe pontosan egyszer belépő fenyőket akarjuk lefogni
- Ugyanez, egyelemű F={F} esetén
- F=V-r
- F=V-r, r-ből mindenhova vezet él, és ezeket az éleket nem törölhetjük.
Itt Fulkerson algoritmusa szerint az eredeti kérdés visszavezethető 1-re, míg a többi mind speciális esete az eggyel előtte levőnek. A 4-es probléma átfogalmazva a V-r csúcshalmaz által feszített részgráf összes -- tetszőleges gyökerű -- fenyőjét szeretné lefogni. Könnyen látható, hogy ahhoz, hogy egyáltalán ne legyen fenyő a gráfban, kell hogy legyen két diszjunkt, 0 befokú halmaz. Még könnyebb, hogy ez elégséges feltétel is. Elég tehát megkeresni G[V-r]-en két diszjunkt, minimális befokösszegű halmazt. Ez pedig opkutos körökben egy közepesen ismert feladat (tehát Frank ismeri, néha föladja a diákjainak, az Egres-szeminárium résztvevői viszont nem tudták volna kapásból, hogy hogy van), visszavezethető egy folyam minimális vágására.
Ennyi információval vágtunk neki a dolognak, Erika mondta is, hogy ő kb öt percesnek tervezte a megbeszélést, aztán lesz ami lesz. Lett. Összesen több mint négy órát voltunk ott. Első körben felmerült, hogy mi a helyzet irányítatlan gráfok esetén, hány él kell a minimális költségű feszítőfák lefogásához. Némi gondolkodás után Kristóf mondott ekvivalens feltételt arra, hogy k-1 élt elhagyva ne nőhessen a minimális feszítőfa költsége: minden vágásban a minimális költségű élből legalább k példány kell. A mellékszálat végül Gyuszkó zárta le, aki ennek ellenőrzésére adott algoritmust: először a legkisebb költségű élek gráfját tekintjük, és ellenőrizzük, hogy a komponensek k-összefüggőek-e. Ezután a komponenseket összehúzzuk, a lépést ismételjük.
Az eredeti problémakörre visszatérve KTamás mutatott egy polinomiálisan számolható ekvivalens feltételt arra, hogy a 3. típusú gráfban k éllel lefoghassuk az r-fenyőket. Szóltam neki, hogy megfeledkezett arról, hogy az r-ből induló éleket is lehet törölni, de szerencsére a módszerét könnyen ki lehetett javítani: két esetet kell vizsgálni. Az első ugyanaz, mint fönt: megkeressük a minimális befok-összegű (r-et nem tartalmazó) diszjunkt halmazpárt, ahol most nem számoljuk az r-ből érkező éleket. Ha kitöröljük a szóban forgó éleket, nem marad fenyő, ami csak egyszer lép be (V-r)-be mert mind a két halmazba csak r-ből vezet él. A másik esetben (V-r)-nek keressük meg a minimális befokú nemüres részhalmazát, most számolva az r-ből induló éleket is. Nyilván ez is egy felső korlát a lefogó élhalmazra, vagyis a két esetben kapott érték minimuma is. Valójában ez a minimum lesz a minimális lefogó élhalmaz elemszáma, amit az rs éllel "kezdődő" fenyő nemlétezésének feltételét vizsgálva láthatunk.
A 2=>1 irány belátásához Erikában felmerült a kérdés, hogy ha minden F-beli F halmazhoz létezik olyan fenyő, ami egyszer lép be F-be, akkor igaz-e, létezik-e, ami egyszerre minden F-belibe csak egyszer lép be. Erre mutattam ellenpéldát, de Gyuszkó közbevetette, hogy nálam nem erősen összefüggő a gráf az F-beli halmazokra megszorítva, pedig az algoritmus ilyen halmazokat gyárt. Aztán rájöttem, hogy az erősen összefüggő esetben triviálisan igaz Erika sejtése, viszont Gyuszkónak nincs igaza: nekünk az élek törlése utáni gráfról kell tudnunk eldönteni, hogy van-e benne megfelelő r-fenyő, ott viszont már egyáltalán nem kell erősen összefüggőnek lenni a feszített részgráfoknak.
Kristóf mutatott egy megoldást a 2-es kérdésre, amely Tamás ötletét vitte tovább. Nem néztem meg nagyon tüzetesen, de nekem jónak tűnt. Ezzel párhuzamosan Gyuszkó is dolgozott ugyanazon, de ő valahogy dinamikus programozással próbálta összerakni a megoldását, csak szubrutinként használva Tamás algoritmusát a 3-as feladatra. Végül valami függvény szubmodularitása kellett volna neki -- saját állítása szerint --, de már senki sem nagyon követte. Még Tamással megbeszélték, hogy egyelőre nem tudják eldönteni, hogy tényleg szubmoduláris-e, aztán mentünk haza.
Nem gondoltam, hogy ilyen hosszú lesz, de persze Erika sem. Többször megfordult a fejemben, hogy elmegyek, de igazából ráértem (8-ra mentem SzGáborékhoz), és arra is kíváncsi voltam, hogy mi sül ki ebből. Így utólag örülök is, hogy maradtam. Asszem meg is kérdezem, hogy hogy áll a feladat (most épp az egyetemen ülök). Hogy miért csak most írtam ezt le, az egy jogos kérdés. Eredetileg nem éreztem elég bő alapanyagnak a témát, és ma döntöttem úgy, hogy leírom a hét matekos történéseit. Csak aztán ez olyan hosszúra nyúlt, hogy a többit inkább egy másik posztban. Mondjuk szűkszavúbban is beszámolhattam volna erről az egészről, de úgy éreztem, tanulságos lehet, hogy hogyan is néz ki egy ilyen workshop (talán azért is válthatott át workshopba ez a szeminárium, mert kevesen voltunk: a fent szereplőkön kívül csak Juli és Attila). Én is úgy érzem, kicsit közelebb kerültem a kutató matematikus életének megismeréséhez.
