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

Задача 1

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

Задача 2

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

Задача 3

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

Задача 4

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

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

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

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

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

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

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

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

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