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

Содержание

1. Максимальный поток
2. Задан граф с начальной 1-ой и конечной 14-ой
3. Матричная форма графа
4. АлгоритмНайти кратчайший путь: 1, 6, 14Определяется минимальный
5. Поиск второго пути с начальной 1-ой и конечной 14-ой
6. Матричная форма графа
7. АлгоритмНайти кратчайший путь: 1, 6, 13, 14Определяется
8. Поиск третьего пути с начальной 1-ой и конечной 14-ой
9. АлгоритмНайти кратчайший путь: 1, 4, 12, 14Определяется
10. Поиск четвертого пути с начальной 1-ой и конечной 14-ой
11. АлгоритмНайти кратчайший путь: 1, 2, 7, 12,
12. Поиск пятого пути с начальной 1-ой и конечной 14-ой
13. АлгоритмНайти кратчайший путь: 1, 3, 6, 13,
14. Поиск шестого пути с начальной 1-ой и конечной 14-ой
15. АлгоритмНайти кратчайший путь: 1, 2, 7, 12,
16. Между 1 и 14 путей не существует – вычисление завершилось
17. 1-й путь) 1,6,14 – пропускная способность – 42-й
18. Скачать презентанцию

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

этого пути уменьшаются веса на 3
Суммарная пропускная способность по этому пути – 27+3=30
Далее нет путей между 1 и14

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

Слайд 16Между 1 и 14 путей не существует – вычисление завершилось

Слайд 171-й путь) 1,6,14 – пропускная способность – 4
2-й путь) 1, 6,

13, 14 – 4
3-й путь) 1, 4, 12, 14 – 8
4-й

путь) 1, 2, 7, 12, 14 – 6
5-й путь) 1, 3, 6, 13, 14 – 5
6-й путь) 1, 2, 7, 12, 15, 14 – 3
7-й путь) путей не существует.

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

1-й путь) 1,6,14 – пропускная способность – 42-й путь) 1, 6, 13, 14 – 4 3-й путь) 1, 4,

Скачать презентацию

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

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Слайд 16Между 1 и 14 путей не существует – вычисление завершилось

Слайд 171-й путь) 1,6,14 – пропускная способность – 4
2-й путь) 1, 6,

13, 14 – 4
3-й путь) 1, 4, 12, 14 – 8
4-й

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

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

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

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Слайд 16Между 1 и 14 путей не существует – вычисление завершилось

Слайд 171-й путь) 1,6,14 – пропускная способность – 42-й путь) 1, 6,

13, 14 – 4 3-й путь) 1, 4, 12, 14 – 84-й

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Слайд 171-й путь) 1,6,14 – пропускная способность – 4
2-й путь) 1, 6,

13, 14 – 4
3-й путь) 1, 4, 12, 14 – 8
4-й