Page 97 - 4496

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

3.16.1 Паросполучення у двочастковому графові
Завдання знаходження максимального або найбільшого
паросполучення у двочастковому графові G =<A B,U>, U
Axb називається завданням про призначення.
Можна припустити, що A=B. Якщо це не так, то
завжди можна меншу множину доповнити елементами, не
пов'язаними з іншими елементами.
Будемо вирішувати наступне завдання: знайти у
двочастковому графі максимальне досконале паросполучення.
Розглянемо завдання в наступній семантиці. Мнжині А
зіставляється множина працівників, множині В – множина
робіт, ребра зважені числами (цілими й позитивними), що
визначають ефективність призначення працівника на роботу.
Число працівників дорівнює числу робіт. Потрібно знайти
таке призначення, коли всі працівники призначені на роботи й
усі роботи зайняті й при цьому досягається максимальна
ефективність використання працівників.
Умова існування зробленого паросполучення у
двочастковому графові визначається теоремою Кеніга-Холу:
Досконале паросполучення існує тоді й тільки тоді,
коли для будь-якого А' A має місце |A’|  |U(A’)|
Метод виділення максимального паросполучення
полягає в наступному (цей метод у літературі називають
угорським).
Зважимо вершини графа вагами х i для вершин
множини A і у i для вершин множини B таким чином, щоб
умова х i + у i с ij задовольнялася для будь-якого ребра. Якщо в

94