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