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