О плотности полиэдральных графов задач комбинаторной оптимизации

Приводятся критерии смежности вершин многогранников известных оптимизационных задач о кратчайшем пути и о трехмерном сочетании. На их основе исследуется величина плотности полиэдральных графов указанных задач, которая характеризует временную сложность алгоритмов комбинаторного типа. Для задачи о кратчайшем пути найдено точное значение, а для задачи о трехмерном сочетании доказана экспоненциальность плотности графа ассоциированного многогранника.