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

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

Содержание

Задан граф с начальной 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

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

СТРАТЕГИЧЕСКОЕ УПРАВЛЕНИЕ КРЕДИТНОЙ ОРГАНИЗАЦИЕЙ СТРАТЕГИЧЕСКОЕ УПРАВЛЕНИЕ КРЕДИТНОЙ ОРГАНИЗАЦИЕЙ 250
Безопасность жизнедеятельности Безопасность жизнедеятельности 418
PR-кампании этап планирования PR-кампании этап планирования 467
Основы комбустиологии Основы комбустиологии 165
Отчет об овечьей ферме Отчет об овечьей ферме 193
Выпускной 20 20 1 Выпускной 20 20 1 203
Тема урока : Ознакомление с оборудованием и технологией механизированной сварки Тема урока : Ознакомление с оборудованием и технологией механизированной сварки 251
Основные теории информации Основные теории информации 237
Страны Азии и Африки Китай Страны Азии и Африки Китай 342
Профессор, почетный гражданин г.Екатеринбурга, заслуженный деятель науки РФ Профессор, почетный гражданин г.Екатеринбурга, заслуженный деятель науки РФ 211
главных вопросов об обоях 15 главных вопросов об обоях 15 211
Формы ОЗЛП.ppt Формы ОЗЛП.ppt 242
Дополнительная образовательная программа Лего Лего и робототехника в Дополнительная образовательная программа Лего Лего и робототехника в 150
Уход за ушами больного Уход за ушами больного 340
Что такое пазлы ? Что такое пазлы ? 462
Теория управляемого хаоса Большакова Анна Бурова Теория управляемого хаоса Большакова Анна Бурова 275
Развитие креативного мышления через математические задания Все права защищены Развитие креативного мышления через математические задания Все права защищены 559
1. Обоснование необходимости изготовления изделия 1. Обоснование необходимости изготовления изделия 319
Женщины в войне 1812 года Женщины в войне 1812 года 323
Игра В мире животных Игра В мире животных 238

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

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

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

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

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

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

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