Дискретная математика. Сети. Потоки в сетях - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Дискретная математика. Сети. Потоки в сетях, слайд №1

Дискретная математика. Сети. Потоки в сетях, слайд №2

Дискретная математика. Сети. Потоки в сетях, слайд №3

Дискретная математика. Сети. Потоки в сетях, слайд №4

Дискретная математика. Сети. Потоки в сетях, слайд №5

Дискретная математика. Сети. Потоки в сетях, слайд №6

Дискретная математика. Сети. Потоки в сетях, слайд №7

Дискретная математика. Сети. Потоки в сетях, слайд №8

Дискретная математика. Сети. Потоки в сетях, слайд №9

Дискретная математика. Сети. Потоки в сетях, слайд №10

Дискретная математика. Сети. Потоки в сетях, слайд №11

Дискретная математика. Сети. Потоки в сетях, слайд №12

Дискретная математика. Сети. Потоки в сетях, слайд №13

Дискретная математика. Сети. Потоки в сетях, слайд №14

Дискретная математика. Сети. Потоки в сетях, слайд №15

Дискретная математика. Сети. Потоки в сетях, слайд №16

Дискретная математика. Сети. Потоки в сетях, слайд №17

Дискретная математика. Сети. Потоки в сетях, слайд №18

Дискретная математика. Сети. Потоки в сетях, слайд №19

Дискретная математика. Сети. Потоки в сетях, слайд №20

Дискретная математика. Сети. Потоки в сетях, слайд №21

Дискретная математика. Сети. Потоки в сетях, слайд №22

Дискретная математика. Сети. Потоки в сетях, слайд №23

Дискретная математика. Сети. Потоки в сетях, слайд №24

Дискретная математика. Сети. Потоки в сетях, слайд №25

Дискретная математика. Сети. Потоки в сетях, слайд №26

Дискретная математика. Сети. Потоки в сетях, слайд №27

Дискретная математика. Сети. Потоки в сетях, слайд №28

Дискретная математика. Сети. Потоки в сетях, слайд №29

Дискретная математика. Сети. Потоки в сетях, слайд №30

Дискретная математика. Сети. Потоки в сетях, слайд №31

Дискретная математика. Сети. Потоки в сетях, слайд №32

Дискретная математика. Сети. Потоки в сетях, слайд №33

Дискретная математика. Сети. Потоки в сетях, слайд №34

Дискретная математика. Сети. Потоки в сетях, слайд №35

Дискретная математика. Сети. Потоки в сетях, слайд №36

Дискретная математика. Сети. Потоки в сетях, слайд №37

Содержание ▲

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

Слайды и текст этой презентации

Слайд 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 на два подмножества Х и таких, что , а . Множество ребер, реализующих это разбиение назовем разрезом

Слайд 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), равная сумме пропускных способностей всех прямых ребер разреза.