Граф замен
Версия от 20:49, 29 сентября 2011; 192.168.0.2 (обсуждение)
Граф замен — специальный ориентированный двудольный граф, фигурирующий в теореме Эдмондса-Лоулера.
Пусть алгоритмом для матроидов , . Введем граф замен , левой долей которого являются элементы множества , правой — все остальные элементы . Проведем все имеющиеся ребра
— текущее независимое множество, построенное,
а также
.
Пусть алгоритм с помощью этого пути либо определяет максимальность набора , либо позволяет найти набор большей мощности.
— кратчайший путь в из в . ТогдаИсточник
Chandra Chekuri — Combinatorial Optimization, с. 2-3.