Опорные вершины главного многогранника Гомори

Abstract

We introduce two combinatorial operations and prove that they transform vertices of the Master Gomory Polyhedron (MGP) to adjacent vertices. This implies that the MGP is determined by the subset of its support vertices, those that do not result from other vertices by these operations. We establish interrelations between the coefficients of the nontrivial facets of the MGP that pass through a given vertex, construct new points on these facets, and prove that the MGP is of diameter 2. = Введены две комбинаторные операции и доказано, что их применение к вершинам главного многогранника Гомори приводит к смежным вершинам. Отсюда следует, что этот многогранник определяется подмножеством своих опорных вершин – тех, которые невозможно построить из других вершин с помощью этих операций. Установлены соотношения, которым удовлетворяют коэффициенты всех нетривиальных фасет, проходящих через заданную вершину, построены новые точки на этих вершинах и доказано, что многогранник имеет диаметр 2.