Frank András (ELTE Operációkutatás Tanszék)

A matroid metszet algoritmus alkalmazásai hálózati optimalizálásban

Egy élsúlyozott gráf maximális súlyú részfájának kiszámítása a mohó algoritmussal történhet,

de hogyan lehet meghatározni két élidegen fát, melyek össz-súlya maximális? Vagy egy

irányított gráfban miként számíthatunk ki egy legolcsóbb részgráfot, amelyben a digráf minden

csúcsába vezet k élidegen út egy megadott forráspontból? A matroid olyan absztrakt függetlenségi

struktúra, amelyben a maximális súlyú független halmaz megkonstruálása a mohó algoritmussal

végezheto. Ugyanakkor a matroidokra vonatkozó legfontosabb optimalizálási feladat

a metszetprobléma, amelyben nem egy, hanem két matroid maximális súlyú közös függetlenjének

kiszámítása a cél. Ennek algoritmikus megoldására egy elegáns algoritmus szolgál, amely

a Magyar Módszer nagyfokú általánosításának tekintheto.

Az eloadásban nem csak a fenti hálózat-optimalizálási feladatokról mutatom meg, hogy

miként oldhatók meg matroidmetszetek segítségével, hanem néhány olyan új alkalmazás is ismertetésre

kerül, amelyek más úton történo kezelése kilátástalannak tunik. Például, hogyan lehet

egy gráfban a leheto legkevesebb feszíto fát megadni úgy, hogy a gráf bármely élének kiesése után

is legalább az egyikük sértetlen maradjon? Vagy, mikor lehetséges egy irányított gráfban a csúcsokat

adott számú osztályba sorolni úgy, hogy mindegyik osztályból bármely pontba vezessen

k pontidegen út? Kiváncsiak lehetünk két élidegen feszíto fa létezésre, ráadásul úgy, hogy két

költségfüggvény is adott az élhalmazon és minimalizálni kell az elso fa elso költségének és a második

fa második költségének az összegét. Végül, hogyan lehet egy adott irányított gráf éleinek

olyan minimális költségu részhalmazát polinom idoben kiszámítani, amelyben egy elore megadott

forráspontból minden más pontba vezet k pontidegen út?

Időpont: nov. 6. kedd 16:15 Helye: BME, H épület 4. em 46.

fõoldal