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