ЛКШ-2024, параллель 6. Лекция 7: Паросочетания.

Двудольные графы. Паросочетания. Максимальное и наибольшее паросочетание. Удлиняющий путь. Алгоритм Куна. Реализация и оптимизация алгоритма Куна.
Теорема Холла (теорема о женихах и невестах).
Минимальное вершинное покрытие. Теорема Кёнига. Построение минимального вершинного покрытия на основе наибольшего паросочетания. Максимальное независимое множество.
Разбиение ориентированного ациклического графа на минимальное число путей.

[Lexonixeo]

У вас название лекции неверное: в лекции говорится про двудольные графы, а в названии вычислительная геометрия