1. С помощью алгоритма Дейкстры найти путь минимального веса между вершинами s и t в нагруженном графе.

Решение

Прямого пути из вершины в вершину нет. Поэтому применим алгоритм Дейкстры.

Вершине присваиваем метку 0. Все остальные вершины имеют метки . Из вершины можно напрямую попасть в вершины и . Это кратчайшие расстояния, поэтому метки этих вершин заменяем соответствующими весами графа (зелёный цвет). Вершина считается посещённой, поэтому вычёркиваем её. Получим:

Ближайшая из непосещённых вершин – вершина . Из неё можно попасть в вершины и . Путь в вершину будет равен ( – путь из вершины в вершину , – путь из вершины в вершину ). , поэтому вес вершины будет равен . Путь в вершину будет равен , поэтому вес вершины будет равен . Путь в вершину будет равен ). , поэтому вес вершины станет равен . Вершина становится посещённой, поэтому вычёркиваем её. Получим:

Ближайшая из непосещённых вершин – вершина . Из неё можно попасть в вершины и . Путь в вершину будет равен . , поэтому вес вершины останется равным . Путь в вершину будет равен , поэтому вес вершины будет равен . Вершина становится посещённой, поэтому вычёркиваем её. Получим:

Ближайшая из непосещённых вершин – вершина . Из неё можно попасть в вершины и . Путь в вершину будет равен , поэтому вес вершины останется равным . Путь в вершину будет равен ). , поэтому вес вершины станет равен . Вершина становится посещённой, поэтому вычёркиваем её. Получим:

Ближайшая из непосещённых вершин – вершина . Из неё можно попасть в вершины и . Путь в вершину будет равен . , поэтому вес вершины станет равен . Путь в вершину будет равен , поэтому вес вершины будет равен . Путь в вершину будет равен ). поэтому вес вершины останется равным . Вершина становится посещённой, поэтому вычёркиваем её. Получим:

Ближайшая из непосещённых вершин – вершина . Из неё можно попасть в вершины и . Путь в вершину будет равен , поэтому вес вершины останется равным . Путь в вершину будет равен ). , поэтому вес вершины станет равен . Вершина становится посещённой, поэтому вычёркиваем её. Получим:

Ближайшая из непосещённых вершин – вершина . Из неё можно попасть в вершину . Путь в вершину будет равен . , поэтому вес вершины останется равным . Вершина становится посещённой, поэтому вычёркиваем её. Из вершины больше никуда попасть нельзя, поэтому её также вычёркиваем Получим:

Все вершины графа получились вычеркнутыми. Поэтому найдены минимальные пути из вершины во все остальные. Вес вершины равен , поэтому кратчайший путь из вершины в вершину равен .

Пути следующие:

2. Найти максимальный поток в заданной транспортной сети, используя алгоритм Форда-Фалкерсона. Проверить ответ по теореме Форда-Фалкерсона (найти минимальный разрез графа сети).

Решение

С помощью алгоритма Форда-Фалкерсона найдем наибольший поток из в .

Шаг 1. Выбираем произвольный поток, например, . Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть . Уменьшаем пропускные способности дуг этого потока на , насыщенную дугу вычеркиваем.

Шаг 2. Выбираем произвольный поток, например, . Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть .

Уменьшаем пропускные способности дуг этого потока на , насыщенную дугу вычеркиваем.

Шаг 3. Выбираем произвольный поток, например, . Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть .

Уменьшаем пропускные способности дуг этого потока на , насыщенную дугу вычеркиваем.

Шаг 4. Выбираем произвольный поток, например, . Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть .

Уменьшаем пропускные способности дуг этого потока на , насыщенную дугу вычеркиваем.

Шаг 5. Остался один возможный поток, например, . Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть . Уменьшаем пропускные способности дуг этого потока на , насыщенные дуги вычеркиваем.

Больше путей нет. Суммарный поток равен: .

Начинаем расстановку пометок. Начальная вершина (источник) имеет пометку 0. Из этой вершины нет ненасыщенных дуг, поэтому большепометки расставить нельзя.

Значит, максимальный поток найден, причем (непомеченные вершины) образуют разрез. Источником теперь является вершина . Величина разреза .