RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2013, том 25, выпуск 2, страницы 31–38 (Mi dm1232)

Эта публикация цитируется в 1 статье

Многогранники коммивояжера и разрезов. Аффинная сводимость

А. Н. Максименко


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

УДК: 519.178

Статья поступила: 09.09.2009

DOI: 10.4213/dm1232


 Англоязычная версия: Discrete Mathematics and Applications, 2013, 23:3-4, 251–259

Реферативные базы данных:


© МИАН, 2024