Венгерский алгоритм транспортной задачи

← →
Strate © (2006-12-09 22:01) [0]

Здравствуйте. Не подскажете где можно почитать хорошее описание алгоритма? В частности интересует один момент, вычитанный в одном из описаний алогритма:

Шаг 2: Мы строим максимальное паросочетание на всех нулях полученных на предыдущем шаге.

Я конечно понимаю, что нужно построить паросочетание на графе, но что-то не представляю каким граф должен получится.
Была у нас допустим вот такая таблица:

5 3 2 1
4 3 5 2
5 6 10 2

после Шага 1 у нас она получилась вот такой:

2 1 0 0
0 0 2 0
1 3 7 0

Видим нули. Какой должен на них получиться граф?

← →
palva © (2006-12-10 01:24) [1]

У этого графа вершины это индексы строк и столбцов. Пишем для данного случая строчку с индексами строк, а потом строчку с индексами столбцов. Получаем:

1 2 3

1 2 3 4

Теперь соединяем ребрами те вершины которые соответствуют нулям матрицы. Например, если a13 = 0, то соединяем 1 из верхней строчки с 3 в нижней. Вот такой получится граф.

Венгерский алгоритм транспортной задачи Найти похожие ветки