=^_^= Кружок обучения мастерству программирования при СПбГУ

Лекции группы A0 - Лекция 09 - Рандом + Геометрия (Сергей Копелиович)

Note: Звездочкой отмечены темы, на которые на лекции времени не хватило.

Краткий план лекции "Рандом + Геометрия"

  1. Поиск паросочетания в двудольном графе (Кун, min cover)
  2. Матроиды
  3. Поиск паросочетания в произвольном графе (Эдмандс)
  4. Задачи про лекс.мин. паросочетание, про регулярные графы

Полный план лекции

  1. Основы
    1. Паросочетание. Лемма о дополняющем пути. (Для произвольного графа)
    2. |C| >= |M|, C - вершинное покрытие.
    3. M --O(E)--> C => min|C| = max|M| : Th. Кёнига-Эгервари
    4. Получили алгоритм построения maxM, minC, maxN (N - независимое множество), задача о max клике в двудольном графе.
    5. Лемме Холла (о девушках)
  2. Фишки
    1. Матроиды = Кун + Мин. по весу в одной доле
    2. Определения. Аксиомы, база.
    3. Алгоритм Радо-Эдмондса
    4. Мин. по весу в обеих долях за O(VE) (нашли оптимум для одной доли, для второй, спарили, ответ = сумме ответов)
    5. Мин. лекс. парсоч за O(VE) (нашли какое-то, далее за O(E) посчитали мн-во допустимых ребер)
  3. Недвудольный случай
    1. * Th. Татта-Берджа про 2|M| = min по U (|V| - ood(G/U) + |U|)
    2. * Док-во алгоритма Эдмондса через Татта-Берджа
    3. Алгоритм Эдмондса.
    4. Док-во без Татта-Берджа, на халяву.
    5. Удобности реализации = Кун (лес := дерево) + dfs
    6. Random-Algo (парсоч в 2-дульном --> пересекающиеся чередующиеся цепочки)
  4. Алгоритм поиска паросочетания на двудольных регулярных графах.
    1. Всегда сущ Perfect Matching (следует из леммы Холла)
    2. d = 2^k => алгоритм за O(E)
    3. Произвольное d, алгоритм за O(ED) (функция потенциалов, улучшение по циклу)
    4. Произвольное d, алгоритм за O(ElogD) (редукция графа за O(E) до [V, VlogD])