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

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

Определение

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

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

Алгоритмы

Произвольное максимальное паросочетание находится тривиальным жадным алгоритмом за линейное время. Для поиска наибольшего паросочетания могут использоваться: алгоритм Эдмондса, рандомизированный алгоритм на основе матрицы Татта. В случае двудольного графа: венгерский алгоритм, алгоритм Хопкрофта — Карпа (англ.), алгоритм Куна. На текущий момент не известно ни одного полиномиального алгоритма нахождения наименьшего максимального паросочетания, т. е. максимального паросочетания, содержащего наименьшее количество рёбер.

См. также

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

Ссылки

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