Дискретная математика. Сети. Потоки в сетях

1. Дискретная математика

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

2. Введение

Сети – это графы, которые
моделируют реальные
транспортные и
коммуникационные сети.

3. Введение

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

4. Введение

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

5. Введение

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

6. Введение

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

7. Введение

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

8. Сети

Сетью называется частично
ориентированный граф G(V, E)
Истоком и стоком (входным и
выходным полюсом)
называются некоторые
отмеченные вершины.

9. Сети

Исток - вершина,
локальная степень захода
которой равна 0.
Сток – вершина, локальная
степень исхода которой
равна 0.

10. Сети

Если в сети k истоков и
m стоков – сеть называется
(k,m)- полюсником.
Если в сети 1 исток и 1 сток, сеть
называется двухполюсной.
Далее будем рассматривать
только двухполюсные сети.

11. Сети

Пусть s – исток, t – сток, так что
любая другая вершина лежит
на пути из вершины s в t.
Вершины, не являющиеся
истоком и стоком называются
внутренними вершинами
сети.

12. Сети

Разобьем множество вершин V
на два подмножества Х и Х
таких, что s Х , а t Х .
Множество ребер,
реализующих это разбиение
назовем разрезом R X, Х .

13. Сети

Ориентированные ребра с
началом в Х и концом в Х
называются прямыми.
Множество прямых ребер
обозначим
E
-
R

14. Сети

Ориентированные ребра с
началом в Х и концом в Х
называются обратными.
Множество обратных ребер
обозначим
E
R

15. Сети

Все неориентированные
ребра являются прямыми.
Их ориентация произвольна,
и определяется при задании
потока в сети.

16. Сети

Замечание 1:
Прямым или обратным ребро
будет в зависимости от вида
разреза в сети.

17. Пример 1

Дана частично ориентированная
двухполюсная сеть.

18.

X s,1, 3 ; X t, 2, 4 .
R X, X 1,2 , 3,4 , 4,1 .
E R 1,2 , 3,4 ; E R 4,1 .

19.

X s, 3, 4 ; X t,1, 2 .
R X, X s,1 , 1,3 , 4,1 , 2,4 , 4, t .
E R s,1 , 1,3 , 4,1 , 2,4 , 4, t ;
E R пусто.

20.

X s,1, 2 ; X t, 3, 4 .
R X, X s,3 , 1,3 , 4,1 , 2,4 , 2, t .
E R s,3 , 1,3 , 2,4 , 2, t ;
E R 4,1 .

21.

X s,1, 3, 4 ; X t, 2 .
R X, X 1,2 , 2,4 , 4, t .
E R 1,2 , 2,4 , 4, t ;
E R пусто

22. Поток в сети

Пусть S произвольная частично
ориентированная сеть.
Пусть каждому ребру сети e E
приписано число
с(e) 0,
пропускная способность ребра е

23. Поток в сети

Потоком в сети S называется пара,
составленная из числовой и
нечисловой функций (f ,w):
w – ориентация всех
неориентированных ребер сети,
f =f(e) – функция значений потока
на ребрах.

24. Поток в сети

Функция f удовлетворяет условиям:
1) 0 f (e) c(e), e E;
2) выполняется закон Киргофа:
дивергенция любой внутренней
вершины сети равна 0.

25. Поток в сети

Дивергенция вершины сети –
число находимое по формуле:
R (a)
f e
e a
f e .
e a
a ребра, выходящие из а;
a ребра, входящие в а.

26. Поток в сети

Величина потока в сети S –
равна дивергенции потока в
вершине s (дивергенция истока).
R R ( s)

27. Поток в сети

Замечание 2:
R ( s ) R t .

28. Поток в сети

Замечание 3:
Величина потока в сети есть
величина переменная,
зависящая от значений
функции f(e).

29. Пример 1

Дана частично ориентированная
двухполюсная сеть.

30. Поток в сети

Замечание 3:
Величина потока в сети есть
величина переменная,
зависящая от значений
функции f(e).

31.

с(a)=2; c(b)=3; c(h)=1; c(d)=2;c(q)=1;
c(w)=1; c(x)=3; c(y)=2; c(z)=2.

32.

33.

34. Поток в сети

Каждому ребру разреза R
ставится в соответствие
пропускная способность
разреза с(R), равная сумме
пропускных способностей всех
прямых ребер разреза.

35.

с(a)=2;c(b)=3;c(h)=1;c(d)=2;
c(q)=1;c(w)=1;c(x)=3;c(y)=2;
c(z)=2. C=c(w)+c(d)=3+1=4

36.

C=c(b)+c(h)+c(x)+c(y)=3+1+3+2=9

37. Поток в сети

Теорема Форда-Фалкерсона
Максимальная величина
потока в сети S равна
минимальной пропускной
способности среди всех ее
разрезов.