2. Задача распределения ресурсов

Необходимо выполнить некоторое множество работ. Имеется множество S: - множество ресурсов, необходимое для выполнения этих работ. Каждая работа может использовать часть ресурсов. Одновременно выполняются работы, использующие разные ресурсы. Все работы выполняются за одно и то же время t. Необходимо распределить ресурсы так чтобы общее время выполнения было минимальным.

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

3. Задача экономии памяти

Пусть дана блок-схема.

Тогда граф будем строить по временной диаграмме:

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

Осталось только этот граф правильно раскрасить.

Итого для хранения сколько там у нас было переменных? Надо всего 5 мест.

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

В общем случае граф называется k-связным, если удаление k-1 вершины не приведёт к расчленению графа. Альтернативно: граф будет являться k-связным тогда, и только тогда когда между любой парой его вершин существует не менее k различных простых маршрутов

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

=-=-=-=-=-=-=

Пусть N=(G,α) – сеть на графе G с пропускной способностью дуг α. a – исток, b – сток этой сети. Потоком через сеть N называется функция

множество дуг во множество неотрицательных вещественных чисел, удовлетворяющее двум условиям:

- Поток, проходящий по дуге e не может превышать её пропускной способности.

2) Для любой вершины, кроме стока и истока, полустепень исхода равна полустепени захода.

Грубо говоря, сколько вошло, столько и вышло.

Лемма. Сумма потоков через дуги, инцидентные стоку, равна сумме потоков инцидентных дуг истоку.

Разрезом сети, имеющей один сток и один исток, называется множество дуг S, такое что любой путь от источника до стока будет проходить хотя бы через одну дугу этого множества. Пропускной способностью разреза называется сумма пропускных способностей входящих в него дуг. Разрез называется минимальный, если он имеет наименьшую пропускную способность α(S) среди всех разрезов сети.

Разрезы:

Теорема Форда-Фолкерсона (1955 год)

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

Лемма 1

Величина любого потока через сеть не превосходит пропускной способности любого разреза этой сети.

Лемма 2

Пусть ϕ – ненулевой поток через сеть N с источником a и стоком b. Тогда существует простой путь из вершины a в b, проходящий по дугам с ненулевым потоком.

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

Дана сеть N=(G,α). a – исток, b – сток.

Шаг 1. Если не существует пути из источника в сток, то положить ϕ = 0 и перейти к шагу 4. Иначе выбрать непустое множество T непересекающихся по дугам путей из a в b, Причём если то положить Поток для каждой дуги, образующий некоторый путь из a в b обладает максимальной пропускной способностью дуги, в него входящей.

Для дуг e, через которые не проходят пути из T, положить ϕ(e)=0, в результате получаем ненулевой поток через сеть N.

Шаг 2. Исходя из сети N и потока ϕ построить сеть N’=(G’,α‘) следующим образом:

1. V’=V; Граф G’ имеет те же самые узлы, что и G.

2. Если e – дуга графа G (e∈E), и α(e)-ϕ(e)≠0 (есть ещё резерв в дуге), то e будет принадлежать графу G’, причём α’(e)=α(e)-ϕ(e)

3. Если e – дуга графа G, такая что ϕ(e)≠0, то вводим дугу ê обратной ориентацией, нежели e, причём α’(ê)=ϕ(e).

4. Если возникают кратные дуги (одинаковые по инцидентности), например то вводим вместо них одну дугу e и полагаем

Шаг 3.

a) Если в сети (G’,α’) не существует пути из a в b, то перейти к шагу 4, иначе в сети N’ построить ненулевой поток ϕ, как это описывается на шаге 1.

b) Для сети (G,α) положить ϕ=ϕ+ϕ’ (накопление ответа) и перейти к шагу 2.

Шаг 4. Вывод ϕ. Стоп.

Можно было выбрать другое множество T.

На графе G’ находим пути из A в B, если они есть, используя как прямые, так и обратные (зелёненькие) дуги. Такой путь есть –

заметим, что для дуги

Переходим ко второй итерации алгоритма, на котором рассматриваем уже потоки с учётом ϕ’, т.е.

На этом графе нет путей ненулевого потока. ϕ=5. Стоп.