A kombinatorika szeminárium következő előadása
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"