В классической задаче о паросочетаниях у нас есть n женихов и n невест, и у них есть преференции, кто с кем не прочь обвенчаться, - имеем двудольный граф. Лемма Холла дает необходимые и достаточные условия на двудольный граф, чтобы всех можно было успешно обвенчать в моногамном обществе.
В драконьей лемме Холла есть n+1 девушка, n юношей и 1 дракон. У юношей и девушек есть по прежнему двудольный граф преференций. Дракон прилетает и упячивает одну из девушек. Оставшуюся молодежь надо успешно обвенчать. Драконий Холл дает необходимые и достаточные условия, при которых это можно сделать независимо от того, кого упячил дракон.
При чем тут пермутоэдр? Его объем можно вычислить, просуммировав определенные мономы по множеству драконьих паросочетаний. Взято из статьи Постникова "PERMUTOHEDRA, ASSOCIAHEDRA, AND BEYOND".
Комментариев нет:
Отправить комментарий