4634
правки
Паросочетание: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Паросочетание''' (''[[Matching]]'') | '''Паросочетание''' (''[[Matching]]'') — | ||
произвольное подмножество попарно [[смежные ребра|несмежных ребер]] [[граф|графа]]. Паросочетание | произвольное подмножество попарно [[смежные ребра|несмежных ребер]] [[граф|графа]]. Паросочетание | ||
называется ''максимальным'', если оно не содержится в паросочетании с | называется ''максимальным'', если оно не содержится в паросочетании с | ||
| Строка 5: | Строка 5: | ||
среди всех паросочетаний графа. | среди всех паросочетаний графа. | ||
Другое название | Другое название — ''[[Независимое множество ребер графа|Независимое множество ребер]]''. | ||
[[Файл:Matching.png|200px]] | [[Файл:Matching.png|200px]] | ||
==См. также== | ==См. также== | ||
''[[Вершинно-реберное инцидентное паросочетание]], [[Правильное паросочетание]], [[Совершенное паросочетание]], [[Частичное паросочетание]], [[Взаимные паросочетания]].'' | * ''[[Вершинно-реберное инцидентное паросочетание]],'' | ||
* ''[[Правильное паросочетание]],'' | |||
* ''[[Совершенное паросочетание]],'' | |||
* ''[[Частичное паросочетание]],'' | |||
* ''[[Взаимные паросочетания]].'' | |||
==Литература== | ==Литература== | ||
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990. | |||