Similar presentations:
Дискретная математика. Сети. Потоки в сетях
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=937. Поток в сети
Теорема Форда-ФалкерсонаМаксимальная величина
потока в сети S равна
минимальной пропускной
способности среди всех ее
разрезов.