52
правки
Изменения
м
Новая страница: «== Паросочетание в недвудольном графе== {{Определение |definition= Паросочетание в недвудольном …»
== Паросочетание в недвудольном графе==
{{Определение
|definition= Паросочетание в недвудольном графе - произвольное множество ребер недвудольного графа, такое, что никакие два ребра не имеют общей вершины. Обозначается паросочетание как <tex>M</tex>.}}
{{Определение
|definition= Вершины графа, инцидентные ребрам <tex>M</tex>, называются покрытыми, а неинцидентные - свободными.}}
{{Определение
|definition= Чередующаяся цепь - путь в графе, для любых двух соседних ребер которого выполняется, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}}
{{Определение
|definition= Дополняющая цепь - чередующаяся цепь, у которой оба конца свободны.}}
{{Определение
|definition= Паросочетание в недвудольном графе - произвольное множество ребер недвудольного графа, такое, что никакие два ребра не имеют общей вершины. Обозначается паросочетание как <tex>M</tex>.}}
{{Определение
|definition= Вершины графа, инцидентные ребрам <tex>M</tex>, называются покрытыми, а неинцидентные - свободными.}}
{{Определение
|definition= Чередующаяся цепь - путь в графе, для любых двух соседних ребер которого выполняется, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}}
{{Определение
|definition= Дополняющая цепь - чередующаяся цепь, у которой оба конца свободны.}}
