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

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


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


См. также ''Вершинно-реберное инцидентное паросочетание, Правильное паросочетание, Совершенное паросочетание, Частичное паросочетание, Взаимные паросочетания.''
==См. также==
''[[Вершинно-реберное инцидентное паросочетание]], [[Правильное паросочетание]], [[Совершенное паросочетание]], [[Частичное паросочетание]], [[Взаимные паросочетания]].''
==Литература==
==Литература==
[Лекции]
[Лекции]

Версия от 18:24, 15 декабря 2009

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

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

См. также

Вершинно-реберное инцидентное паросочетание, Правильное паросочетание, Совершенное паросочетание, Частичное паросочетание, Взаимные паросочетания.

Литература

[Лекции]