работа по курсу «Дискретная математика» Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов (стр. 8 из 11)

Рис. 3.

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

Число ребер в наибольшем паросочетании графа G называется числом паросочетания и обозначается a₁(G).

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

1. V₁ = X,

2. вершины х₁ и х₂ смежны в L(G) тогда и только тогда, когда ребра х₁ и х₂ смежны в G.

Рис. 4

На рис. 4 изображены два графа – G и L(G). Вершины графа G – темные кружки, вершины графа L(G) – светлые кружки. Ребра графа G – тонкие линии, ребра графа L(G) – жирные линии.

ЗАДАНИЕ 20. Найти все максимальные паросочетания в заданном графе, используя алгоритм с возвратом для нахождения независимых множеств вершин реберного графа.

ЗАДАНИЕ 21. Найти наибольшее паросочетание в заданном графе, используя алгоритм с возвратом для нахождения независимых множеств вершин реберного графа.

Раздел 3. Потоки в сетях и родственные задачи

3.1. Потоки в сетях

3.1.1 Полный поток в транспортной сети

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

Введем основные понятия данной теории.

Транспортной сетью называется орграф D = (V,X) с множеством вершин V = {v₁,…,v_n}, для которого выполняются условия:

1) существует одна и только одна вершина v₁, называемая источником, такая, что Г^-1 (v₁) = Æ (т.е. ни одна дуга не заходит в v₁),

2) существует одна и только одна вершина v_n, называемая стоком, такая, что Г(v_n) = Æ (т.е. из v_n не исходит ни одной дуги),

3) каждой дуге xÎX поставлено в соответствие целое число c (x) ³ 0, называемое пропускной способностью дуги.

Функция j(x), определенная на множестве X дуг транспортной сети D и принимающая целочисленные значения, называется допустимым потоком (или просто потоком) в транспортной сети D, если

1) для любой дуги xÎX величина j(x), называемая потоком по дуге x, удовлетворяет условию 0 £ j(x) £ c(x),

2) для любой промежуточной вершины v сумма потоков по дугам, заходящим в v, равна сумме потоков по дугам, исходящим из v.

Величиной потока j в транспортной сети D называется величина, равная сумме потоков по всем дугам, заходящим в сток, или, что то же самое сумме потоков по всем дугам, исходящим из источника.

Дуга xÎX называется насыщенной, если поток по ней равен ее пропускной способности. Поток j называется полным, если любой путь в сети из источника в сток содержит, по крайней мере, одну насыщенную дугу.

А л г о р и т м

построения полного потока в сети

Данные: транспортная сеть D, заданная матрицей пропускных способностей дуг.

Результат: полный поток в сети.

1) Полагаем для любой дуги xÎХ j(x) = 0 ( начинаем с нулевого потока ).

2) Полагаем D* = D.

3) Удаляем из орграфа D* все дуги, являющиеся насыщенными при потоке j в транспортной сети D. Полученный орграф снова обозначим через D*.

4) Ищем в D* простую цепь m из v₁ в v_n . Если такой цепи нет, то j - искомый полный поток в транспортной сети D. В противном случае переходим к шагу 5.

5) Увеличиваем поток j(x) по каждой дуге x из m на одинаковую величину a>0 такую, что, по крайней мере, одна дуга из m окажется насыщенной, а потоки по всем остальным дугам из m не превышают их пропускных способностей. При этом величина потока j также увеличится на a, а сам поток j в транспортной сети D остается допустимым. После этого перейдем к шагу 3.

3.1.2 Максимальный поток

Поток j называется максимальным, если его величина принимает максимальное значение по сравнению с другими допустимыми потоками в транспортной сети D. Максимальный поток всегда является полным (обратное, вообще говоря, неверно).

Введем для заданной транспортной сети D и допустимого потока j в этой сети орграф приращений I(D,j), имеющий те же вершины, что и сеть D. Каждой дуге x = (v,w) Î X транспортной сети D в орграфе приращений I(D, j) соответствуют две дуги: x и x* = (w,v) – дуга, противоположная по направлению дуге x. Припишем дугам x и x* орграфа приращений I(D, j) длину l:

0, если j(x) < c(x),

l(x) =

¥, если j(x) = c(x),

0, если j(x) > 0,

l(x*) =

¥, если j(x) = 0.

А л г о р и т м

построения максимального потока

Данные: транспортная сеть D, заданная матрицей пропускных способностей дуг.

Результат: максимальный поток в сети.

1) Полагаем i = 0. Пусть j₀ – любой допустимый поток в транспортной сети D (например, полный или нулевой).

2) По сети D и потоку j_i строим орграф приращений I(D, j_i).

3) Находим простую цепь m_i, являющуюся минимальным путем из v₁ в v_n в нагруженном орграфе I(D, j_i) (можно использовать любой описанный выше алгоритм). Если длина этой цепи равна ¥, то поток j_i максимален и работа алгоритма заканчивается. В противном случае увеличиваем поток вдоль цепи m_i на максимально допустимую величину a_i > 0, где a_iÎZ (прибавляя ее для каждой дуги xÎX, через которую проходит цепь m_i, к уже имеющейся величине потока по дуге x, если дуга x входит в m_i, и вычитая, если дуга x* входит в m_i), такую, что при этом сохраняется условие допустимого потока. В результате меняется поток в транспортной сети D, т.е. от потока j_i переходим к потоку j_i+1, который является допустимым, и при этом величина его увеличивается на a_i. Присваиваем i = i + 1 и переходим к шагу 2.

Алгоритм меток для нахождения максимального потока

Рассмотрим другой алгоритм построения максимального потока в транспортной сети, использующий метки вершин.

Помечивающий алгоритм Форда – Фалкерсона

для нахождения максимального потока

Данные: транспортная сеть D, заданная матрицей пропускных способностей дуг.

Результат: максимальный поток в сети.

1) Построить произвольный поток φ на транспортной сети D (например, положить φ(u) = 0 для любой дуги u ).

2) Просмотреть пути, соединяющие вход сети v₁ с выходом v_n. Если поток φ полный, то перейти к п.4.

3) В противном случае рассмотреть путь μ, соединяющий вход сети v₁ с выходом v_n, все дуги которого не насыщены. Построить новый поток φ´:

где

. Повторить этот процесс до получения

полного потока φ.

4) Присвоить целочисленные метки вершинам сети D и знаки «+» или «-» дугам по правилам:

· входу v₁ присвоить метку 0,

· если вершина v_i получила некоторую метку, а y - еще непомеченная вершина, то вершине y

Гv_i, такой что φ((v_i,y))<c((v_i,y)) присвоить метку i, а дуге (v_i,y) – знак «+»; вершине y Г^-1v_i , такой, что φ((y,v_i))>0, присвоить метку i, а дуге (y,v_i) – «-». Остальные непомеченные вершины и дуги метки и знаки не получают;

· повторять процесс, описанный в предыдущем пункте до тех пор, пока не прекратится появление новых отмеченных вершин и дуг. Если в результате выполнения этого пункта вершина v_n не получит метки, то поток является максимальным. В противном случае перейти к п.5.

5) Рассмотреть последовательность отмеченных вершин λ=(v_n, v_i1, v_i2,…,v₁), каждая из которых имеет метку, равную номеру последующей вершины, и последовательность μ (не обязательно путь), соединяющих последовательные вершины из λ. Построить новый поток φ´:

Перейти к пункту 4.

Пример. Рассмотрим транспортную сеть D и полный поток φ, для которого

= 14:

2

(1,+)