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

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


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


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


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

Текущая версия от 11:41, 6 июня 2011

Паросочетание (Matching) — произвольное подмножество попарно несмежных ребер графа. Паросочетание называется максимальным, если оно не содержится в паросочетании с большим числом ребер, и наибольшим, если число ребер в нем наибольшее среди всех паросочетаний графа.

Другое название — Независимое множество ребер.

Matching.png

См. также

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.