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

Задача 1

а) Михаил Слабодкин

б) Михаил Слабодкин, Ольга Самойлова

Задача 2

Лиана Хазалия, Улитка Говорит

Задача 3

Лиана Хазалия

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

1. Постройте серию транспортных сетей на $n$ вершинах и $\mathcal O\left(n^2\right)$ рёбрах, на которой алгоритм Диница работает $\Omega\left(n^4\right)$ времени. [сформулировали, не разбирали]

2. В целочисленной транспортной сети дан целочисленный максимальный поток. Пропускную способность одной из стрелок уменьшили на единицу. Найдите максимальный поток в полученной сети быстрее, чем находить его заново.

3. Задача о циркуляции. Дан граф, на каждом ребре выбран диапазон количества жижи, которое может по нему течь, для удобства будем считать, что кроме этого на каждом ребре задано некоторое эталонное направление. Вы должны для каждого ребра $e$ выбрать из его диапазона $\left[\ell_e,r_e\right]$ количество жижи $f_e$, которое будет по нему течь. Если $f_e>0$, то будет течь $f_e$ жижи вдоль эталонного направления; если $f_e=0$, то не будет течь ни в какую сторону, а если $f_e<0$, то будет течь $-f_e$ жижи против эталонного направления.

   Кроме того, выбирать числа надо так, чтобы в каждую вершину втекало и вытекало поровну жижи — в этом условие отличается от условия на поток в транспортной сети только отсутствием истока и стока. Треубется проверить, существует ли хотя бы одна циркуляция в такой сети.

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

   б) Определите, существует ли циркуляция в сети, за время поиска потока в сети с таким же числом вершин и рёбер, как в заданном графе.

4. Дан граф с выбранными вершинами $a$, $b$, $c$. Проверьте за полиномиальное время, что есть путь с концами в $a$ и $b$, проходящий через $c$, являющийся:

   а) рёберно простым;

   б) простым (то есть вершинно простым).