City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Семинар 7. Потоки в транспортных сетях
Advanced chapters of algorithms, part 2

What: Seminar
When: Saturday, 26 March 2022, 00:00–01:30
Where: Онлайн, занятие в zoom

Description

Разбор теоретического задания 5

Задача 1

Арина Уланова, Михаил Иванов

Задача 2

Арина Уланова

Задача 3

Улитка Говорит

Задача 4

Ольга Самойлова

Задачи с семинара 7

  1. Докажите, что если в \(G\) существует поток величины \(x\), то для любого вещественного \(y\in[0;x]\) существует поток величины \(y\).

  2. Докажите, что если в сети \(e\) ребер, и пропускная способность каждого не больше \(C\), то величина максимального потока не превосходит \(Ce\).

  3. Докажите, что любой поток можно представить как сумму путей из \(s\) в \(t\) и циклов.

  4. Докажите, что если все пропускные способности целочисленные, то существует максимальный поток, в котором поток по каждому ребру тоже целочисленный.

  5. Решите задачу о максимальном паросочетании в двудольном графе с помощью максимального потока. Как связаны разрез и минимальное вершинное покрытие?

  6. а) Приведите пример сети с вещественными пропускными способностями, в которой алгоритм Форда-Фалкерсона может никогда не завершиться.

    б) Приведите пример сети с вещественными пропускными способностями, в которой поток, который находит алгоритм Форда-Фалкерсона, не стремится к оптимальному.