Условие:
Сеть задана матрицей весов, которая получена из матрицы смежности графа заменой единиц на веса соответствующих дуг и нулей на прочерки:
Вершина с номером 1 является источником, вершина с номером 6 - стоком. В сети задан разрез
Решение:
Шаг 1. Интерпретация разреза.
• В вершины сети заданы номера 1...6.
• Источник – вершина 1, сток – вершина 6.
• Разрез задан: Vₛ = {1, 2, 3} и Vₜ = {остальные} = {4, 5, 6}.
Шаг 2. Анализ матрицы весов.
Матрица дана в виде:
1 2 3 4 5 6
1: - 4 9 8 3 -
2: - - - - 7 -
3: - 4 - - 3 6
4: - - 3 - - 6
5: - - - - - 9
6: - - - - - -
В этой матрице прочерки...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи