Л егко бачити, что трудомісткість кожного з пп. 1 – 9 не перевершує т ому час роботи алгоритму в цілому оцінюється зверху величиною

Як відзначалося вище, після виконання п. 8 ваги всіх ребер графа G залишаються невід’ємними, і, отже, безліч оптимальних рішень не міняється. Умові закінчення XM = YM = ( означає, що в «останньому» графі(T мається n дуг, спрямованих від Х к Y, яким відповідає зроблене паросполучення нульової ваги в «останньому» графі G. Відповідно до властивості 2 воно є оптимальним розв’язкомм вихідної задачі.

Резюмуємо усе вище викладене у виді теореми.

Теорема 77.5. Алгоритм А6 будує зроблене паросполучення мінімальної ваги в двочастковому зваженому графі G = (X, Y, | EG |), | X | = | Y | = n, за час O(n⁴).

Зауваження. Відомий алгоритм, що вирішує цю задачу за час O(n³).

В алгоритмі А6 оцінка O(n⁴) виникає, власне кажучи, через те, що приходиться O(n²) раз виконають операцію (X, Y, ), що сама вимагає часу O(n²). Зниження оцінки до O(n³) досягається за рахунок того, що результат цієї операції вдається одержати за час O(n).

Недавно опублікований алгоритм, оцінка трудомісткості якого в багатьох випадках переважніше O(n³). Ця оцінка має вид O(n^2,5log(n)), де Т – найбільший з ваг ребер графа.

мал. 77.3

Приклад. На мал. 77.3 представлена матриця ваг W = || Wij || двочасткового графа G = (X, Y, EG), у якої Wij = w(xi, xj), xi ( X, xj (Y.

Там же зображений граф(T, побудований по максимальному паросочитанию M = {x2y1, x1y2} нульові ваги в графі G. Відповідні цьому паросочитанию дуги графа(T обведені жирними лініями, а елементи матрици W відзначені зірочками.

Перед першим виконанням п. 4 маємо XM = {x3, x4, x5}, YM = {y3, y4, y5}. Пошук у ширину з XM дає Х' = {x2, x3, x4, x5}, У' = {y1}. Вершини безлічі X( ( Y( будемо відзначати значком «+». Оскільки шляху з XM у YM немає, те переходимо до пп. 7 – 9. Знаходимо ??= W32 = 1 і не виконуємо операцію ({x2, x3, x4, x5}, {y1}, 1), тобто віднімаємо 1 із всіх елементів у рядках 2, 3, 4, 5 і додаємо це число до всіх елементів першого стовпця. У результаті до графа(T додасться дуга (x3, y2). Модифікована матриця W (тобто граф G) і граф(T представлені на мал. 77.4 застосування пошуку в ширину до графа(T дає шлях Р = (x3, y2, x1,y5) з XM у YM. Замінимо (виконання п. 5) у графі(T дуги (x3, y2), (y2, x1), (x1,y5) відповідно на дуги (y2,x3), (x1, y2), (y5, x1). Новий граф(T також зображений на мал. 77.4. У ньому XM = {x4, x5}, YM = {y3, y4}.

Знову виконавши пошук у ширину з XM, одержимо X’ = {x2, x4, x5}, Y’ = {y1}. Серед елементів матрици W, що лежать на перетині рядків з номером 2, 4, 5 і стовпцем з номерами 2, 3, 4, 5, знаходимо мінімальний.

М ал. 77.4

Мал. 77.5

Мал. 77.6

Одержимо ??= W32 = 2. Результати наступного застосування до графа G операції ({x2, x4, x5}, {y1}, 2) і модифікований граф(T, представлені на мал. 77.5. У цьому графі мається шлях Р = (x5, y5, x1, y4) із з XM у YM. «Новий» граф(T, отриманий у результаті виконання п. 5, також зображений на мал. 77.5. Пошук у ширину в цьому графі з безлічі XM = {x4} дає Х' = {x2, x4}, У' = {y1}. Знаходимо ??= W32 = 1. Результати наступного виконання пп. 8, 9 представлені на мал. 77.6. Пошук у ширину з x4 дає Х' = {x2, x4, x5}, Y '= {y1, y5}. Знаходимо ??= W32 = 2. Одержуємо нові матрицю і граф(T (мал. 77.7). У графі(T маємо (x4, y3)-шлях Р = (x4, y4, x1, y3). Змінивши цей граф відповідно до п. 5, одержимо новий (мал. 77.7), у якому XM = YM = (.

П 'ять его дуг, що ведуть «від X до Y», відповідають ребрам зробленого паросполучення мінімальної ваги у вихідному графі G. Вага цього

мал. 77.7

паросполучення дорівнює 0 + 0 + 0 + 1 + 6 + 3 = 10.