Допустимо тепер, що V(( ( V(. Оскільки V одержує постійну мітку l(V) з V((, а не з V(, те

V(P*) = l(v() + w(v(, v) ( l(v(() + w(v((, v) = w(P().

Таким чином, і у випадку б) вірна нерівність w(p() ( w(p*), тобто p( – найкоротший (s, V)-пута.

Оцінимо тепер трудомісткість алгоритму. Обчислювальні витрати максимальні, коли вершина t одержує постійну мітку останньої і граф G є повним. У цьому випадку число ітерацій алгоритму дорівнює |G| – 1, тобто кожний із пп. 2 – 4 виконується |G| – 1 разів. Очевидно, що п. 4 виконується за час ПРО(1), а для виконання кожної з пп. 2, 3 досить часу ПРО(|G|).

Мал. 76.1

Побудова шляху за допомогою міток  можна здійснити, витративши не більше ПРО(|G|) операцій. Таким чином, в цілому час побудови найкоротшого (s, t)-шляху не перевершують



Приклад 1. На мал. 76.1 зображені п'ять копий Gk

г рафа G, кожна з яких відбиває ситуацію, що склалася після чергової ітерації алгоритму. Біля кожної дуги написана її вага. Вершинам копії Gk приписані влучні, отримані ними в результаті виконання перших k ітерацій. Деякі дуги обведені жирними лініями, тобто відзначені. Добовлення такої дуги (a, b) при переході від Gk до Gk+1 означає, що вершина b одержала свою мітку l(b) з a і ця мітка стала постійною на (k + 1)-й ітерації. Вершина t у нашому прикладі одержує постійну мітку останньої, і відзначені дуги G5 утворять дерево найкоротших шляхів з s.

При розв’язанні багатьох задач виникає необхідність відшукання в незваженому графі (s, t)-шляху з мінімальною кількістю дуг. Такий шлях, мабуть, можна знайти за допомогою алгоритму Дейкстри. Для цього досить привласнити всім дугам графу G ваги, рівні 1, і застосувати алгоритм А6. Останнім роботу алгоритму в цій ситуації, звертаючи особливу увагу на послідовність, у якій вершини графа G одержують постійні мітки. Очевидно, що спочатку постійні мітки l = 1 одержать усі вершини безлічі Г(s). Потім мітка l = 2 буде привласнена кінцям дуг, що виходять з вершин з мітками l = k –1. Цей процес обходу (і присвоєння міток) вершин графа називають пошуком у ширину в графі (на інтуїтивному рівні пошук у ширину описаний у параграфі 9). По закінченні пошуку в ширину мітка l(x) вершини x дорівнює мінімальному числу дуг у (s, x)-шляху. Как і раніше, сам цей шлях визначається мітками . Здійснення пошуку в ширину за допомогою алгоритму Дейкстри зв'язано, як ми знаємо, з обчислювальними витратами

2. Алгоритм пошуку в ширину. Р озглянемо алгоритм А6, що здійснює пошук у ширину за час O(|EG|). У цьому алгоритмі мітки l і ( грають ту ж роль, що й у попередньому, з тієї, однак, різницею, що мітки l не поділяються на тимчасові і постійні. Як тільки вершина x одержує мітку l(x) ( (, ця мітка відразу стає постійною (тобто остаточною). За рахунок цього, зокрема, досягається економія часу обчислень у порівнянні з алгоритмом Дийкстры.

Особливу роль в алгоритмі А6 грає список Q. Кожна вершина графа один раз заноситься в цей список і один раз з нього викреслюється. При цьому викреслюється увесь час перша(на поточний момент) вершина цього списку, а тільки що додана вершина завжди є останньої в списку, тобто Q-черга. На початку в Q знаходиться єдина вершина s, l(s=0), а всі інші вершини міток не мають. Загальна ітерація складається в наступному. Вибирається перша вершина х у списку Q. Кожній не поміченій вершині y  Г(x) привласнюються мітки l(y)=l(x)+1 і (y)=x, після чого вершина в стає останньої в списку Q, а вершина х віддаляється з Q. Алгоритм припиняє роботу, як тільки в Q не залишиться жодної вершини. При цьому вершини, досяжні з s, будуть мати мітки, а недосяжні – нематимуть. Для швидкого виконання операцій викреслювання і включення в Q використовуються змінні покажчики p і q – адреси першої й останній зайнятих осередків списку Q відповідно.

Будемо вважати, что граф G заданий списками суміжності і Nv – список, що містить конци всіх дуг, що виходять з вершини v.

Алгоритм А6 пошуку в ширину.

1. Q(1):=s, p:=1, q:=1, l(s):=0.

2. x:=Q(p), m:=|Г(x)| [обрана перша вершина x черги Q].

[П.п. 3 – 5 присвоєння міток не позначеним вершинам з Г(x)].

3. k:=1.

4. Якщо вершина в = Nx(k) має мітку, то перейти до п. 5. Інакше l(y):=l(x)+1, (y):=x, q:=q+1, Q(q):=y [вершина в позначена і включена в чергу Q] і перейти до п.5.

5. Якщо k=m, то перейти до п.6, інакше k:=k+1 і перейти до п.4.

6. p:=p+1 [вершина x виключена з Q].

7. Якщо p>q, то кінець [Q = 0, тобто усі вершини досяжні з s, одержали мітки], інакше перейти до п.2.

Т еорема 76.2. Алгоритм А6 привласнює мітки l і  усім вершинам графа, досяжним з вершини s за час ПРО(|EG|). При цьому

з мінімальним числом дуг, а l(x) – число дуг у цьому шляху.

О сновні обчислювальні витрати пов'язані з виконанням п. 3 алгоритму. Сумарний час виконання цього пункту складає

оскільки кожний зі списків Nv проглядається в точності один раз. Витрати на виконання інших пунктів, мабуть, не перевершують цієї величини.

Вище відзначалося, что результати алгоритму А6 (тобто мітки l і ) ті ж, що й в алгоритмі Дейкстри, якщо кожній дузі графа G приписати вага, рівна 1. Тому справедливість другого твердження випливає з твердження 76.1.

Зауваження 4. Іноді потрібно шукати шляхи з вершин безлічі X ( VG

в усі інші вершини. Для розв’язку цієї задачі достаточно злегка модифікувати алгоритм А6, зміни в ньому п. 1. Саме, у списог Q варто помістити усі вершини x Є X. На модифікований у такий спосіб алгоритм А6 будемо посилатися як на пошук у ширину з безлічі X.

3. Алгоритм пошуку найкоротших шляхів у графах з від’ємними вагами дуг. Перейдемо тепер до розгляду загальної ситуації. Будемо вважати, що в графі G пдопускаються дуги від’ємної ваги. Запропонований нижче алгоритм А7 будує в такому графі найкоротші шляхи між усіма парами вершин графа за умови, що в графі немає від’ємних контурів (контурів від’ємної ваги). Якщо ж такий контур у графі є, то алгоритм сповіщає про це і припиняє роботу, залишаючи задачу відшукання найкоротшого шляху невирішеною (див. нижче зауваження 6).

Будемо вважати, что граф G, |G| = n, заданий матрицею ваг W = ||Wij||, тобто Wij = (i, j), якщо (i, j) Є AG, і Wij = 

противному випадку. Крім того, припускаємо Wij = 0 для всіх і = 1, 2, ..., n. Алгоритм заснований на наступних розуміннях. Нехай i, j, k – три будь-які вершини графа G, і ми хочемо одержати (i, j)-шлях, найкоротший серед (i, j)-шляхів, що не містять внутрішні вершини, відмінних від k. Очевидно, что для этого досить вибрати меншу з двох величин Wij і Wik + Wkj, що і буде вагою такого (i, j)-шляху. Якщо зафіксувати k і проробити цю операцію (назвемо її t-операцією, застосованої до індексу k) для всіх пар (i, j), то одержимо матрицю W’ = ||W’ij||, у якої W’ij = min{Wij, Wik + Wkj}. Виявляється (це буде пізніше доведене), маючи матрицю

ваг найкоротших шляхів, що проходять тільки через вершини безлічі S  VG

м ожна одержати таку ж матрицю для шляхів, що проходять через безліч

Д ля цього досить точно застосувати t-операцію до індексу m і всім елементам матриці

Саме в цьому складається ітерація алгоритму А7, що, починаючи з W = W,

б удує таку послідовність матриць з астосуванням t-операції до індексу m і матриці

Якщо в графі G немає від’ємних контурів, то елемент

п ри кожному m дорівнює вазі найкоротшого (i, j)-шляху, усі внутрішні вершини якого належать безлічі {1, 2, ..., m}. Таким чином, остання з цих матриць,

м істить ваги найкоротших шляхів між усіма парами вершин графу. Для того щоб після

закінчення роботи алгоритму мати можливість швидко знайти найкоротший шлях між будь-якою парою вершин, будемо на k-й ітерації разом з матрицею

б удувати матрицю

С початку думаємо

Далі, на k-й ітерації думаємо

Т аким чином,

номер вершини, що передує вершині j у поточному (i, j)-шляху, тобто в найкоротшому (i, j)-шляху, усі внутрішні вершини якого містяться в безлічі {1, 2, ..., k}. Матриця

г рає ту ж роль, що й мітки  у попередніх алгоритмах А5 і А6. За допомогою цієї матриці найкоротший (i, j)-шлях L(i, j) визначається в такий спосіб: L(i, j) = (i, ..., j3, j2, j1, j), де

А лгоритм А7 відшукання найкоротших шляхів між усіма парами вершин.

1 .

у противному випадку.

2. Виконати для всіх

3 . Якщо для деякого l,

то кінець [у графе маємо від’ємний контур]. Інакше перейти до п. 4.

4 . k:=k+1. Якщо k=n+1, то кінець

м атриця ваг найкоротших шляхів, обумовлених за допомогою матриці

Зауваження 5. Алгоритм буде застосовний до змішаних графів, якщо кожне неорієнтоване ребро замінити на двох дуг тієї ж ваги (див. зауваження 2). При цьому варто врахувати, что неорієнтоване ребро від’ємної ваги приводить до від’ємного контуру.

Зауваження 6. Алгоритм «відмовляється» будувати найкоротші шляхи, коли в графі G маються від’ємні контури. У цьому випадку задача відшукання найкоротшого шляху між двома вершинами (чи між усіма парами вершин) залишається коректною, але стає дуже важкою. Можна показати, что вона не менш важка, чим, наприклад, задача про комівояжера.

Перейдемо тепер до обґрунтування алгоритму А7 і оцінювання його трудомісткості.

Теорема 76.3. Нехай зважений орієнтований мультиграф L має ейлеровий ланцюг, що з'єднує вершини a і b. Якщо в L немає від’ємних контурів, то в ньому є такий (a, b)-шлях Р, що w(L)  w(P).

Доказ. Будемо вважати, що мультиграф L не є шляхом (інакше твердження тривіальне). Тому він містить деякий контур S. Видаливши з L усі дуги цього контуру, одержимо мультиграф L’. Оскільки w(S)  0, то w(L)  w(L).

К рім того, відповідно до теореми 65.2 напівступеня вершин мультиграфа L’ задовольняють співвідношенням

Тому вершини a і b належать до однієї її слабкої компоненти L’’, і остання містить ейлеров (a, b)-ланцюг. Продовжуючи подібним чином, одержимо необхідний (a, b)-шлях.

Теорема 76.4. Якщо в графі немає від’ємних контурів, то при всіх

в ага найкоротшого (i, j)-шляху, усі внутрішні вершини якого містяться в безлічі {1, 2, ..., k}.

Доказ. Доводимо індукцією по k. При k=1 справедливість твердження очевидна. Припустимо, что воно справедливо для 2, 3, ..., k – 1, і розглянемо

н айкоротший (i, j)-шлях, усі внутрішні вершини якого належать безлічі {1, 2, ..., k}. Якщо

і , відповідно до припущення індукції,

Д опустимо тепер, что P містить вершину k. Позначимо через

в ід i до k і від k до j відповідно. Припустимо, что один з цих шляхів, наприклад

н е є найкоротшим, і нехай P’ – найкоротший (i, k)-шлях, усі вершини якого містяться в безлічі {1, 2, ..., k-1}. Розглянемо мультиграф L, що виходить із графа

з аміною кожної дуги, що входить одночасно в

д вома екземплярами цієї дуги. Очевидно, що L не містить від’ємних контурів. Тому, відповідно до твердження 76.3, L містить такий (i, j)-шлях Р, що

Ц я нерівність суперечить мінімальності P.

Таким чином, шляху

Є найкоротшими серед, відповідно, (i, k)- і (k, j)-шляхів, усі внутрішні вершини яких належать безлічі {1, 2, ..., k – 1}. Тому, скориставшись припущенням індукції, одержимо

Теорема 76.5. Час роботи алгоритму А7 не перевершує O(|G|³). Якщо граф не містить від’ємних контурів, то Wⁿ_ij - вага найкоротшого (i, j)-шляху в графе G для всіх i,j = 1,…,n,n=|G|... Якщо ж такі контури в графе є, то існують такі числа m і l, что W^m_ll < 0.

Доказ. Справедливість першого твердження теореми очевидна, оскільки кожна з не більш чем |G| ітерацій виконується за час O(|G|³)

Друге твердження теореми безпосередньо випливає з теореми 76.4.

Допустимо тепер, что граф G містить від’ємні контури. Нехай m – такий найменший індекс, що для деякої вершини l у графе G маємо від’ємний контур S, що містить только l і деякі вершини безлічі {1, 2, ..., m}. Ясно, что контур S включає вершину m. Тоді при будь-яких i,j = 1,…,n число W^m-1_ij дорівнює вазі найкоротшого (i,j)-шляху, усі внутрішні вершини якого належать безлічі {1, 2, ..., m – 1}. Доказ цього факту дослівно повторює доказ теореми 76.4. Контуру S відповідають (l, m)-шлях Р1 і (m, l)-шлях Р2, такі, що Р1 ( Р2 = S.

Оскільки внутрішні вершини шляхів Р1 і Р2 належати безлічі {1, 2, ..., m – 1}, то

О тже,

Мал. 76.2

Приклад 2. Нижче приведені результати виконання кожної з чотирьох ітерацій алгоритму для графу, зображеного на мал. 76.2:

Знайдемо, наприклад, за допомогою матриці P⁴ найкоротший (2, )-шлях: P⁴₂₁ = 4, P⁴₂₄ = 3, P⁴₂₃ = 2. Отже, (2, 3, 4 , 1) – найкоротший (2,1)-шлях.

Лекція 3.1. Найбільші паросполучення і задача про призначення

Задача про побудови найбільших паросполучень у графі широко поширена, і для її розв’язку існують ефективні алгоритми. Ці алгоритми засновані на методі ланцюгів, що чергуються, основаному на роботах Дж. Петерсону. У даній лекції ми розглянемо декілька ефективних алгоритмів, побудованих на цьому методі.

1. Алгоритми побудови найбільших паросполучень. Нехай М – паросполучення в графі G. Ланцюг графа G, ребра якого по черзі входять і не входять у М, називається ланцюгом що чергується відносно М. Ланцюг довжини 1 по визначенню також чергується. Ребра ланцюга називаються темними чи світлими, якщо вони чи входять, відповідно, не входять у М. Вершини графа G, інцендетні ребрам з М, називаються насиченними, всі інші вершини – ненасиченними. Розглянемо, наприклад, граф на мал. 77.1. Безліч ребер

М = {e1, e7, e10} (1)

є в G паросполученням;

P = {7, 8, 4, 1, 2, 5} (2)

• що чергується відносно М ланцюг; e1 = {1, 2}, e10 = {4, 8} – темні ребра Р; e3 = {1, 4}, e5 = {2, 5}, e13 = {7, 8} – світлі ребра Р; {1, 2, 3, 4 , 6, 8} і {5, 7, 9, 10} – безлічі насичених і ненасичених вершин відповідно.

мал. 77.1.

Очевидно, что якщо в графе G існує ланцюг що чергується відносно паросполучення М ланцюг, то можна побудувати в G паросполучення з більшим числом ребер, ніж у М. Справді, у такому ланцюзі число темних ребер на одиницю менше числа світлих. Видаливши з М усі темні ребра і приєднавши усі світлі, одержимо нове паросполучення, у якому число ребер на одиницю більше. З цієї причини ланцюг що чергується відносно паросочетания М ланцюг, що з'єднує дві різні ненасиченні вершини, будемо називати збільшуючим відносно М ланцюгом у графі G.

Отже, відсутність увеличивающих відносно М ланцюгів необхідно, щоб паросполучення М було б найбільшим. Ця умова виявляється і достатньою.

Теорема 77.1. Паросполучення М в графі є найбільшим тоді і только тоді, коли в цьому графі немає збільшуючих відносно М ланцюгів.

Доказ. Необхідність умови теореми, як вище відзначалося, очевидна. Достатність доведемо від противного. Нехай М1 також є паросполученням у G і |М1| > |M|. Розглянемо граф Н, утворений ребрами, що входять у суму М и М1 по модулі 2, тобто в (M  M1)\(M  M1). Тому що довільна вершина v цього графа инцідентна не більш ніж одному ребру кожного з паросполучень М и М1 , то її ступінь не більше чим 2. Якщо deg v = 2, то одне з инцідентних вершині v ребер входить у М, інше в – М1. Тому будь-який зв'язний компонент графа Н є або циклом, що містить те саме число ребер з М и з М1, або ланцюгом що чергується відносно М. Але |M1| > |M|, отже, серед цих компонентів обов'язково є ланцюгом що чергується відносно М , крайні ребра якої (перше й останнє) входять у М1. Тоді крайні вершини цього ланцюга не насичені паросполученням М, що суперечить умові теореми. 

Д ля ілюстрації знову звернемося до графа G на мал. 77.1. Що чергується відносно паросполучення (1) ланцюг (2) з'єднує ненасиченні вершини 5 і 7. Отже, можна побудувати паросполучення М' з великим числом ребер:

Паросполучення М’ також не є найбільшим: (9, 10) – збільшуючийся відносно М’ ланцюг. Паросполучення

– найбільше, ?(G) = 5.

Таким чином, теорема 77.1 підказує наступну стратегію пошуку найбільшого паросполучення: почавши з довільного паросполучення М, будувати послідовність М1 = М, М2, М3 ..., у якій паросполучення Мк+1 виходить із Мк за допомогою тільки що розглянутої зміни уздовж деякого ланцюга, що збільшується. Оскільки | Мк+1 | = | Мк | + 1, то задля одержання найбільшого паросполучення буде потрібно не більш |G|/2 ітерацій (тобто переходів від Мк до Мк+1). У якості М можна взяти, наприклад, довільне ребро чи графа, що краще, деяке максимальне паросполучення, так що вихідне паросполучення завжди є в нашому розпорядженні. Тому розробка ефективного алгоритму, заснованого на зазначеній стратегії, зводиться до побудови процедури, що швидко знаходиться ланцюг, що збільшується, у графі, або виявляє його відсутність. Обмежимося випадком двочасткового графу, хоча така процедура (а виходить, і ефективний алгоритм відшукання найбільшого паросочитания) відома й у випадку довільного графу. Отже, нехай G = (X, Y, E) – двочастковий граф і М – паросполучення в цьому графі. Поставимо у відповідність графу G і паросполучення М допоміжний орієнтований двочастковий граф

І ншими словами, щоб одержати графG, досить додати орієнтацію “від Y до X” усіх ребер графа G, що входить у паросполучення М, і “від X до Y” всіх інших ребер цього графа. На мал. 77.2 зображені граф G з паросполученням М (виділено жирними лініями) і графG.

Мал. 77.2

Позначимо через XM і YM безліч ненасичених вершин, що входять, відповідно, у X і Y. Справедливість наступного твердження очевидна.

Теорема 77.2. У графе G збільшуючийся відносно паросполучення М ланцюг існує тоді і только тоді, коли в графеG існує (s, t)-шлях, у якого s XM, t  Y M.

НехайР – (s, t)-шлях у графі G, s  XM, t YM, P – відповідний ланцюг, що збільшується, у ( G і М1 - паросполучення, отримане зміною М уздовж ланцюга Р. Тоді допоміжний графG1 для графа G і паросполучення М1 можна одержати з графаG заміною кожної дуги шляхуP на зворотню. Ця операція разом з пошуком шляхуP складає ітерацію алгоритму, що приводиться. Передбачається, что граф G заданий списком суміжності.

Алгоритм А6 побудови найбільшого паросполучення в двочастковому графі.

1. Побудувати будь-яке максимальне паросполучення М в графі G.

2. По графі G і паросполученню М побудувати граф G.

3. Н ехай у графе

4. Я кщо в результаті пошуку в ширину з вершин безлічі

не одержали мітки, то перейти до п.5. Інакше перейти до п.6.

5. Нехай Т = {(x1, y1), (x2, y2), ..., (xk, yk)} – безліч усіх дуг, що виходять з безлічі Y. Покласти М* = {y1x1, y2x2, ..., ykxk} [M* - найбільше паросполучення]. Кінець.

6. 

Теорема 77.3. Алгоритм А8 будує найбільше паросполучення в двочастковому графі G = (X, Y, EG) за час O (|EG| min {|X|, |Y|}).

Те, що алгоритм коректний і побудоване їм паросполучення є найбільшим, випливає з теореми 77.1 і твердження 77.2. Очевидно також, що число ітерацій алгоритму (тобто виконань п. 2 – 5) не перевершує величини min {|X|, |Y|}, оскільки на кожній ітерації, крім останньої, величини

з меньшується на одиницю.

Відповідно до твердження 76.2 п. 3 виконується за час O(|EG|). Легко показати, що ця ж оцінка трудомісткості справедлива і для інших кроків алгоритму. Таким чином, час виконання окремої ітерації складає O( |EG| ), а алгоритму в цілому – O (|EG| min {|X|, |Y|}).

Разом з найбільшим паросполученням алгоритм А8 фактично знаходить і найменше верхове покриття в графе G. У результаті останнього виконання п. 3 алгоритму буде встановлена відсутність шляху з

у графе G. Отже, тільки частина вершин цього графа буде мати мітки після закінчення пошуку в ширину з

Позначимо через X і Y, відповідно, безлічі непомічених вершин частки Х и позначених вершин частки Y. Покладемо Z = X + Y.

Будемо вважати, що в графе G немає ізольованих вершин.

Теорема 77.4. Безліч Z є меншим верховим покриттям графа G.

Твердження достатнє довести для зв’язаних графів. Нехай (a, b) – довільна дуга графа(G. Якщо a(Y, b(X, то ці вершини або обидві позначені, або ні. В обох випадках дуга (a, b) инцідентна вершині безлічі Z. Нехай a(X, b(Y. Тоді, якщо вершина не позначена, то a(Z.

Якщо ж a позначена, то і вершина b позначена і, отже, b(Z.

Отже, будь-яка дуга графа (G инцидентна деякій вершині безлічі Z, тобто Z – покриття графа G. Крім того, легко бачити, що | Z | = | T |, де Т – безліч усіх дуг графа (G, що ведуть з безлічі Y. Безлічі Т в графі G відповідає найбільше паросполучення. Тому з теореми 32.2 випливає, що верхове покриття Z є найменшим.

Використаний тут метод ланцюгів, що чергуються, відіграє важливу роль і при рішенні більш загальних задач. Одну з них ми зараз розглянемо.

2. Алгоритм побудови паросполучень для зважених графів. Нехай G = (X, Y, EG) – повний двочастковий зважений граф, | X | = | Y | = n. Потрібно знайти в графе G паросполучення, вага якого мінімальний. Легко бачити, что це – згадувана раніше задача про призначення (див. гл. IV, параграфа 30).

Зроблене паросполучення мінімальної ваги назвемо для стислості оптимальним розв’язком.

Задача про призначення володіє двома простими властивостями:

1. Оскільки для кожної вершини будь-яке зроблене паросполучення містить у точності одне ребро, инцідентне цій вершині, то безліч оптимальних рішень не зміниться, якщо ваги всіх ребер, инцідентних якій-небудь вершині, збільшити (зменшити) на те саме число.

2. Якщо ваги всіх ребер графа невід’ємні і вага деякого зробленого паросполучення дорівнює нулю, то воно є оптимальним розв’язком.

Нехай, як звичайно, w(x, y) – вага ребер xy. Будемо вважати, що

З першої властивості випливає, що випадок, коли маємо ребра від’ємної ваги, зводиться до нашого. Крім того, ця властивість дозволяє, витративши

о перацій, перейти до зваженого графа, у якого кожній вершині інцидентно ребро нелівої ваги і ваги всіх ребер невід’ємні. Для цього досить змінити матрицю ваг графа G у такий спосіб: спочатку відняти з всіх елементів кожного рядка мінімальний елемент цього рядка, а потім то ж саме проробити зі стовпцями. Будемо вважати, что ця операція вже виконана і граф G має необхідні властивості.

Нехай A  X, B  Y і де-яке число. Будемо говорити, що до графа G застосовується операція (А, У, ), якщо спочатку з ваги кожного ребра, інцидентного вершині з безлічі А, віднімається а потім до ваги кожного ребра, інцидентного вершині з У, додається ?. Відповідно до властивості 1 зважений граф, що вийшов у результаті, має ту ж безліч оптимальних рішень, що і граф G. Крім того, ребра виду ab, де a  A, b  B, у перетвореному графі будуть мати ті ж ваги, что й у вихідному. Нехай T = (X, Y, U) – двочастковий граф і М – паросполучення в цьому графі. Будемо, як і раніше, позначати черезT = T(T, M) орієнтований двочастковий граф, отриманий із графа Т шляхом ориентаций «від Y до X» усіх ребер паросполучення М и «від X до Y» інших ребер цього графу.