Презентация на тему: Потоки в сетях

Потоки в сетях.
Варианты задач:
Потоки в сетях.
Теорема Форда-Фацкерсона :
Потоки в сетях.
Потоки в сетях.
Потоки в сетях.
Потоки в сетях.
Потоки в сетях.
Потоки в сетях.
Потоки в сетях.
Потоки в сетях.
Потоки в сетях.
Потоки в сетях.
Потоки в сетях.
Потоки в сетях.
Потоки в сетях.
Потоки в сетях.
Потоки в сетях.
Потоки в сетях.
Потоки в сетях.
Потоки в сетях.
Потоки в сетях.
Потоки в сетях.
Потоки в сетях.
1/25
Средняя оценка: 4.6/5 (всего оценок: 33)
Код скопирован в буфер обмена
Скачать (903 Кб)
1

Первый слайд презентации: Потоки в сетях

Изображение слайда
2

Слайд 2: Варианты задач:

Изображение слайда
3

Слайд 3

Задачи о MAX потоке Рассмотрим граф G =( X, A ) с пропускными способностями дуг g, i, j, источником S и стоком t. S, t X.Множество чисел,определенных на дугах (, называется потоками в дугах, если выполняется условие максимальной.

Изображение слайда
4

Слайд 4: Теорема Форда-Фацкерсона :

(о максимальном потоке и максимальном разрезе). ), Доказательство.

Изображение слайда
5

Слайд 5

Изображение слайда
6

Слайд 6

Изображение слайда
7

Слайд 7

Алгоритм начинает работу с произвольного допустимого потока (можно взять и 0-й поток), затем стремится увеличить величину потока с помощью систематического поиска всех возможных аугментальных целей потока от s к t. Поиск аугментальной цели осуществляется с помощью расставленных пометок в вершинах графа. Поэтому указывают, вдоль каких дуг может быть увеличен поток и на сколько. Как только найдена одна из таких цепей, поток вдоль нее увеличивают до max значения, а пометки в вершинах стираются и вновь полученный поток используется в качестве исходного при новой расстановке пометок. Алгоритм работу заканчивает и дает max поток, если нельзя найти ни 1 аугментальную цель.

Изображение слайда
8

Слайд 8

Алгоритм расстановки пометок для задачи о max (от s и t ) потоке. А. Расстановка пометок.

Изображение слайда
9

Слайд 9

Изображение слайда
10

Слайд 10

Пример задачи о max потоке. Пусть дан граф G (направленный, без циклов, нумерация вершины от меньшего номера к большему).

Изображение слайда
11

Слайд 11

Изображение слайда
12

Слайд 12

Изображение слайда
13

Слайд 13

Итерация 3. Пометка для :

Изображение слайда
14

Слайд 14

Пометка для Пометка для Пометка для

Изображение слайда
15

Слайд 15

Пометка для Пометка для Пометка для не получена и не может быть получена. Новые потоки ;

Изображение слайда
16

Слайд 16

На этой итерации насыщенных дуг не появилось. Итерация 5. Пометка для Пометка для Пометка для Пометка для Пометка для Пометка для и не отмечены.

Изображение слайда
17

Слайд 17

Пометка для Пометка для Новые потоки; Появилась насыщенная дуга Итерация 6. Пометка для Пометка для Пометка для не может быть помечена.

Изображение слайда
18

Слайд 18

не может быть помечена. - нельзя пометить. Полученный поток – max величин 29,а min разрез имеет вид; Величина min разреза =10+4+8+7=29= величине max потока. Вершина 9 не помечена и никаких других пометок нельзя расставить. Min разрез отделяет множество помеченных вершин от непомеченных Пример.

Изображение слайда
19

Слайд 19

- источник; - сток; Пропускные способности дуг указаны на рисунке. Найти max поток от к Начальный поток – с нулевыми значениями на всех дугах. Шаг 1. Припишем пометку Шаг 2. (1) множество вершин есть 2.Множество вершин не помечена. Итак, помечена и просмотрена, и помечены и не просмотрены, а все остальные вершины не помечены.

Изображение слайда
20

Слайд 20

Повторим шаг 2 и первой просмотрим вершину Теперь вершины и помечены и просмотрены, а и помечены, но не просмотрены. Взяв для просмотра и повторяя шаг 2, прейдем к следующим пометкам; пометкой будет для пометкой будет Беря для просмотра найдем, что никаких пометок расставить нельзя Продолжим просмотр с получим следующие потоки:

Изображение слайда
21

Слайд 21

Переходим к шагам 4 и 5, получим: Получим следующие пометки вершин до их стирания на шаге 6: - насыщенная дуга. Стираем пометки и возвращаемся к шагу 1 для второго прохода,получим:

Изображение слайда
22

Слайд 22

помечена и просмотрена. решена и просмотрена. также помечена и просмотрена.

Изображение слайда
23

Слайд 23

Все остальные значения потока не изменились. Новый вид потока и пометки вершин до стирания имеют вид:

Изображение слайда
24

Слайд 24

Изображение слайда
25

Последний слайд презентации: Потоки в сетях

Изображение слайда