Добавил:
north memphis Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
КиТГр Экзамен Билеты Расписанные 2025.pdf
Скачиваний:
36
Добавлен:
29.01.2025
Размер:
4 Мб
Скачать
☆

Продолжать алгоритм необходимо до тех пор, пока не останется ни единого пути из А в F. В конце необходимо посчитать сумму путей, что и будет являться ответом.

47. Как связаны задача о максимальном потоке и минимальный разрез? Проиллюстрируйте примером.

Лемма (максимальный поток и минимальный разрез)

Если , то поток – максимален, а разрез минимален.

Где – поток в разрезе; – пропускная способность разреза

Среди всех разрезов сети разрез с минимальной пропускной способностью определяет

максимальный поток в сети:

48. Клика – определение. Приведите пример графа с данной максимальной кликой.

Определение (клика)

Это такое подмножество вершин, в котором все вершины соединены между собой ребром.