Изменения
Нет описания правки
{{Задача|definition == Постановка задачи ==* Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и в каждом столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.* }}Очевидно, что решение данной задачи эквивалентно решению следующей: {{Задача|definition = Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.}}
== Сведение к задаче о потоке минимальной стоимости Алгоритм ==
[[Файл:pic1.PNG|thumb|right|270px|Пример построенного графа для матрицы <tex>A = \begin{pmatrix}
1 & 2 \\
3 & 4 \end{pmatrix}</tex>]]
Сведем задачу о назначениях к задаче нахождения потока минимальной стоимости.
Построим ориентированный граф, состоящий из двух частей <tex>G</tex> следующим образом:
* Имеется исток <tex>S</tex> и сток <tex>T</tex>.
Найдём в полученном графе <tex>G</tex> максимальный [[Поток минимальной стоимости|поток минимальной стоимости]]. <br />
== Доказательство ==
Понятно, что величина потока будет равна <tex>N</tex>. Заметим, что для каждой вершины <tex>i</tex> из первой части найдётся только одна вершина <tex>j</tex> из второй части, такая, что поток <tex>f(i, j) = 1</tex>. Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому это взаимно однозначное соответствие между вершинами первой части и вершинами второй части является решением задачи.
