Шапорев С.Д. Дискретная математика - файл n11.doc

приобрести
Шапорев С.Д. Дискретная математика
скачать (1595.4 kb.)
Доступные файлы (14):
n1.doc1008kb.24.06.2000 17:47скачать
n2.doc580kb.29.02.2000 18:08скачать
n3.doc957kb.07.03.2000 15:50скачать
n4.doc492kb.24.06.2000 17:37скачать
n5.doc1198kb.19.04.2000 15:24скачать
n6.doc985kb.19.04.2000 21:35скачать
n7.doc771kb.07.05.2000 17:26скачать
n8.doc992kb.08.05.2000 16:38скачать
n9.doc217kb.08.05.2000 19:26скачать
n10.doc1581kb.26.03.2000 20:59скачать
n11.doc1011kb.31.03.2000 22:04скачать
n12.doc1025kb.31.03.2000 22:09скачать
n13.doc1691kb.05.04.2000 16:10скачать
n14.doc960kb.09.04.2000 12:05скачать

n11.doc





страницы.

Шаг1. Ш.

Первая итерация. Шаг 2.

.

Шаг 3. , переход на начало второго шага.

Вторая итерация. Шаг 2.

.

Шаг 3. , переход на начало второго шага.

Третья итерация. Шаг 2.

.

Шаг 3. , переход на начало второго шага.

Четвертая итерация. Шаг 2.

.

Шаг 3. , переход на начало второго шага.

Пятая итерация. Шаг 2. Ш,

.

Шаг 3. . Итак, получен остовный граф. изображен на рисунке справа, его вес

Исходный граф Остовный граф





12

5 5 6 4 5 5 6 4

14

10 7 9 9


§ 4.11. Потоки в сетях.
Функциональное назначение большинства физически реализованных сетей состоит в том, что они служат носителями систем потоков, то есть систем, в которых некоторые объекты текут, движутся или транспортируются по системе каналов (дуг сети) ограниченной пропускной способности. Примерами могут служить поток автомобильного транспорта по сети автодорог, поток грузов по участку железнодорожной сети, поток воды в городской сети водоснабжения, поток электрического тока в электросети, поток телефонных или телеграфных сообщений по каналам связи, поток программ в вычислительной сети. Ограниченная пропускная способность означает, что интенсивность перемещения соответствующих предметов по каналу ограничена сверху определенной величиной.

Наиболее часто в сети решается задача о максимальном потоке и минимальном разрезе. При этом граф должен удовлетворять следующим условиям:

1). - связный граф без петель;

2). существует ровно одна вершина, не имеющая предшествующих; эта вершина называется источником и обозначается ;

3). существует ровно одна вершина, не имеющая последующих; эта вершина называется стоком и обозначается ;

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

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

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

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

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

Множество дуг, начала которых лежат в , а концы в , называется ориентированным разрезом и обозначается . Следовательно,

. (4.11.1)

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

(4.11.2)

I разрез На рисунке слева изображена сеть, на кото-

1 рой около каждого ребра указана его пропус-

3 II разрез кная способность. Произведены два разреза I

2 5 и II. При разрезе I вершины оказались раз-

7 7 4 биты на подмножества и

, а ребрами, образующими раз-

рез стали ребра . При

разрезе II , а , разрез образуют ребра .
§ 4.12. Теорема Форда – Фалкерсона.
Теорема. Для любой сети с одним источником и одним стоком величина максимального потока в сети от источника к стоку равна величине минимального разреза.

Алгоритм Форда – Фалкерсона построения максимального потока и минималь-ного разреза основан на следующих обстоятельствах.

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

  2. Рассмотрим произвольный маршрут (неориентированный путь) из в . Дуги, образующие этот маршрут, естественным образом делятся на два типа: прямые (ориентированные от к ) и обратные (ориентированные от к ). Пусть существует путь, в котором прямые дуги не насыщены, а потоки на обратных дугах положительны. Пусть - минимальная из остаточных пропускных способностей прямых дуг, а - минимальная из величин потоков обратных дуг. Тогда поток в сети можно увеличить на величину , прибавляя к потокам на прямых дугах и вычитая из потоков на обратных дугах. Очевидно, что при этом условие баланса (условие сохранения потока) для узлов, входящих в рассматриваемый маршрут, не нарушится. Ясно, что если множество обратных дуг не пусто, то при такой

процедуре увеличения потока в сети фактического

перемещения объектов вдоль рассматриваемого

маршрута не происходит, так как оно в принципе

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

Ясно также, что первая процедура является частным случаем второй.

Пример. Пропускные способности дуг заданы следующей матрицей. Построить максимальный поток от к и указать минимальный разрез, отделяющий от .

Этап 1. Путь

