maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2012-6-101-106mais-143Research ArticleОригинальные статьиArticlesПолиэдральные графы задач РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ и ПОЛНЫЙ ДВУДОЛЬНЫЙ ПОДГРАФPolyhedral Graphs of GRAPH PARTITIONING and COMPLETE BIPARTITE SUBGRAPH ProblemsАнтоновАнатолий ИгоревичAntonovA. I.

аспирант

аспирант

anatoly.i.antonov@gmail.comБондаренкоВладимир АлександровичBondarenkoV. A.

д-р физ.-мат. наук, профессор, заведующий кафедрой дискретного анализа

д-р физ.-мат. наук, профессор, заведующий кафедрой дискретного анализа

bond@bond.edu.yar.ruЯрославский государственный университет им. П.Г. ДемидоваРоссияЯрославский государственный университет им. П.Г. ДемидоваRussian Federation201212032015196101106Copyright © Антонов А.И., Бондаренко В.А., 20152015Антонов А.И., Бондаренко В.А.Antonov A.I., Bondarenko V.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/143

Приводится эффективное описание графов многогранников задач РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ и ПОЛНЫЙ ДВУДОЛЬНЫЙ ПОДГРАФ. Для каждого из них устанавливается, что плотность графа, то есть его кликовое число, растет экспоненциально по размерности пространства.

We provide an effective description of graphs of polyhedra for GRAPH PARTITIONING and COMPLETE BIPARTITE SUBGRAPH problems. We establish the fact, that the clique number for each of this problems increases exponentially with the dimension of the space.

многогранники комбинаторных задачсмежность вершинкликовое число графа многогранникаpolyhedra of combinatorial problemsadjacency of verticesclique number of graph of polyhedronгрант Правительства РФReferencesБондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. М.: ЛКИ, 2008. 184 с.Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. М.: ЛКИ, 2008. 184 с.Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

The authors declare that there are no conflicts of interest present.