25
правок
Изменения
→Паросочетание в двудольном графе
{{Определение
|id=matching_def
|definition= '''Паросочетание''' (англ. ''mathing'') <tex>M</tex> в двудольном графе — произвольное множество ребер двудольного графа, такое что никакие два ребра не имеют общей вершины.}}
{{Определение
|definition= Вершины двудольного графа, инцидентные ребрам паросочетания <tex>M</tex>, называются '''покрытыми''', а неинцидентные — '''свободными'''.}}
{{Определение
|definition= Паросочетание <tex>M</tex> графа <tex>G</tex> называется '''полным''', если оно покрывает все вершины графа.}}
{{Определение
|definition= '''Чередующаяся цепь''' — путь в двудольном графе, для любых двух соседних ребер которого верно, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}}
|definition= '''Уменьшающая цепь''' — чередующаяся цепь, у которой оба конца покрыты.}}
{{Определение
|definition= '''Сбалансированная цепь''' — чередующаяся цепь, у которой один конец свободен, а другой покрыт.}}
== Теорема о максимальном паросочетании и дополняющих цепях ==
