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