В нашей онлайн базе уже более 10821 рефератов!

Список разделов
Самое популярное
Новое
Поиск
Заказать реферат
Добавить реферат
В избранное
Контакты
Украинские рефераты
Статьи
От партнёров
Новости
Крупнейшая коллекция рефератов
Предлагаем вам крупнейшую коллекцию из 10821 рефератов!

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

Дискретная математика (Конспекты 15 лекций)

Страница 10

V – вершина орграфа

M-(V) – множество ребер, для которых вершина V является концом.

M+(V) – множество ребер, для которых вершина V является началом.

Транспортной сетью называется связный орграф без петель, для которого выполнены следующие условия

1. Существует только одна вершина A, для которой M-(А) – пустое множество. А – исток.

2. Имеется только одна вершина B, для которой M+(B) – пустое множество. В – сток.

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

2(1) 3(1) 1(1)

6(0)

5(5)

1(1) 4(1) 2(1)

Потоком в транспортной сети (ТС) называется целочисленная функция, определенная на любых ребрах ТС и удовлетворяющая следующим свойствам

1. ф(X) <= C(X), где С(X) – пропускная способность ребра.

На всех ребрах значение функции потока не превосходит значения пропускной способности ребра. Значение функции потока ставим рядом со значением пропускной способности ребра в скобках.

2. Для каждой внутренней вершины V транспортной сети, не равной A или B выполняется следующее условие: суммарная функция потока по ребрам, входящим в вершину, равна суммарной функции потока по ребрам, исходящим из вершины (сколько втекает, столько и вытекает).

Величиной потока [ф] = val(ф) называется число, равное сумме функций потока по всем ребрам, выходящим из вершины А или сумма всех функций потока по всем ребрам, входящим в вершину В.

Выбор потока.

1. Берем путь из А в В.

2. Выбираем минимальную пропускную способность и ставим ее в соответствие каждому ребру из пути.

3. Просматриваем все остальные ребра. Если они не пересекаются, то проделываем для них то же самое, начиная с п1. Всем остальным ребрам ставим в соответствие значение функции потока, равное 0.

Поток в транспортной сети называется максимальным, если выполнено условие

Val(ф) £ Val(Ф*)

Ф* = maximum

Любое подмножество S транспортных вершин, содержащих исток и не содержащих сток, определяет разрез, отделяющий исток от стока (разрез).

Разрез состоит из всех вершит тех ребер, которые имеют свои начала в вершинах множества S, а концы – из дополнения к множеству S.

Пропускной способностью разреза K называется сумма значений пропускных способностей всех ребер этого разреза.

Разрез K** называется минимальным, если для любого другого разреза выполнено условие C(K**) £ C(K).

Теорема Форда – Фалькерсона (без доказательства).

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

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

1. Берем любой поток в транспортной сети.

2. Строим граф перестроек g* по следующему правилу:

В него входят все вершины исходного графа g.

Те ребра, на которых значение функции потока в исходном графе g были равны 0, входят в новый граф без изменений со своими пропускными способностями.

Все ребра, на которых ф(x) > 0 в новом графе g* заменяются двумя ребрами x* и x**. Ребро x* направлено в ту же сторону, что и x, и пропускная способность c(x*) = c(x) – ф(x).

Ребро x** направлено в противоположную сторону ребру x, и пропускная способность c(x**) = ф(x).

Ребра с нулевой пропускной способностью можно не рисовать.

3. В графе g* ищем путь из А в В по ребрам с ненулевой пропускной способностью. Если его нет, то имеющийся поток является максимальным и алгоритм закончен. Иначе переходим к пункту 4.

(Этот путь называется увеличенной цепью. D = min(c(x)) – минимальное значение пропускной способности этой цепи).

4. Меняем значение функции потока в графе g для тех ребер, которые соответствуют найденному пути в графе перестроек по следующему правилу:

Если направление ребра x в графе g совпадает с направлением пути, то новое ф(x) = ф(x) + D

Если же направление противоположно направлению пути, то ф(x) = ф(x) - D

5. Переходим на шаг 2 с новым потоком.

Название: Дискретная математика (Конспекты 15 лекций)
Раздел: Математика
Дата публикации: 2007-01-22 12:31:01
Прочтено: 21610 раз

1 2 3 4 5 6 7 8 9 [10]

скачать реферат скачать реферат

Новинки
Интересные новости


Заказ реферата
Заказать реферат
Счетчики

Rambler's Top100

Ссылки
Все права защищены © 2005-2019 textreferat.com