Задачи по потокам (14 апреля 2016)

1. Задачи на паросочетания
1. Покрытие вершин орграфа простыми непересекающимися циклами (раздвоили вершины, matching)
2. Покрытие вершин ацикличного орграфа минимальным числом путей (раздвоили вершины, matching)
2. Теория в форме задач
1. k путей (дан орграф, найти k непересекающихся по рёбрам путей из s в t).
2. Вершинный поток в орграфе (найти k непересекающихся по вершинам путей)
3. Неориентированный граф: два способа создавать ребро.
4. Поток в графе с несколькими истоками и стоками
5. Избытки и недостатки (есть несколько точек производств, точек потребления, настроить транспортную сеть между ними)
6. [L,R]-циркуляция и [L,R]-поток
3. Задачи про поток
1. Поиск паросочетания в двудольном графе через поток
2. Поиск мультипаросочетания (у каждой вершины степень не более k)
3. Даны матрицы (девочка, собачка) (девочка, мальчик), найти трисочетание (девочке нравится и мальчик и собачка)
4. [не успеем] Турнирная таблица (дана недоигранная таблица игр "каждый с каждым" и итоговые результаты, восстановить счёт).
5. [не успеем] Восстановление матрицы (даны суммы в строках, столбцах, некоторые клетки)
6. [не успеем] Поиск контролирующего множества min веса, независимого множества max веса
4. Кодим
1. Поток [code]
2. Чуть более быстрый поток [code]
3. [не успеем] Декомпозиция потока [code]
5. [не успеем] Минимальный разрез
1. [не успеем] Удалить в связном неорграфе минимальное число рёбер, чтобы он потерял связность (global cut)
2. [не успеем] У каждого ребра в неорграфе есть стоимость. Удалить рёбра минимальной суммарной стоимости, чтобы s и t оказались в разных компонентах связности.
3. [не успеем] Проверить, единственный ли минимальный разрез?
4. [не успеем] Минимальный и максимальный по количество вершин в половине с истоком