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

Понедельник, 06 апреля 2015

Таймс, ауд. 404

Описание

Кодим паросочетание и контролирующее множество
Stable Marriage
Рандомизированный алгоритм для паросочетания в произвольном графе
Задачи
- Максимальная двудольная клика (matching)
- Покрыть клетчатое поле с дырками доминошками (matching)
- Нарисовать чёрно-белый шедевр минимальным числом мазков (cover)
- Удаление орграфа, за ход можно удалить или входящие в v, или исходящие из v рёбра (cover)
- Максимальное мультипаросочетание (выбрать рёбра так, чтобы у любой вершины степень \(\le 2\)).
- Покрытие графа минимальным числом путей (раздвоили вершины, matching)
- Есть самолёты (время вылета, вместимость). Есть пассажиры (отрезок допустимых времён вылета). Сделать так, чтобы все пассажиры улетели.
- Есть прямые. Выбрать максимальное подмножество так, чтобы не было параллельных и имеющих одинаковый y пересечения c x=0.