В теории графов, паросочетание или независимое множество ребер в графе — это набор попарно несмежных ребер.

Определение

Пусть дан граф G = (V,E), паросочетание M в G это множество попарно несмежных ребер, то есть ребер, не имеющих общих вершин.

Максимальное паросочетание — это такое паросочетание, которое не содержится ни в каком другом паросочетании этого графа.
Наибольшее паросочетание — это такое паросочетание, которое содержит максимальное количество ребер.

Алгоритмы

Алгоритм поиска максимального паросочетания в двудольном графе

Ссылки

• Словарь терминов теории графов