Publikace na Matematicko-fyzikální fakulta |
2010
Abstrakt
Zabýváme se kombinatorickou hrou hranou dvěma hráči (Alenou a Bernardem) na váženém grafu G. Tato hra zobecňuje hru s pizzou, kterou se zabývali Brown, Winkler a další.
Ukážeme, že pro každé epsilon > 0 a každé k >= 1 existuje k-souvislý graf G, na kterém Bernard umí získat 1-epsilon celkové váhy vrcholů. Také se zabýváme výpočetní složitostí úlohy rozhodnout, zda má Alena na daném grafu vyhrávající strategii v této a jí podobné hře.