[Править]Литература

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

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

Максимальное паросочетание — это такое паросочетание M в графе G, которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем ребрам паросочетания. Другими словами, паросочетание M графа Gявляется максимальным, если любое ребро в G имеет непустое пересечение по крайней мере с одним ребром из M. Ниже приведены примеры максимальных паросочетаний (красные рёбра) в трёх графах.

Максимальные паросочетания[править | править вики-текст]

Максимальное паросочетание можно найти простым жадным алгоритмом. Наибольшее паросочетание является также максимальным, и, поэтому, имеется возможность найти самое большое максимальное паросочетание за полиномиальное время. Однако неизвестно никакого полиномиального по времени алгоритма для нахождения минимального максимального паросочетания, то есть максимального паросочетания, содержащего минимально возможное число рёбер.

Заметим, что наибольшее паросочетание из k рёбер является рёберным доминирующим множеством^[en] с k рёбрами. И обратно, если задано минимальное рёберное доминирующее множество с k рёбрами, мы можем построить наибольшее паросочетание с k рёбрами за полиномиальное время. Таким образом, задача нахождения минимального по размеру максимального паросочетания эквивалентна задаче нахождения минимального рёберного доминирующего множества^[10]. Обе эти задачи оптимизации известны как NP-трудные и являются классическими примерами NP-полных задач^[11]. Обе задачи могут быть апроксимированы с коэффициентом 2 с полиномиальным временм — просто находим произвольное максимальное паросочетаниеM^[12].

Дан двудольный граф  , содержащий   вершин и   рёбер. Требуется найти наибольшее паросочетание, т.е. выбрать как можно больше рёбер, чтобы ни одно выбранное ребро не имело общей вершины ни с каким другим выбранным ребром.

Описание алгоритма Необходимые определения

Паросочетанием   называется набор попарно несмежных рёбер графа (иными словами, любой вершине графа должно быть инцидентно не более одного ребра из множества  ). Мощностью паросочетания назовём количество рёбер в нём. Наибольшим (или максимальным) паросочетанием назовём паросочетание, мощность которого максимальна среди всех возможных паросочетаний в данном графе. Все те вершины, у которых есть смежное ребро из паросочетания (т.е. которые имеют степень ровно один в подграфе, образованном  ), назовём насыщенными этим паросочетанием.

Цепью длины   назовём некоторый простой путь (т.е. не содержащий повторяющихся вершин или рёбер), содержащий   рёбер.

Чередующейся цепью (в двудольном графе, относительно некоторого паросочетания) назовём цепь, в которой рёбра поочередно принадлежат/не принадлежат паросочетанию.

Увеличивающей цепью (в двудольном графе, относительно некоторого паросочетания) назовём чередующуюся цепь, у которой начальная и конечная вершины не принадлежат паросочетанию.