2. Некоторые прикладные задачи

1. Задачи об источниках и потребителях

В задачах этого типа встречаются три рода объектов: «источники», «потребители», «промежуточные пункты». Источниками могут быть электростанции, заводы, контрольно-измерительные приборы, железнолорожные станции и т.д., которые поставляют соответственно электроэнергию, изделия, информацию, грузы и т.д. для потребителей. В промежуточных пунктах может происходить, например, преобразование электроэнергии, упаковка или комплектация изделий, кодирование информации, перевалка грузов, причем, что весьма существенно, без изменения количества грузов. Источники, промежуточные пункты и потребители связаны сетью линий передач или автомобильными, железнодорожными, морскими линиями или каналами связи с заданными пропускными способностями.

Пусть в некоторую единицу времени источники x_j (j=1,2,..,k) вырабатывают a_j единиц продукции, а потребность потребителя y_i (I=1,2,..,m) в этой продукции равна b_i. Пропускные способности линий считаются также отнесенными к выбранной единице времени. Таким образом, в задачах этого типа идет речь о неизменном и однородном по времени стационарном потоке.

С каждой такой задачей свяжем транспортную сеть D. Вершинами сети D служат источники, потребители, промежуточные пункты и еще две вспомогательные вершины: вход x₀ и выход z. Вершину x₀ свяжем дугами (x₀,x_j) (j=1,..,k) с источниками и припишем им пропускные способности a_j. Потребителей y_i свяжем с выходом z дугами (y_i,z) с пропускными способностями b_i. Остальные вершины соединим между собой дугами с соответствующими пропускными способностями в соответствии с реальным наличием связей между ними.

Возникает задача о нахождении такого распределения потока энергии (грузов, информации и т.д.) по линиям, чтобы в максимальной степени (желательно полностью) удовлетворить потребителей. Очевидно, что эта задача об отыскании потока наибольшей величины на транспортной сети D.

22. Решить задачу об источниках и потребителях, сведя ее к задаче построения максимального потока в транспортной сети и используя первый алгоритм построения максимального потока .

23. Решить задачу об источниках и потребителях, сведя ее к задаче построения максимального потока в транспортной сети и используя второй алгоритм – алгоритм меток для построения максимального потока.

3. Двудольные графы и паросочетания

Рассмотрим задачу о назначении на должности. Пусть в некотором учреждении имеется 6 вакантных должностей y₁,y₂,…,y₆ и 6 работников x₁,x₂,…,x₆. Граф D, изображенный на рис.5, иллюстрирует, какие должности y может в силу своей квалификации занимать работник x. Пусть выполнено условие: каждый работник может занимать только одну должность, и каждая работа выполняется только одним работником. Тогда решение этой задачи сводится к построению наибольшего паросочетания в данном двудольном графе.

x₁ x₂ x₃ x₄ x₅ x₆

y₁ y₂ y₃ y₄ y₅ y₆

Рис. 5.

1. Нахождение наибольшего паросочетания в двудольном графе

Граф G = (V,X) называется двудольным, если множество V его вершин допускает разбиение на два непересекающихся подмножества V₁ и V₂ (две доли), причем каждое ребро графа соединяет вершины из разных долей.

Обозначим G = (V₁,V₂, X) двудольный граф G с долями V₁ и V₂. Будем считать, что V₁ V₂.

Двудольный граф G = (V₁,V₂, X) есть полный двудольный граф, если каждая вершина из V₁ соединена ребром с каждой вершиной из V₂.

Паросочетанием Р для двудольного графа G=(V₁,V₂,X) называется любое множество попарно несмежных ребер в G.

Р есть наибольшее паросочетание для G , если число ребер в Р наибольшее среди всех возможных паросочетаний для G.

Р есть максимальное паросочетание (тупиковое) для G, если к Р нельзя добавить ни одного ребра из G, не нарушив условия паросочетаемости.

Р есть совершенное паросочетание для G, если Р имеет V₁ ребер.

Наибольшее паросочетание максимально. Совершенное паросочетание является и наибольшим, и максимальным.

Рассмотрим задачу нахождения наибольшего паросочетания в заданном двудольном графе. Это классическая задача комбинаторики, известная также под названием «задачи о назначениях».

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

Пусть G=(V₁,V₂,X) – произвольный двудольный граф. Построим сеть S(G) с источником s, стоком t (st, s,tV₁V₂,), множеством вершин

, множеством дуг

,

и пропускной способностью c(u,v)=1 для каждой дуги (u,v) X’.

На рис.3 показано построение сети S(G) для некоторого двудольного графа.Отметим, что в сети S(G) существует максимальный нуль-единичный поток, т.е. максимальный поток φ такой, что φ(x)=0 или φ(x)=1 для каждой дуги xX’.

Теорема. Существует взаимно однозначное соответствие между паросочетаниями в G и нуль-единичными потоками в S(G), при котором паросочетанию M={(v₁,u₁), …(v_k,u_k)} мощности k (v_iV₁, u_iV₂ для 1 i  k) соответствует поток φ_М величины k, определяемый следующим образом:

φ_М (s,v_i) = φ_М (v_i,v_j)= φ_М (v_j,t)=1, 1i k,

и φ_М (x)=0 для остальных дуг x сети S(G); потоку φ величины k соответствует паросочетание М_φ, |М_φ|=k, определяемое следующим образом:

М_φ = {(v,u)| vV₁ & uV₂ & φ(v,u)=1}.

Данная теорема позволяет использовать произвольный алгоритм построения максимального потока (целочисленного) для определения наибольшего паросочетания.

Рис.3.

24. Решить задачу нахождения наибольшего паросочетания в двудольном графе, сведя ее к задаче построения максимального потока в транспортной сети и используя первый алгоритм построения максимального потока.

25. Решить задачу нахождения наибольшего паросочетания в двудольном графе, сведя ее к задаче построения максимального потока в транспортной сети и используя алгоритм меток для построения максимального потока.

Замечание. Двудольный граф задавать в виде матрицы смежности, строки которой соответствуют вершинам первой доли, а столбцы – вершинам второй доли.