|
|
|
|
|
|
|
|||
| Év szerint | Hónap szerint | Ugrás a hónaphoz | |||||||
Rója Pál: Vékony elhelyezések fákban |
|
|||
|
|
||||
|
||||
| Absztrakt. 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. |
||||
Esemény exportálása JEvents v3.1.8 Stable Copyright © 2006-2013