Аннотация:
Пусть $STSP_m$ – многогранник задачи коммивояжера для $m$ городов, а $CUT_n$ – многогранник разрезов полного графа на $n$ вершинах. Показано, что $CUT_n$ аффинно эквивалентен одной из граней многогранника $STSP_m$ при $m=(2n-2)(2n-3)$. С другой стороны, $STSP_m$ является аффинным образом одной из граней многогранника $CUT_n$ при $n=(m-1)^2+1$.