Контрольная работа: Решение практических заданий по дискретной математике

Шаг 4. Конец первого этапа.

Следовательно, длина кратчайшего пути равна .

Этап 2. Построение кратчайшего пути.

1-я итерация.

Шаг 5. Составим множество вершин, непосредственно предшествующих с постоянными метками : Проверим равенство

для этих вершин:

т.е.

т.е.

Включаем дугу в кратчайший путь,

Шаг 6. Возвращаемся на пятый шаг.

2-я итерация.

Шаг 5.

Включаем дугу в кратчайший путь, .

Шаг 6. . Завершение второго этапа.

Следовательно, кратчайший путь построен. Его образует последовательность дуг: .

Окончательно, кратчайший путь от вершины до вершины v₆ построен. Его длина (вес) равна . Сам путь образует последовательность дуг:

б) Определим максимальный поток через сеть G. Для этого используем алгоритм Форда-Фалкерсона.

Выбираем произвольно путь из вершины v₁ в вершину v₆ . Пусть это будет путь . Минимальную пропускную способность на этом пути, равную 10, имеет дуга , т.е. Увеличим на этом пути поток до 10 единиц. Дуга становится насыщенной. Дуга имеет на данный момент пропускную способность, равную 10.

Путь Следовательно, поток на этом пути можно увеличить на 9 единиц. Дуги становятся насыщенными.

Других маршрутов нет (другие маршруты проходят через насыщенные дуги). Поток максимален. Делаем разрез вокруг вершины v₁ по насыщенным дугам