Презентация Дискретная математика. Сети. Потоки в сетях онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Дискретная математика. Сети. Потоки в сетях абсолютно бесплатно. Урок-презентация на эту тему содержит всего 37 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:37 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:1.79 MB
- Просмотров:135
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№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), равная сумме пропускных способностей всех прямых ребер разреза.
№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 равна минимальной пропускной способности среди всех ее разрезов.
Скачать все slide презентации Дискретная математика. Сети. Потоки в сетях одним архивом:
