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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 7: Строка 7:
Другое название --- ''[[Независимое множество ребер графа|Независимое множество ребер]]''.
Другое название --- ''[[Независимое множество ребер графа|Независимое множество ребер]]''.


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


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

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

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

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

Matching.png

См. также

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

Литература

[Лекции]