4.2. Пример
Решим ЗН для полного двудольного графа 
где матрица С стоимостей (весов) такая:
Редуцированной матрицей Сбудет 
-матрица, приведенная ниже, где векторы слева 
матрицы и вверху — весовые векторы 
соответственно.
(см. скан)
Начнем со случайно выбранного паросочетания, т. е. случайно выберем некоторое множество нулей, никакие два элемента в котором не лежат в одной строке или столбце. Выбранные нули отмечены звездочкой. В строке 4 нет отмеченных элементов, и она получает пометку рстр 
Следующие пометки располагаются в таком порядке 
Окончательные векторы пометок 
показаны справа от матрицы С и под ней.
Дальше помечать нечего. Теперь мы имеем 
После вычисления 
которое равно 1, и после изменения весов 
получаем новую матрицу 
изображенную ниже:
(см. скан)
Расстановка пометокпродолжается, так что 
Так как столбец 8 не имеет отмеченных нулей, то найдена аугментальная цепь, показанная стрелками в вышеприведенной матрице. «Меняя» отмеченные и неотмеченные нули вдоль этой цепи, получаем новое, улучшенное, паросочетание.
При второй итерации пометки стираются и в качестве строки 
отмеченных элементов выбирается строка 8, которая отмечается как рстр 
Больше пометок расставить нельзя, 
оказывается равным 
заменяется на 6 и новая матрица С дана ниже. (Заметим, что при второй итерации венгерское дерево является на самом деле единственной изолированной — в терминах текущего графа 
вершиной, соответствующей строке 8.) Затем процесс расстановки пометок продолжается и получаются векторы и 
приведенные ниже.
(см. скан)
Опять помечать больше нечего, 
оказывается равным 4, веса 
изменяются и ниже дается новая матрица С (см. стр. 411).
Продолжается процесс расстановки пометок, и эти пометки (с учетом порядка их расстановки) таковы: 
Рстолб 
Рстре — 
Так как столбец 6 не имеет отмеченных элементов и он помечен, то найдена аугментальная цепь, показанная стрелками в матрице С. «Изменяя» вдоль этой цепи 
и не отмеченные нули, получаем совершенное паросочетание, являющееся поэтому паросочетанием с минимальной стоимостью (весом). Ребра этого паросочетания таковы: 
а полная стоимость (вес) равна 76 (для проверки заметим, что 
