Алгоритм вырезания соцветий — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Новая страница: «== Паросочетание в недвудольном графе== {{Определение |definition= Паросочетание в недвудольном …»)
(нет различий)

Версия 21:00, 23 декабря 2010

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

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


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


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


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