Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

4.2. Пример

Решим ЗН для полного двудольного графа где матрица С стоимостей (весов) такая:

Редуцированной матрицей Сбудет -матрица, приведенная ниже, где векторы слева матрицы и вверху — весовые векторы соответственно.

(см. скан)

Начнем со случайно выбранного паросочетания, т. е. случайно выберем некоторое множество нулей, никакие два элемента в котором не лежат в одной строке или столбце. Выбранные нули отмечены звездочкой. В строке 4 нет отмеченных элементов, и она получает пометку рстр Следующие пометки располагаются в таком порядке Окончательные векторы пометок показаны справа от матрицы С и под ней.

Дальше помечать нечего. Теперь мы имеем После вычисления которое равно 1, и после изменения весов получаем новую матрицу изображенную ниже:

(см. скан)

Расстановка пометокпродолжается, так что Так как столбец 8 не имеет отмеченных нулей, то найдена аугментальная цепь, показанная стрелками в вышеприведенной матрице. «Меняя» отмеченные и неотмеченные нули вдоль этой цепи, получаем новое, улучшенное, паросочетание.

При второй итерации пометки стираются и в качестве строки отмеченных элементов выбирается строка 8, которая отмечается как рстр Больше пометок расставить нельзя,

оказывается равным заменяется на 6 и новая матрица С дана ниже. (Заметим, что при второй итерации венгерское дерево является на самом деле единственной изолированной — в терминах текущего графа вершиной, соответствующей строке 8.) Затем процесс расстановки пометок продолжается и получаются векторы и приведенные ниже.

(см. скан)

Опять помечать больше нечего, оказывается равным 4, веса изменяются и ниже дается новая матрица С (см. стр. 411).

Продолжается процесс расстановки пометок, и эти пометки (с учетом порядка их расстановки) таковы: Рстолб Рстре — Так как столбец 6 не имеет отмеченных элементов и он помечен, то найдена аугментальная цепь, показанная стрелками в матрице С. «Изменяя» вдоль этой цепи и не отмеченные нули, получаем совершенное паросочетание, являющееся поэтому паросочетанием с минимальной стоимостью (весом). Ребра этого паросочетания таковы: а полная стоимость (вес) равна 76 (для проверки заметим, что

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление