3. Барашев В.П., Унучек С.А. Дискретная математика

10. Для построения максимального паросочетания воспользуемся

11.Маршрут v5 7→w2 7→v4 7→w4 7→v3 7→w1 соединяет ненасыщенные вершины v5 и w1.

231

П3

12. Оптимальное распределение работ между работниками:

П3 = {( {v1, w5}, 5), ({v2, w3}, 7), ({v3, w1}, 4),

= ({v4, w4}, 3), ({v5, w2}, 6) };

эфф = 5 + 7 + 4 + 3 + 6 = 25

-суммарная максимальная эффективность всех выполняемых работ.

13.Проверка:

Пример 12.8. Решить задачу об оптимальном назначении с матрицей

Решение.

1. Найдем и подчеркнем максимальные элементы в строке.

232

|П1| = 3 ≠ |V | = 5, паросочетание П1 не является совершенным.

3. Находим множества S и φ(S):

Неподчеркнутых элементов матрицы, значение которых равно сумме соответствующих меток, на данном шаге алгоритма нет. Это означает, что ребра в двудольном графе не добавляются, граф G2 совпадает с G1, паросочетание П2 - с П1.

5. Множества S и φ(S) также остаются без изменений:

S = {v1, v2, v3, v4}, φ(S) = {w2, w3}; |S| = 4 > |φ(S)| = 2.

233

Повышаем и понижаем метки, приписанные тем же вершинам ,

7.S = {v1, v2, v3, v4}, φ(S) = {w2, w3, w4}; |S| = 4 > |φ(S)| = 3.

8.Изменяем метки, приписанные вершинам.

0 3 3 1 0

9. Строим граф G4 и находим в нем полное паросочетание П4 .

234

10. Паросочетание П4 является максимальным, но не является совершенным. Значит, по теореме Холла существует такое множество S V : |S| > |φ(S)|. Так как окружение множества

S = {v1, v2, v3, v4} состоит из 4 вершин: φ(S) = {w1, w2, w3, w4}

(то есть |S| = 4 = |φ(S)|), данное множество нам не подходит.

В качестве множества S возьмем, например, вершины v2 и v4, смежные с одной вершиной w2:

S = {v2, v4}, φ(S) = {w2}; |S| = 2 > |φ(S)| = 1.

11. Понижаем метки у вершин v2 и v4, повышаем метку вершины w2.

Новые ребра не появились; граф G5 совпадает с G4, паросочетание П5 - с П4.

Множества S и φ(S) также остаются без изменений:

S= {v2, v4}, φ(S) = {w2}; |S| = 2 > |φ(S)| = 1.

12.Изменяем метки, приписанные вершинам.

235

14. Оптимальное распределение работ между работниками:

П6 = {( {v1, w1}, 4), ({v2, w4}, 5),

({v3, w3}, 8), ({v4, w2}, 11), ({v5, w5}, 8) };

эфф = 4 + 5 + 8 + 11 + 8 = 36 - суммарная максимальная эффективность всех выполняемых работ.

15. Проверка:

∑5

ai = 4 + 4 + 5 + 6 + 8 = 27;

i=1

∑5

bj = 0 + 5 + 3 + 1 + 0 = 9;

j=1

∑4

ai + bj = 27 + 9 = 36 = эфф (верно).

1

236

12.4Задачи для самостоятельного решения

Решить задачу об оптимальном назначении с заданной матрицей эффективностей.

237

Ответы к задачам для самостоятельного решения

1.эфф = 26;

2.эфф = 22;

3.эфф = 17;

4.эфф = 26;

5.эфф = 46;

6.эфф = 24;

7.эфф = 40.

238

Глава 13

Сети. Потоки.

13.1Основные определения.

Рассмотрим ориентированный граф G =< V, E > без петель, в котором каждой дуге (ребру, имеющему направление) l ставится в соответствие неотрицательное число c(l), называемое пропускной способностью дуги.

Обозначим через M+(v) множество дуг, для которых вершина v является началом; через M−(v) - множество дуг, для которых v - конец.

Определение 13.1. Транспортной сетью G =< V, E > называется ориентированный граф без петель, все дуги l которого имеют пропускную способность c(l) > 0, и имеющий две выделенные вершины v0 и vn такие, что:

Вершина v0 называется источником (все дуги в этой вершине только начинаются и ни одна не заканчивается).

Вершина vn называется стоком (все дуги заканчиваются в стоке и ни одна не начинается).

Все вершины в транспортной сети, отличные от источника и стока, называются промежуточными.

Определение 13.2. Потоком в транспортной сети называется неотрицательная функция φ(l), заданная на дугах сети, такая, что:

239

1.для любой дуги l E выполнено неравенство φ(l) 6 c(l);

2.для всех промежуточных вершин v V выполнено равенство

∑∑

φ(l) = φ(l).

l M−(v) l M+(v)

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

Замечание 13.1. Поток не возникает и не накапливается в промежуточных вершинах.

Транспортная сеть является математической моделью распределения жидкости (например, нефти) или газа в трубопроводе, движения потоков транспорта по сети автодорог и так далее.

Определение 13.3. Величиной потока |φ| называют сумму потоков по дугам, исходящим из источника:

∑

l M+(v0)

Замечание 13.2. Величина потока равна также суммарному потоку, заходящему в сток: ∑

|φ| = φ(l).

l M−(vn)

Определение 13.4. Поток φ в транспортной сети G =< V, E > называется максимальным потоком, если его величина не меньше величины любого потока φ в этой сети: |φ| > |φ|.

Замечание 13.3. Очевидно, что в одной и той же сети может быть несколько максимальных потоков, но их величины совпадают.

240