В математике , экономике и информатике многогранник стабильного соответствия или многогранник стабильного брака представляет собой выпуклый многогранник , полученный из решений экземпляра задачи стабильного соответствия . [1] [2]
Многогранник устойчивых паросочетаний представляет собой выпуклую оболочку индикаторных векторов устойчивых паросочетаний данной задачи. Он имеет размерность для каждой пары элементов, которые могут быть сопоставлены, и вершину для каждого стабильного сопоставления. Для каждой вершины декартовы координаты равны единице для пар, которые совпали в соответствующем паросочетании, и нулю для пар, которые не совпали. [1]
Стабильный паросочетающий многогранник имеет полиномиальное число гиперграней . К ним относятся обычные неравенства, описывающие сопоставления без требования устойчивости (каждая координата должна быть между 0 и 1, и для каждого элемента, который должен быть сопоставлен, сумма координат для пар, включающих этот элемент, должна быть ровно единица), а также неравенства, ограничивающие результирующее сопоставление должно быть устойчивым (для каждого потенциально совпадающего элемента пары сумма координат совпадений, которые хотя бы не хуже одного из двух элементов, должна быть не меньше единицы). Точки, удовлетворяющие всем этим ограничениям, можно рассматривать как дробные решения релаксации линейного программирования задачи устойчивого согласования.
Это теорема Ванде Вейта (1989) о том, что многогранник, описываемый перечисленными выше ограничениями граней, имеет только вершины, описанные выше. В частности, это целочисленный многогранник . Это можно рассматривать как аналог теоремы Гаррета Биркгофа о том, что аналогичный многогранник, многогранник Биркгофа , описывающий множество всех дробных паросочетаний между двумя множествами, является целым. [3]
Эквивалентный способ формулировки той же теоремы состоит в том, что каждое дробное паросочетание может быть выражено как выпуклая комбинация целочисленных паросочетаний. Тео и Сетураман (1998) доказали это, построив распределение вероятностей для целочисленных паросочетаний, ожидаемое значение которых может быть установлено равным любому заданному дробному паросочетанию. Для этого они выполняют следующие действия:
Полученное случайно выбранное стабильное сопоставление выбирает любую конкретную согласованную пару с вероятностью, равной дробному значению координаты этой пары. Поэтому построенное таким образом распределение вероятностей по устойчивым паросочетаниям обеспечивает представление данного дробного паросочетания в виде выпуклой комбинации целочисленных устойчивых паросочетаний. [4]