Увеличим по этому пути поток до 12 единиц, ребро становится насыщенным. Поставим величину потока на дугах и .



Форд (1-1 г.г.) - американский математик.
Путь

15 Поток можно

11(14) увеличить на три единицы. Дуга

12(12) 7(8) 7(7) станет насыщенной.

Путь

11(13) 15(15) Можно увеличить поток на семь единиц;

Дуга станет насыщенной, потоки

Разрез на дугах примут вид

8(8)

Больше путей нет. Конец первого этапа.

Этап 2. Рассмотрим теперь маршруты, содержащие противоположные дуги.

Маршрут Поток можно увеличить на единицу на дуге . Тогда потоки по дугам этого маршрута станут такими Дуга стала насыщенной.

Больше маршрутов нет. Поток максимален. Делаем разрез вокруг по насыщенным дугам и получаем его величину 15+8=23 единицы.



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

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

, (4.13.1)

где - поток по дуге при ограничениях

1).

2). для начальной вершины - уравнение истока,

3). для конечной вершины - уравнение стока,

4). для любой другой вершины - условие сохранения потока.

Если - кратчайший путь от к в сети , - минимальная из пропускных способностей дуг, входящих в путь , и если , то задача имеет тривиальное решение – весь поток направляется вдоль пути . Общее решение задачи о потоке минимальной стоимости строится следующим образом. Сначала находится кратчайший путь от к и величина максимально возможного потока вдоль этого пути. Если окажется, что , то задача решена. В противном случае сеть модифицируют специальным образом. Затем опять находят кратчайший путь от к и максимально возможный поток вдоль этого пути в модифицированной сети. Процедуры модификации сети и нахождения кратчайшего пути в ней повторяются до тех пор, пока либо нужное количество не будет переправлено, либо возникнет сеть, в которой нет пути от к , что означает отсутствие решения у исходной задачи.

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

Модифицированная относительно данного потока сеть строится следующим образом.

1). , то есть число и набор вершин в модифицированной сети не меняется.

2). , где - некоторое множество фиктивных дуг. Таким образом, после модификации число дуг сети увеличивается.

3). Если , то дуга включается в множество . При этом полагается Этот пункт применяется только к дугам, по которым проходит поток , относительно которого происходит модификация сети.

4). Для всех ненасыщенных дуг, где нет противоположного потока, в том числе и для ненасыщенных дуг с потоком, относительно которого происходит модификация сети, то есть для полагают .

5). Для всех насыщенных дуг полагают

Это довольно сложный и «длительный» алгоритм. Нахождение кратчайшего пути как в исходной, так особенно в модифицированной сети может потребовать использования алгоритма Беллмана – Мура. Кроме того решение типичных учебных задач требует три – четыре итерации алгоритма.

Рассмотрим подробный пример. Пусть матрицами и заданы пропускные способности дуг сети и стоимости транспортировки единичного потока вдоль всех дуг. Требуется: 1) построить максимальный поток от к и указать минимальный разрез, отделяющий от ;

2) построить поток величины , имеющий минимальную стоимость, здесь - целая часть числа.

Построим рисунок соответствующей сети. Первое число на дугах соответствует стоимости транспортировки единичного потока вдоль этой дуги; второе число – пропускная способность дуги.

1). Построим максимальный поток от вершины к вершине по алгоритму Форда – Фалкерсона.



Этап 1. Путь

9(6) . Увеличим по этому пути

поток до 11 единиц, ребро станет на-

9(13) сыщенным. Второй возможный путь

7(11) 9(14)

12(11) . Поток по этому пу-

10(11) 13(17) 9(10) ти равен 10 единицам. Дуга станет на-

сыщенной. Третий путь, по которому возмо-

9(13) жен ненулевой поток – это путь

Здесь . По этому пути можно увеличить поток лишь на единицу, при этом дуга станет насыщенной. Больше путей нет.

Этап 2. Рассмотрим маршруты с противоположными ребрами. Маршрут Поток можно увеличить на две единицы на дуге . Эта дуга станет насыщенной. Тогда потоки по этому маршруту будут такими Больше маршрутов нет. Поток максима-

лен. На рисунке слева на дугах графа стоят

6(2) две цифры: первая – пропускная способность

I II дуги, вторая – поток по дуге ( насыщенные

13(13) дуги выделены). Теперь можно сделать нес-

11(-2) 9 колько разрезов, например, отделяя исток и

11(11) сток. И по первому I, и по второму II разрезу

11(11) 17(14) 10(10) поток одинаков единицы.

2). Построим теперь поток величины

13(10) единиц. По рас-

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

Этап 1. Шаг 1.

Первая итерация. Шаг 2. , ,

.

Шаг 3. .

Шаг 4. Нет. Переход на начало второго шага.

Вторая итерация. Шаг 2. , .

Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации