Изменения

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

180 байт убрано, 20:50, 23 декабря 2015

Нет описания правки

# Постройте граф, в котором алгоритм Форда-Фалкерсона (ФФ) находит $\Omega(C_{max})$ путей. Веса всех рёбер целочисленные.

# Постройте граф, в котором не будет найден максимальный поток. Веса рёбер вещественные.

~~# Если выбирать путь с максимальным $C_{min}$, то время работы ФФ будет $O(polynom(V, E) \log(C_{max}))$. Докажите это.~~

# Постройте граф, в котором алгоритм Эдмондса-Карпа совершить $\Omega(V E)$ дополнений до пути.

# Доказать теорему о декомпозиционном барьере. (см. вики-конспекты)

Анонимный участник