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

Задача 1

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

Задача 2

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

Задача 3

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

Задача 4

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

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

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

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

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

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

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

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

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