0. (с прошлого раза)
0.1 Ещё раз про Common Substring
0.2 Как увидеть в автомате дерево, два способа

1. Удлиняющие цепочки
1.1 Утверждение: есть цепочка iff паросочетание не максимальное
1.2 Но найти dfs-ом хрен получится

2. Чередующийся лес
2.1 Классификация вершин (even/S, odd/T, free, отдельно exposed)
2.2 Шаг наращивания, разные случаи
2.3 Отдельно обсудим случай цикла. Его тогда надо сжать
2.3.1 Дошли до новых вершин как до even. Надо в очередь
2.3.2 Если в будущем найдётся цепочка, то можно расжать
2.4 Теорема Эдмондса, формулировка (и в одну сторону уже доказали)
2.5 Время работы: оценка n^2 m, n^3 (пусть сжатие на k*n)
2.6 Теорема Эдмондса (в другую сторону)

3. Мысль про куна
3.1 Кун работает (второй раз из вершины нет смысла искать)
3.2 Лес заменяется на дерево, чуть-чуть меняются случаи
3.3 Теорема Эдмондса не работает (то есть да, но надо обобщать)

4. Габов
4.1 mate, p
4.2 учимся применять цепочку
4.3 соцветие (простой случай)
4.4 понятие base
4.5 сложный случай: base ведёт себя как СНМ
4.6 считаем LCA
4.7 топаем и направляем новые ссылочки p
4.8 Оценка n^3

------ перерыв -------

5. Формула Татта-Бержа
5.0 Формулировка и мотивация
5.1 Доказательство в случае сжатого графа
5.2 Обобщение
5.3 Инсайт про структурную декомпозицию Галаи-Эдмондса

6. Взвешенные паросочетания
6.1 Complementary slackness
6.2 Пишем линейную программу для парсоча и двойственную к ней
6.3 применение complementary slackness как критерия останова
6.4 инициализация алгоритма, меняем решение Primal и Duel одновременно
6.5 Конец совы (остаток алгоритма, насколько влезло)

---- reference ----

Про самого простого эдмондса и Татта-Бержа:
http://math.mit.edu/~goemans/18453S17/matching-nonbip-notes.pdf

Про max weighted matching:
"Efficient Algorithms for Finding Maximum Matching in Graphs, Zvi Galil"
http://www.cs.kent.edu/~dragan/GraphAn/p23-galil.pdf


Lawler E.L, Combinatorial Optimization: Networks and Matroids". click

http://inis.jinr.ru/sl/M_Mathematics/MA_Algebra/MAc_Combinatorics/Lawler%20E.L.%20Combinatorial%20optimization..%20networks%20and%20matroids%20(1976)(384s).pdf

В принципе про невзвешенный недвудольный матчинг там тоже написано.