работа по курсу «Дискретная математика» Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов (стр. 9 из 11)
7(8) 7(7)
0 (1,+) 5 (3,-) 6 (4,+)
1 4(5) 3 6(7) 1(1)  |
3(3) 10(10) 0(3) 13(15)
4 (5,+) Рис. 1.
Присвоим вершине 1 метку 0, тогда вершине 2 присвоим метку (1,+), т.к. φ((1,2))<c((1,2)). Т.к. φ((2,5))=c((2,5)), то переходим к вершине 3, которой присвоим метку (1,+), затем вершине 5 – (3,-), вершине 4 – (5,+), вершине 6 – метку (4,+). Рассмотрим последовательность вершин λ=(6,4,5,2,1), и построим новый поток, величина которого равна 15.
2
(1,+) 
7(8) 7(7)
0 5 6
1 5 (5) 3 5(7) 1(1)
3(3) 10(10) 1(3) 14(15)
4 Рис. 2.
Нетрудно заметить, что улучшить данный поток нельзя.
3.2. Некоторые прикладные задачи
3.2.1 Задачи об источниках и потребителях
В задачах этого типа встречаются три рода объектов: «источники», «потребители», «промежуточные пункты». Источниками могут быть электростанции, заводы, контрольно-измерительные приборы, железнолорожные станции и т.д., которые поставляют соответственно электроэнергию, изделия, информацию, грузы и т.д. для потребителей. В промежуточных пунктах может происходить, например, преобразование электроэнергии, упаковка или комплектация изделий, кодирование информации, перевалка грузов, причем, что весьма существенно, без изменения количества грузов. Источники, промежуточные пункты и потребители связаны сетью линий передач или автомобильными, железнодорожными, морскими линиями или каналами связи с заданными пропускными способностями.
Пусть в некоторую единицу времени источники xj (j=1,2,..,k) вырабатывают aj единиц продукции, а потребность потребителя yi (I=1,2,..,m) в этой продукции равна bi. Пропускные способности линий считаются также отнесенными к выбранной единице времени. Таким образом, в задачах этого типа идет речь о неизменном и однородном по времени стационарном потоке.
С каждой такой задачей свяжем транспортную сеть D. Вершинами сети D служат источники, потребители, промежуточные пункты и еще две вспомогательные вершины: вход x0 и выход z. Вершину x0 свяжем дугами (x0,xj) (j=1,..,k) с источниками и припишем им пропускные способности aj. Потребителей yi свяжем с выходом z дугами (yi,z) с пропускными способностями bi. Остальные вершины соединим между собой дугами с соответствующими пропускными способностями в соответствии с реальным наличием связей между ними.
Возникает задача о нахождении такого распределения потока энергии (грузов, информации и т.д.) по линиям, чтобы в максимальной степени (желательно полностью) удовлетворить потребителей. Очевидно, что эта задача об отыскании потока наибольшей величины на транспортной сети D.
ЗАДАНИЕ 22. Решить задачу об источниках и потребителях, сведя ее к задаче построения максимального потока в транспортной сети и используя первый алгоритм построения максимального потока .
ЗАДАНИЕ 23. Решить задачу об источниках и потребителях, сведя ее к задаче построения максимального потока в транспортной сети и используя второй алгоритм – алгоритм меток для построения максимального потока.
3.3. Двудольные графы и паросочетания
Рассмотрим задачу о назначении на должности. Пусть в некотором учреждении имеется 6 вакантных должностей y1,y2,…,y6 и 6 работников x1,x2,…,x6. Граф D, изображенный на рис.5, иллюстрирует, какие должности y может в силу своей квалификации занимать работник x. Пусть выполнено условие: каждый работник может занимать только одну должность, и каждая работа выполняется только одним работником. Тогда решение этой задачи сводится к построению наибольшего паросочетания в данном двудольном графе.
x1 x2 x3 x4 x5 x6 
y1 y2 y3 y4 y5 y6Рис. 5.
3.3.1 Нахождение наибольшего паросочетания в двудольном графе
Граф G = (V,X) называется двудольным, если множество V его вершин допускает разбиение на два непересекающихся подмножества V1 и V2 (две доли), причем каждое ребро графа соединяет вершины из разных долей.
Обозначим G = (V1,V2, X) двудольный граф G с долями V1 и V2. Будем считать, что çV1ç£ çV2ç.
Двудольный граф G = (V1,V2, X) есть полный двудольный граф, если каждая вершина из V1 соединена ребром с каждой вершиной из V2.
Паросочетанием Р для двудольного графа G=(V1,V2,X) называется любое множество попарно несмежных ребер в G.
Р есть наибольшее паросочетание для G , если число ребер в Р наибольшее среди всех возможных паросочетаний для G.
Р есть максимальное паросочетание (тупиковое) для G, если к Р нельзя добавить ни одного ребра из G, не нарушив условия паросочетаемости.
Р есть совершенное паросочетание для G, если Р имеет çV1ç ребер.
Наибольшее паросочетание максимально. Совершенное паросочетание является и наибольшим, и максимальным.
Рассмотрим задачу нахождения наибольшего паросочетания в заданном двудольном графе. Это классическая задача комбинаторики, известная также под названием «задачи о назначениях».
Оказывается, что задачу нахождения наибольшего паросочетания в двудольном графе можно свести к задаче построения максимального потока в некоторой сети.
Пусть G=(V1,V2,X) – произвольный двудольный граф. Построим сеть S(G) с источником s, стоком t (s¹t, s,tÏV1ÈV2,), множеством вершин
, множеством дуг 
,и пропускной способностью c(u,v)=1 для каждой дуги (u,v) ÎX’.
На рис.3 показано построение сети S(G) для некоторого двудольного графа.Отметим, что в сети S(G) существует максимальный нуль-единичный поток, т.е. максимальный поток φ такой, что φ(x)=0 или φ(x)=1 для каждой дуги xÎX’.
Теорема. Существует взаимно однозначное соответствие между паросочетаниями в G и нуль-единичными потоками в S(G), при котором паросочетанию M={(v1,u1), …(vk,uk)} мощности k (viÎV1, uiÎV2 для 1£ i £ k) соответствует поток φМ величины k, определяемый следующим образом:
φМ (s,vi) = φМ (vi,vj)= φМ (vj,t)=1, 1£i£ k,