Разделы презентаций

Максимальный поток

Содержание

Задан граф с начальной 1-ой и конечной 14-ой

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

Слайд 1Максимальный поток
Старший преподаватель
кафедры теоретической кибернетики
Хадиев Р.М.
КАЗАНСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

Максимальный потокСтарший преподавателькафедры теоретической кибернетикиХадиев Р.М.КАЗАНСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

Слайд 2Задан граф с начальной 1-ой и конечной 14-ой

Задан граф с начальной 1-ой и конечной 14-ой

Слайд 3Матричная форма графа

Матричная форма графа

Слайд 4Алгоритм
Найти кратчайший путь: 1, 6, 14
Определяется минимальный вес ребра на

этом пути – 4
На всех ребрах этого пути уменьшаются

веса на 4
Пропускная способность по этому пути – 4
Далее повторяем 1-4 шаги алгоритма, суммируя пропускные способности найденных путей, пока будут пути между 1 и14

АлгоритмНайти кратчайший путь: 1, 6, 14Определяется минимальный вес ребра на этом пути – 4 На всех ребрах

Слайд 5Поиск второго пути с начальной 1-ой и конечной 14-ой

Поиск второго пути с начальной 1-ой и конечной 14-ой

Слайд 6Алгоритм
Найти кратчайший путь: 1, 6, 13, 14
Определяется минимальный вес ребра

на этом пути – 4
На всех ребрах этого пути

уменьшаются веса на 4
Суммарная пропускная способность по этому пути – 4+4=8
Далее повторяем 1-4 шаги алгоритма, суммируя пропускные способности найденных путей, пока будут пути между 1 и14
АлгоритмНайти кратчайший путь: 1, 6, 13, 14Определяется минимальный вес ребра на этом пути – 4 На всех

Слайд 7Поиск третьего пути с начальной 1-ой и конечной 14-ой

Поиск третьего пути с начальной 1-ой и конечной 14-ой

Слайд 8Алгоритм
Найти кратчайший путь: 1, 4, 12, 14
Определяется минимальный вес ребра

на этом пути – 8
На всех ребрах этого пути

уменьшаются веса на 8
Суммарная пропускная способность по этому пути – 8+8=16
Далее повторяем 1-4 шаги алгоритма, суммируя пропускные способности найденных путей, пока будут пути между 1 и14
АлгоритмНайти кратчайший путь: 1, 4, 12, 14Определяется минимальный вес ребра на этом пути – 8 На всех

Слайд 9Поиск четвертого пути с начальной 1-ой и конечной 14-ой

Поиск четвертого пути с начальной 1-ой и конечной 14-ой

Слайд 10Алгоритм
Найти кратчайший путь: 1, 2, 7, 12, 14
Определяется минимальный вес

ребра на этом пути – 6
На всех ребрах этого

пути уменьшаются веса на 6
Суммарная пропускная способность по этому пути – 16+6=22
Далее повторяем 1-4 шаги алгоритма, суммируя пропускные способности найденных путей, пока будут пути между 1 и14
АлгоритмНайти кратчайший путь: 1, 2, 7, 12, 14Определяется минимальный вес ребра на этом пути – 6 На

Слайд 11Поиск пятого пути с начальной 1-ой и конечной 14-ой

Поиск пятого пути с начальной 1-ой и конечной 14-ой

Слайд 12Алгоритм
Найти кратчайший путь: 1, 3, 6, 13, 14
Определяется минимальный вес

ребра на этом пути – 5
На всех ребрах этого

пути уменьшаются веса на 5
Суммарная пропускная способность по этому пути – 22+5=27
Далее повторяем 1-4 шаги алгоритма, суммируя пропускные способности найденных путей, пока будут пути между 1 и14
АлгоритмНайти кратчайший путь: 1, 3, 6, 13, 14Определяется минимальный вес ребра на этом пути – 5 На

Слайд 13Поиск шестого пути с начальной 1-ой и конечной 14-ой

Поиск шестого пути с начальной 1-ой и конечной 14-ой

Слайд 14Алгоритм
Найти кратчайший путь: 1, 2, 7, 12, 15, 14
Определяется минимальный

вес ребра на этом пути – 3
На всех ребрах

этого пути уменьшаются веса на 3
Суммарная пропускная способность по этому пути – 27+3=30
Далее нет путей между 1 и14
АлгоритмНайти кратчайший путь: 1, 2, 7, 12, 15, 14Определяется минимальный вес ребра на этом пути – 3

Слайд 15Мощность максимального потока – 30

Мощность максимального потока – 30

Похожие презентации

________1.ppt ________1.ppt 233
Коллективное поведение Коллективное поведение 241
САМОМЕНЕДЖМЕНТ Разработал к.т.н., доцент Скачкова И.А САМОМЕНЕДЖМЕНТ Разработал к.т.н., доцент Скачкова И.А 301
СПОСОБЫ ЛИЧНОГО ВЫЖИВАНИЯ Тема лекции: Действия членов экипажа при оставлении СПОСОБЫ ЛИЧНОГО ВЫЖИВАНИЯ Тема лекции: Действия членов экипажа при оставлении 274
1.11. Потери и коэффициент полезного действия 1.11. Потери и коэффициент полезного действия 687
Ассессмент -центр Ассессмент -центр 163
Общественная палата Республики Татарстан Общественная палата Республики Татарстан 276
СОЦИАЛЬНАЯ РАБОТА С СЕМЬЕЙ СОЦИАЛЬНАЯ РАБОТА С СЕМЬЕЙ 243
О Приемной кампании в 1 классы 2019-2020 учебного года О Приемной кампании в 1 классы 2019-2020 учебного года 252
Социальная Работа Социальная Работа 486
Фотобиология Фотобиология 530
Семейства цветковых растений ГБОУ школа №7 Красносельского района Семейства цветковых растений ГБОУ школа №7 Красносельского района 232
Библиотека-центр Библиотека-центр 224
ФК РУСИЧИ-2008 СШОР Русичи ( г.Орёл ) Предложение для спонсоров и ФК РУСИЧИ-2008 СШОР Русичи ( г.Орёл ) Предложение для спонсоров и 240
Биомасса энергиясын пайдалануды дамыту. Стратегиялық және заңнамалық Биомасса энергиясын пайдалануды дамыту. Стратегиялық және заңнамалық 254
Участие студентов ИФО в олимпиадах Участие студентов ИФО в олимпиадах 207
Спонтанные кровоизлияния у детей Спонтанные кровоизлияния у детей 262
Тяжелые металлы Тяжелые металлы 271
Власть: происхождение и виды Власть: происхождение и виды 369
Химия и география Химия и география 247

Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.

Для правообладателей

Яндекс.Метрика