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

Категория: Математика
Нажмите для полного просмотра!
Дискретная математика. Сети. Потоки в сетях, слайд №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) Истоком и стоком (входным и выходным полюсом) называются некоторые отмеченные вершины.
Описание слайда:
Сети Сетью называется частично ориентированный граф G(V, E) Истоком и стоком (входным и выходным полюсом) называются некоторые отмеченные вершины.

Слайд 9


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

Слайд 10


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

Слайд 11


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

Слайд 12


Сети Разобьем множество вершин V на два подмножества Х и таких, что , а . Множество ребер, реализующих это разбиение назовем разрезом
Описание слайда:
Сети Разобьем множество вершин V на два подмножества Х и таких, что , а . Множество ребер, реализующих это разбиение назовем разрезом

Слайд 13


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

Слайд 14


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

Слайд 15


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

Слайд 16


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

Слайд 17


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

Слайд 18


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

Слайд 19


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

Слайд 20


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

Слайд 21


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

Слайд 22


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

Слайд 23


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

Слайд 24


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

Слайд 25


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

Слайд 26


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

Слайд 27


Поток в сети Замечание 2:
Описание слайда:
Поток в сети Замечание 2:

Слайд 28


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

Слайд 29


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

Слайд 30


Поток в сети Замечание 3: Величина потока в сети есть величина переменная, зависящая от значений функции f(e).
Описание слайда:
Поток в сети Замечание 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.
Описание слайда:
с(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


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

Слайд 33


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

Слайд 34


Поток в сети Каждому ребру разреза R ставится в соответствие пропускная способность разреза с(R), равная сумме пропускных способностей всех прямых ребер разреза.
Описание слайда:
Поток в сети Каждому ребру разреза 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
Описание слайда:
с(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
Описание слайда:
C=c(b)+c(h)+c(x)+c(y)=3+1+3+2=9

Слайд 37


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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию