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

Сентябрь 13, 2022

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

Содержание

2. Введение Сети – это графы, которые моделируют реальные транспортные и коммуникационные сети.
3. Введение Задача о максимальном потоке в сети заключается в том, чтобы подсчитать максимальное количество некоторых объектов,
4. Введение Под объектами могут пониматься - пакеты данных, путешествующих по интернету; - коробки с товарами, которые
5. Введение Эта задача может использоваться при составлении расписания авиарейсов, распределения задач в суперкомпьютерах, обработке цифровых изображений
6. Введение Перемещение объектов могут ограничено пропускной способностью соединений сети или скоростью транспорта на загруженных дорогах.
7. Введение В задаче о максимальном потоке одна их вершин графа назначается истоком – точкой, в которой
8. Сети Сетью называется частично ориентированный граф G(V, E) Истоком и стоком (входным и выходным полюсом) называются
9. Сети Исток - вершина, локальная степень захода которой равна 0. Сток – вершина, локальная степень исхода
10. Сети Если в сети k истоков и m стоков – сеть называется (k,m)- полюсником. Если в
11. Сети Пусть s – исток, t – сток, так что любая другая вершина лежит на пути
12. Сети Разобьем множество вершин V на два подмножества Х и таких, что , а . Множество
13. Сети Ориентированные ребра с началом в Х и концом в называются прямыми. Множество прямых ребер обозначим
14. Сети Ориентированные ребра с началом в и концом в Х называются обратными. Множество обратных ребер обозначим
15. Сети Все неориентированные ребра являются прямыми. Их ориентация произвольна, и определяется при задании потока в сети.
16. Сети Замечание 1: Прямым или обратным ребро будет в зависимости от вида разреза в сети.
17. Пример 1 Дана частично ориентированная двухполюсная сеть.
22. Поток в сети Пусть S произвольная частично ориентированная сеть. Пусть каждому ребру сети приписано число пропускная
23. Поток в сети Потоком в сети S называется пара, составленная из числовой и нечисловой функций (f
24. Поток в сети Функция f удовлетворяет условиям: 1) 2) выполняется закон Киргофа: дивергенция любой внутренней вершины
25. Поток в сети Дивергенция вершины сети – число находимое по формуле:
26. Поток в сети Величина потока в сети S – равна дивергенции потока в вершине s (дивергенция
27. Поток в сети Замечание 2:
28. Поток в сети Замечание 3: Величина потока в сети есть величина переменная, зависящая от значений функции
29. Пример 1 Дана частично ориентированная двухполюсная сеть.
30. Поток в сети Замечание 3: Величина потока в сети есть величина переменная, зависящая от значений функции
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.
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
38. Скачать презентацию

Слайд 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 на два подмножества Х и таких, что

, а .
Множество ребер, реализующих это разбиение назовем разрезом

Слайд 13

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

прямых ребер обозначим

Слайд 14

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

обратных ребер обозначим

Слайд 15

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

потока в сети.

Слайд 16

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

в сети.

Слайд 17

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

Слайд 18

Слайд 19

Слайд 20

Слайд 21

Слайд 22

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

сети приписано число
пропускная способность ребра е

Слайд 23

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

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

Слайд 24

Поток в сети
Функция f удовлетворяет условиям:
1)
2) выполняется закон Киргофа:
дивергенция любой внутренней

вершины сети равна 0.

Слайд 25

Поток в сети
Дивергенция вершины сети – число находимое по формуле:

Слайд 26

Поток в сети
Величина потока в сети S – равна дивергенции потока

в вершине s (дивергенция истока).

Слайд 27

Поток в сети
Замечание 2:

Слайд 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

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

Содержание

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

ВведениеЗадача о максимальном потоке в сети заключается в том, чтобы подсчитать

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

ВведениеЭта задача может использоваться при составлении расписания авиарейсов, распределения задач в

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

ВведениеВ задаче о максимальном потоке одна их вершин графа назначается истоком

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

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

СетиЕсли в сети k истоков и m стоков – сеть

СетиПусть s – исток, t – сток, так что любая другая

СетиРазобьем множество вершин V на два подмножества Х и таких, что

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

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

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

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

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

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

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

Поток в сетиФункция f удовлетворяет условиям:1)2) выполняется закон Киргофа:дивергенция любой внутренней

Поток в сетиДивергенция вершины сети – число находимое по формуле:

Поток в сетиВеличина потока в сети S – равна дивергенции потока

Поток в сетиЗамечание 2:

Поток в сетиЗамечание 3:Величина потока в сети есть величина переменная, зависящая

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

Поток в сетиЗамечание 3:Величина потока в сети есть величина переменная, зависящая

с(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.

Поток в сетиКаждому ребру разреза R ставится в соответствие пропускная способность

с(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

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

Похожие презентации

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

Введение
Задача о максимальном потоке в сети заключается в том, чтобы подсчитать

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

Введение
Эта задача может использоваться при составлении расписания авиарейсов, распределения задач в

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

Введение
В задаче о максимальном потоке одна их вершин графа назначается истоком

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

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

Сети
Если в сети k истоков и
m стоков – сеть

Сети
Пусть s – исток, t – сток, так что любая другая

Сети
Разобьем множество вершин V на два подмножества Х и таких, что

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

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

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

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

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

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

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

Поток в сети
Функция f удовлетворяет условиям:
1)
2) выполняется закон Киргофа:
дивергенция любой внутренней

Поток в сети
Дивергенция вершины сети – число находимое по формуле:

Поток в сети
Величина потока в сети S – равна дивергенции потока

Поток в сети
Замечание 2:

Поток в сети
Замечание 3:
Величина потока в сети есть величина переменная, зависящая

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

Поток в сети
Замечание 3:
Величина потока в сети есть величина переменная, зависящая

с(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.

Поток в сети
Каждому ребру разреза R ставится в соответствие пропускная способность

с(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