Паросочетание

Материал из WEGA
Версия от 15:17, 15 декабря 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Паросочетание''' (''Matching'') - произвольное подмножество попарно несмежных р...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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

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

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

Литература

[Лекции]