Алгоритмы на графах и их приложения. Дорофеева В.И. - 30 стр.

     2.7.3 Задача о построении максимального паросочетания
в двудольном графе
     Решение подобного рода задач используется для моделирования процес-
сов, происходящих в жизни. Например, при распределении заданного количе-
ства людей по определенному количеству должностей. Граф при этом строится
следующим образом. В два столбца выстраиваются вершины: первый столбец –
служащие, второй столбец – должности, и вершины-служащие соединяются с
вершинами-должностями в направлении, обратному тому, которое задано в ис-
ходной задаче (исходное направление соответствует должностям, на которые в
принципе могут быть назначены служащие). Затем ставятся две вершины слева
и справа от этих столбцов, они будут являться источником и стоком. Дуги,
идущие от источника и к стоку имеют пропускную способность равную едини-
це, а дуги, соединяющие вершины в столбцах имеют пропускную способность
больше, чем по ним может пройти в данном графе. После решения задачи тол-
стыми линиями между столбцами указаны те пары, которые соответствуют
друг другу.
     Задача №5. Задача решается для двудольного графа G=(X,Y,U), где X –
множество вершин, из которых исходят дуги, а Y – множество вершин, в кото-
рые заходят дуги, X=5, Y=5. Жирными линиями, соединяющими вершины
исходного двудольного графа, на рисунке 32 указаны дуги, входящие в макси-
мальное паросочетание.


     Задача №6. Задача решается для двудольного графа G=(X,Y,U), где X –
множество вершин, из которых исходят дуги, а Y – множество вершин, в кото-
рые заходят дуги, X=8, Y=9. Жирными линиями, соединяющими вершины
исходного двудольного графа, на рисунке 33 указаны дуги, входящие в макси-
мальное паросочетание.




                                      30