A kombinatorika szeminárium következő előadása

december 5. (péntek)

10:00, !!! Vályi !!! terem

Rója Pál: Vékony elhelyezések fákban

Egy G gráf elhelyezése egy fában a gráf csúcsai és a fa levelei közötti bijekció. A gráf minden éle megfelel a fában két levél közötti útnak. Az elhelyezés ad egy súlyozást G élein: egy él súlya a megfelelő fabeli út hossza.

Célunk a fa és az elhelyezés megválasztása úgy, hogy az össz-súly minél kisebb legyen (az elhelyezés vékony legyen). Speciális fák között keresgélünk: előírjuk, hogy a nem-levél csúcsok foka 3 legyen.

Kiindulunk egy fából és elhelyezésből, majd módosítjuk ezt, hogy az össz-súly redukálódjon. A redukáló operációk többszöri alkalmazásával eljutunk egy vékony fa elhelyezéshez, melynek néhány szép tulajdonságát fogjuk belátni.

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

Péter

Supported by TÁMOP-4.2.2.A-11/1/KONV-2012-0073 projekt, "Telemedicina fókuszú kutatások Orvosi, Matematikai és Informatikai tudományterületeken"