Алгоритмы поиска паросочетаний и покрытий. Лекция 12

1.

Лекция 12. Алгоритмы поиска паросочетаний и покрытий
1.
Алгоритм решения задачи о паросочетании максимальной мощности
2.
Алгоритм построения чередующегося дерева
3.
Алгоритм построения паросочетания максимальной мощности
4.
Алгоритм выбора паросочетания с максимальным весом (Эдмондса и Джонсона)
Паросочетанием графа называется некоторое множество его дуг, такое, что каждая вершина графа инцидентна
не более чем одной дуге этого множества.
Покрытием графа называется некоторое множество дуг в графе, такое, что каждая его вершина инцидентна по
крайней мере одной дуге этого множества.
На рис. каждое из множеств дуг {