Аннотация:
Рассматриваются неравенства с коэффициентами 0 и 1, порождающие
грани выпуклой оболочки векторов инциденций связных остовных однородных
степени к подграфов полного графа. Получены достаточное условие и ряд необходимых
условий, при которых неравенство порождает фасету указанного
многогранника. На основании этих условий найдены три класса фасет – ограничения
единичного куба, неравенства, порожденные кликами, и неравенства,
порожденные графами, введенными Эдмондсом при описании выпуклой оболочки
2-сочетаний.
Библиогр. 6.
УДК:519.1
Статья поступила: 10.03.1995 Переработанный вариант: 23.06.1996