Алгоритм вырезания соцветий

Паросочетание в недвудольном графе

Определение:

Паросочетание в недвудольном графе - произвольное множество ребер недвудольного графа, такое, что никакие два ребра не имеют общей вершины. Обозначается паросочетание как [math]M[/math].

Определение:

Вершины графа, инцидентные ребрам [math]M[/math], называются покрытыми, а неинцидентные - свободными.

Определение:

Чередующаяся цепь - путь в графе, для любых двух соседних ребер которого выполняется, что одно из них принадлежит паросочетанию [math]M[/math], а другое нет.

Определение:

Дополняющая цепь - чередующаяся цепь, у которой оба конца свободны.