Паросочетание: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Паросочетание''' (''Matching'') - произвольное подмножество попарно несмежных р...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Паросочетание''' (''Matching'') - | '''Паросочетание''' (''[[Matching]]'') - | ||
произвольное подмножество попарно несмежных ребер графа. Паросочетание | произвольное подмножество попарно [[смежные ребра|несмежных ребер]] [[граф|графа]]. Паросочетание | ||
называется ''максимальным'', если оно не содержится в паросочетании с | называется ''максимальным'', если оно не содержится в паросочетании с | ||
большим числом ребер, и наибольшим, если число ребер в нем наибольшее | большим числом [[ребро|ребер]], и наибольшим, если число ребер в нем наибольшее | ||
среди всех паросочетаний графа. | среди всех паросочетаний графа. | ||
Другое название --- ''Независимое множество ребер''. | Другое название --- ''[[Независимое множество ребер графа|Независимое множество ребер]]''. | ||
См. также ''Вершинно-реберное инцидентное паросочетание, Правильное паросочетание, Совершенное паросочетание, Частичное паросочетание, Взаимные паросочетания.'' | ==См. также== | ||
''[[Вершинно-реберное инцидентное паросочетание]], [[Правильное паросочетание]], [[Совершенное паросочетание]], [[Частичное паросочетание]], [[Взаимные паросочетания]].'' | |||
==Литература== | ==Литература== | ||
[Лекции] | [Лекции] | ||
Версия от 18:24, 15 декабря 2009
Паросочетание (Matching) - произвольное подмножество попарно несмежных ребер графа. Паросочетание называется максимальным, если оно не содержится в паросочетании с большим числом ребер, и наибольшим, если число ребер в нем наибольшее среди всех паросочетаний графа.
Другое название --- Независимое множество ребер.
См. также
Вершинно-реберное инцидентное паросочетание, Правильное паросочетание, Совершенное паросочетание, Частичное паросочетание, Взаимные паросочетания.
Литература
[Лекции]