О пучке паросочетаний графа и числе LP-ориентаций многогранника Эдмондса

J. Edmonds представил задачу о максимальном паросочетании в графе как задачу линейного программирования и построил соответствующий этой задаче выпуклый многогранник - многогранник паросочетаний. С другой стороны, любая линейная функция на выпуклом многограннике задает LP-ориентацию его ребер.
В докладе будет описан пучок гиперплоскостей, регионы которого взаимно однозначно соответствуют LP-ориентациям многогранника паросочетаний. Вычисление характеристического многочлена такого пучка гиперплоскостей позволяет найти число LP-ориентаций многогранника паросочетаний с использованием теоремы T. Zaslavsky.
Текущие результаты по нахождению характеристического многочлена пучка паросочетаний для некоторых классов графов будут представлены в докладе.
Доклад состоится через zoom. Идентификатор: 845 0597 8739 Код доступа: 633657