Page 98 - 4496

розв'язку залишати тільки ті ребра, для яких виконується
рівність
х i + у i =с ij
(*),

і забезпечити підбором х i і у i виконання умови теореми
Кеніга-Холу, то при цьому сума с ij у паросполученні (яке
існує за теоремою Кеніга-Холу) буде максимально можливим,
сума всіх х i і у i – мінімально можливою, тому що перша сума
обмежує другу зверху, друга сума обмежує першу знизу. У
силу умови (*) при цьому с ij= х i + у i
Починаються розрахунки з того, що значенню х i
приписується maax с ij по всім j, а у i –нульові значення.
Побудуємо граф претендентів, що містить тільки ті
ребра вихідного графа, для яких виконується рівність (*). Для
графа претендентів перевіряємо умову теореми Кеніга-Холу.
Якщо знаходиться підмножина А', для якої умова теореми не
виконується, то для кожного її елемента вагу х i зменшимо на
одиницю, а вага кожного елемента з U(A’) збільшується на
одиницю. Якщо з'являються нові ребра, для яких слушна
умова (*), їх вносять у претенденти й знову перевіряють
умови теореми. Це триває, поки не будуть виконані умови
теореми Кеніга-Холу.
У графі претендентів розв'язок знаходять шляхом
перебору. При цьому спочатку для всіх вершин, ступінь яких
рівна 1, тобто для яких призначення однозначні, проводять
призначення, і відповідні пари вершин із графа видаляються,
що скорочує обсяг перебору.

3.17 Цикломатичне число графа

Нехай у графі m - число ребер, n- число вершин, p -
число компонентів зв’язаності. Величина = n - p називається

95