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