Летние международные олимпиады для 1-11 классов Участвовать→
Конкурс разработок «Пять с плюсом» июнь 2021
Добавляйте свои материалы в библиотеку и получайте ценные подарки
Конкурс проводится с 1 июня по 30 июня

Конспект лекции по теме "Потоки в транспортных сетях"

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

Тема: Потоки в транспортных сетях

 

Трансnортной сетью называется пара T=(G,C), где:

image G – это взвешенный орграф , удовлетворяющий следующим условиям: а) нет петель;

б) существует только одна вершина, не имеющая ни одного прообраза - это исток;

в) существует только одна вершина, не имеющая ни одного образа - это сток;

image С - функция пропускных способностей дуг, которая является положительной

вещественной функцией, определенной на множестве дуг графа

Пропускная способность дуги V – это положительное число С(v), которое поставлено в соответствие каждой дуге графа.

Простая цепь – это цепь, в которой все вершины различны

Вершина ,не имеющая ни одного прообраза называется входом сети или источником и обычно обозначается Vo.

Вершина, не имеющая ни одного образа называется выходом сети или стоком и обозначается U0

В транспортной сети существует один исток и один сток. 

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

1.   Ограниченности: поток по любой дуге сети не превосходит пропускной способности этой

дуги;

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

равен суммарному потоку, выходящему из этой вершины.

Дуга сети называется насыщенной, если поток по этой дуге равен пропускной способности

этой дуги.

Поток по пути называется полным, если хотя бы одна дуга пути насыщена.

Величиной потока называется сумма значений этой функции по всем выходным дугам сети. 

Понятия потока и величины потока в сети часто путают, однако между ними существует различие: поток - это функция, а величина потока - число.

Разрезом сети называется множество, которому принадлежит исток и не принадлежит сток.

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

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

Разрез называется минимальным, если имеет наименьшую пропускную способность.

Отыскание минимального разреза - одна из основных задач анали за транспортных сетей.

Пусть Т=(V, X, s, t, с, f) - транспортная сеть с пропускной способностью с: Х→Nи потоком f:

XN, максимально возможная величина которого cmin

Говорят, что дуга х в сети Т является насыщенной, если f(х) = с(x).

Теорема (Форда - Фалкерсона о максимальном потоке): Любая транспортная сеть Т = (V,

X, s, t, с, f) имеет максимальный поток и его величина равна сmin-

 

Пример 1

Пусть дана сеть Т = (V, X, s, t, с, f) (рис. 1). Здесь V={s, t, 1, 2, 3, 4, 5}; X={x1, ..., x12},

отношение инцидентности задается списком: x1=(s, 1); х2=(s, 2); х3=(s, 3); х4=(2, 3); х5=(2, 1), х6=(1, 4), х7=(2, 5), х8=(3, 5), х9=(3, t);

х10=(5, 4); х11=(4, t); x12 = (5, t);

пропускная способность сети: с={<х1, 8>, <х2, 10>, < х3, 11>, < X4, 2>, < x5, 3>, <х6, 6>,

7, 9>, <х8, 2>, <х9, 6>> <х10, 4>, <х11, 12>, <х12, 7>}.

Требуется построить максимальный поток.

image 

Рис. 1 Транспортная сеть

Решение

1.                        Исходим из начального нулевого потока f0i)=0, i=1, ..., 12.

2.                        Перебираем все возможные простые цепи (теорема 1) с дугами прямой направленности из s в t, по которым возможно увеличение потока:

L1 - s, x2, 2, х5, 1, x6, 4, x11, t;

L2 - s, x1, 1, x6, 4, x11, t;

L3 - s, x2, 2, x4, 3, х9, t;

L4-s, x3, 3, x9, t;

L5 - s, x3, 3, x8, 5, х10, 4, х11, t; L6 - s, x2, 2, х7, 5, x12, t.

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

Таблица 1 Простые цепи с дугами прямой направленности

Поток

х1

х2

х3

х4

х5

х6

х7

х8

х9

х10

х11

х12

min

с(х)

8

10

11

2

3

6

9

2

6

4

12

7

 

f0(x)

0

0

0

0

0

0

0

0

0

0

0

0

 

L1, δ1

 

10

 

 

3

6

 

 

 

 

12

 

3

f1=f0+3

0

3

0

0

3

3

0

0

0

0

3

0

 

L2, δ2

8

 

 

 

 

3

 

 

 

 

9

 

3

f2=f1+3

3

3

0

0

3

6

0

0

0

0

6

0

 

L3, δ3

 

7

 

2

 

 

 

 

6

 

 

 

2

f3=f2+8

3

5

0

2

3

6

0

0

2

0

6

0

 

L4, δ4

 

 

11

 

 

 

 

 

4

 

 

 

4

f4=f3+3

3

5

4

2

3

6

0

0

6

0

6

0

 

L5, δ5

 

 

7

 

 

 

 

2

 

4

6

 

2

f5=f4+4

3

5

6

2

3

6

0

2

6

2

8

0

 

L6, δ6

 

5

 

 

 

 

9

 

 

 

 

7

5

f6=f5+9

3

10

6

2

3

6

5

2

6

2

8

5

 

 

Полученный поток f6 является полным, так как все возможные простые цепи дуг прямой

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

3) Перебираем все простые неориентированные цепи в сети Т из s в t и увеличиваем полный поток, полученный на предыдущем шаге согласно теореме 2. Из этой теоремы следует, что упомянутые цепи не должны включать насыщенные дуги прямой направленности, а также нулевые дуги обратного направления. Исходя из этого, строим цепи в рассматриваемом примере;

L7 - s, x1, 1, x5, 2, х7, 5, t;

L8 - s, x1, 1, x5, 2, х7, 5, х10, 4, х11, t;

L9 - s, x3, 3, x4, 2, х7, 5, х10, 4, х11, t;

В таблице 2 указаны значения промежуточных потоков. Стрелками помечены дуги обратной

направленности, вошедшие в простые цепи. Как и в табл. 1. насыщенные дуги выделены жирным шрифтом.

Таблица 2

Простые цепи с дугами как прямой, так и обратной направленности

image

Дальнейшее увеличение потока невозможно. Максимальная величина потока (в дугах

истока, как и в дугах стока), а также в минимальном сечении  Рmin = {x6, x7, x8, x12} равна: Mf=cmin = 23.

Информация о публикации
Загружено: 26 марта
Просмотров: 128
Скачиваний: 0
Фоминых Ирина Владимировна
Прочее, СУЗ, Уроки

Проверьте знания своих учеников интересными заданиями

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

Скачать материал