Аноним

Паросочетание: различия между версиями

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Паросочетание''' (''[[Matching]]'') -
'''Паросочетание''' (''[[Matching]]'')
произвольное подмножество попарно [[смежные ребра|несмежных ребер]] [[граф|графа]]. Паросочетание
произвольное подмножество попарно [[смежные ребра|несмежных ребер]] [[граф|графа]]. Паросочетание
называется ''максимальным'', если оно не содержится в паросочетании с
называется ''максимальным'', если оно не содержится в паросочетании с
Строка 5: Строка 5:
среди всех паросочетаний графа.
среди всех паросочетаний графа.


Другое название --- ''[[Независимое множество ребер графа|Независимое множество ребер]]''.
Другое название ''[[Независимое множество ребер графа|Независимое множество ребер]]''.


[[Файл:Matching.png|500px]]
[[Файл:Matching.png|200px]]


==См. также==
==См. также==
''[[Вершинно-реберное инцидентное паросочетание]], [[Правильное паросочетание]], [[Совершенное паросочетание]], [[Частичное паросочетание]], [[Взаимные паросочетания]].''
* ''[[Вершинно-реберное инцидентное паросочетание]],''
* ''[[Правильное паросочетание]],''
* ''[[Совершенное паросочетание]],''
* ''[[Частичное паросочетание]],''
* ''[[Взаимные паросочетания]].''
==Литература==
==Литература==
[Лекции]
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.