Изменения

Перейти к: навигация, поиск

Список заданий по АСД 2к 2015 осень

161 байт убрано, 21:58, 23 декабря 2015
Нет описания правки
# Глобальным разрезом называется разбиение множества вершин графа на два непустых непересекающихся множества. Сведите задачу о глобальном разрезе к поиску $O(V)$ максимальных потоков.
# Постройте граф, в котором алгоритм Форда-Фалкерсона (ФФ) находит $\Omega(C_{max})$ путей. Веса всех рёбер целочисленные.
# Постройте граф, в котором не будет найден максимальный поток. Веса рёбер вещественные.
# Постройте граф, в котором алгоритм Эдмондса-Карпа совершить $\Omega(V E)$ дополнений до пути.
# Доказать теорему о декомпозиционном барьере. (см. вики-конспекты)
Анонимный участник

Навигация