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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 6: Строка 6:


Другое название --- ''[[Независимое множество ребер графа|Независимое множество ребер]]''.
Другое название --- ''[[Независимое множество ребер графа|Независимое множество ребер]]''.
[[Файл:Matching.png|500px]]


==См. также==
==См. также==

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

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

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

Matching.png

См. также

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

Литература

[Лекции]