Паросочетания

1. Кодим
1. Паросочетание [code]
2. Контролирующее множество [code]
2. Теория
1. Сведения: min cover ↔ max independent set ↔ max clique
2. Stable Marriage
3. Рандомизированный алгоритм для паросочетания в произвольном графе
3. Задачи
1. Максимальная двудольная клика (matching)
2. Покрыть клетчатое поле с дырками доминошками (matching)
3. Нарисовать чёрно-белый шедевр минимальным числом мазков (cover)
4. Удаление орграфа, за ход можно удалить или входящие в v, или исходящие из v рёбра (cover)
5. Максимальное мультипаросочетание (выбрать рёбра так, чтобы у любой вершины степень ≤ 2).
6. Покрытие графа минимальным числом путей (раздвоили вершины, matching)
7. Есть самолёты (время вылета, вместимость). Есть пассажиры (отрезок допустимых времён вылета). Сделать так, чтобы все пассажиры улетели.
8. Есть прямые. Выбрать максимальное подмножество так, чтобы не было параллельных и имеющих одинаковый y пересечения c x=0.