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