Том 3, номер 3, 1996 г., Стр. 84-110

УДК 519.1
Р. Ю. Симанчёв
О ранговых неравенствах, порождающих фасеты многогранника связных $k$-факторов

Аннотация:
Любая система линейных уравнений и неравенств, описывающая выпуклую оболочку конечного множества точек, содержит неравенства, порождающие собственные грани максимальной размерности (фасеты). В данной статье рассматриваются неравенства с коэффициентами 0 и 1, порождающие грани выпуклой оболочки векторов инциденций связных остовных однородных степени к подграфов полного графа. Получены достаточное условие и ряд необходимых условий, при которых неравенство порождает фасету указанного многогранника. На основании этих условий найдены три класса фасет — ограничения единичного куба, неравенства, порожденные кликами, и неравенства, порожденные графами, введенными Эдмондсом при описании выпуклой оболочки 2-сочетаний.

Симанчёв Р. Ю. ¹
1. Омский государственный университет, мат. фак,
пр. Мира, 55а, 644077 Омск, Россия

Статья поступила 16 марта 1995 г.
Исправленный вариант — 23 июня 1996 г.