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

Понедельник, 06 апреля 2015
Таймс, ауд. 404

Описание

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