Abstrakt
V práci uvažujeme problém nalezení vyrovnaného uspořádání vrcholů grafu. Přesněji chceme minimalizovat součet přes všechny vrcholy z absolutní hodnoty rozdílu počtu levých a pravých sousedů.
Ukážeme, že problém je NP-úplný pro grafy s maximálním stupněm 4, 5-regulární grafy a rovinné grafy s maximálním stupněm 6. Navrhneme též polynomiální algoritmus, který rozhodne, zda existuje uspořádání vrcholů s nevyrovnaností menší než daná konstanta.