1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Определение
|id=matching_def
|definition= '''Паросочетание''' (англ. ''matсhing'') <tex>M</tex> в двудольном графе — произвольное множество рёбер двудольного графатакое, такое что никакие два ребра не имеют общей вершины.}}
{{Определение
|definition= Вершины двудольного графа, инцидентные рёбрам паросочетания <tex>M</tex>, называются '''покрытыми''' (англ. ''matched''), а неинцидентные — '''свободными''' (англ. ''unmatched'').}}
{{Определение
|id = maximal_matching
|definition= '''Максимальное паросочетание(по включению)''' (англ. ''maximal matching'') — это такое паросочетание <tex>M</tex> в графе <tex>G</tex>, которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем рёбрам паросочетания.}}
Другими словами, паросочетание <tex>M</tex> графа <tex>G</tex> является максимальным, если любое ребро в <tex>G</tex> имеет непустое пересечение по крайней мере с одним ребром из <tex>M</tex>.
{{Определение
|id = maximal_matching_size
|definition= '''Максимальное паросочетание (по мощности)''' (англ. ''maximum cardinality matching'') — это паросочетание <tex>M</tex> в графе <tex>G</tex> максимальное по мощности.}}
{{Определение
