25
правок
Изменения
→Паросочетание в двудольном графе
|definition= Вершины двудольного графа, инцидентные ребрам паросочетания <tex>M</tex>, называются '''покрытыми''' (англ. ''matched''), а неинцидентные — '''свободными''' (англ. ''unmatched'').}}
{{Определение
|definition= Число вершин в наименьшем покрытии графа <tex>G</tex> называется '''числом покрытия (или числом вершинного покрытия)''' (англ. ''edge covering number'') графа <tex>G</tex> и обозначается через <tex>\rho(G)</tex>.}}
{{Определение
|definition= Число ребер в наибольшем паросочетании графа <tex>G</tex> называется '''числом паросочетания''' (англ. ''matching number'').}}
{{Определение
|definition= '''Максимальное паросочетание''' (англ. ''maximal matching'') — это такое паросочетание <tex>M</tex> в графе <tex>G</tex>, которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем ребрам паросочетания.}}
Другими словами, паросочетание <tex>M</tex> графа <tex>G</tex> является максимальным, если любое ребро в <tex>G</tex> имеет непустое пересечение по крайней мере с одним ребром из <tex>M</tex>.
|definition= Паросочетание <tex>M</tex> графа <tex>G</tex> называется '''совершенным (или полным)''' (англ.''perfect matching''), если оно покрывает все вершины графа.}}
{{Определение
